Протокол возведения числа a в степень n

Два последних примера показывают, как происходит накапливание произведения.

Пример 7. Найти максимальный элемент последовательности a₁, a₂, … a_n и определить его порядковый номер.

Входные данные: a₁, a₂, … a_n – числовая последовательность, элементы которой вводятся с клавиатуры; здесь n – число элементов последовательности.

Выходные данные: max - максимальный элемент последовательности (вещественное число), k – его порядковый номер.

Промежуточные данные: i– целочисленная переменная, принимающая значения

от 1 до n с шагом 1, параметр цикла. Блок-схема приведена на рис.17.

 

max = ai, k = i

 

Рис. 17. - Нахождение максимального элемента последовательности

Следующий пример демонстрирует один из важнейших элементов циклического процесса – накапливание суммы.

Пример 8. Вычислить сумму натуральных четных чисел, не превышающих N.

Входные данные: N – целое число.

Выходные данные: S – сумма четных чисел.

Промежуточные данные: i – переменная, принимающая значения от 2 до N с шагом 2, следовательно, также имеет целочисленное значение.

При сложении нескольких чисел необходимо накапливать результат в определенном участке памяти, каждый раз считывая из этого участка предыдущее значение суммы и прибавляя к нему следующее слагаемое. Для выполнения первого оператора накапливания суммы из участка памяти необходимо взять такое число, которое не влияло бы на результат сложения. Т.е. перед началом цикла переменной, предназначенной для накапливания сумы, необходимо присвоить значение нуль. Блок-схема решения этой задачи представлена на рис.18.

 

S = S + i

		Печать S

 

 

Рис. 18. - Вычисление суммы четных натуральных чисел

В таблице приведены результаты тестирования алгоритма для n=15. Несложно заметить, что при нечетных значениях параметра цикла алгоритм не изменится.

i
S

Протокол вычисления суммы четных натуральных чисел

 

 

АЛГОРИТМЫ СО СТРУКТУРАМИ ВЛОЖЕННЫХ ЦИКЛОВ

Нередко при алгоритмическом решении задачи возникает необходимость создания цикла, содержащего в своем теле другой цикл. Такие вложенные друг в друга циклы относятся к структурам вложенных циклов. Порядок вложенности циклов, когда в теле внутреннего цикла содержатся другие циклы, может быть достаточно большим. Этот порядок определяется методом, с помощью которого достигается решение поставленной задачи. Так, при обработке одномерных массивов, как правило, удается построить алгоритмическую схему без вложения циклов. Однако в ряде случаев при решении таких задач без вложенных циклов не обойтись.

Отметим, что все вложенные друг в друга циклы, включая наружный, должны иметь счетчики с различными именами. Вне этих циклов счетчики могут быть использованы как обычные переменные или как счетчики других циклов.

Структура вложенных циклов:

end(2)

	end(1)

Рис. 19. - Структура вложенных циклов

Пример 1. Рассмотрим задачу сортировки одномерного массива А длины N. Отсортировать массив – значит расположить его элементы в порядке возрастания или убывания.

Опишем метод сортировки массива в порядке возрастания. Сначала выполняется проход по массиву с целью определения в нем наименьшего элемента. Затем производится перестановка этого элемента с первым. Далее совершается второй проход по массиву, начиная со второго элемента. Найденный наименьший элемент переставляется со вторым и т. д. После (N-1)-го прохода с выполнением названных операций массив окажется отсортированным.

Замечание. Перестановка элементов осуществляется с помощью «буферного» элемента. Поставим задачу: поменять местами элементы A_i и A_j одномерного массива (последовательности) A₁, A₂, …. A_n. Пусть С - буферный элемент. Тогда последовательность действий С=A_i, A_i = A_j, A_j=С осуществляет перестановку этих элементов в массиве {A}.

Задание. Построить блок-схему алгоритма сортировки одномерного массива А длины N.

Входные данные: неупорядоченная последовательность элементов A₁, A₂, …. A_n.

Выходные данные: упорядоченная последовательность элементов A₁, A₂, …. A_n.

Промежуточные данные: буферный элемент С, индексы текущих элементов i и j.

Блок-схема приведена на рис.20.

 

нет

да

 

 

Рис. 20. Блок-схема алгоритма сортировки одномерного массива А длины N

 

Алгоритмы со структурами вложенных циклов часто используют при решении задач обработки двумерных массивов. В таких алгоритмах счетчики циклов используются для манипуляции с индексами массивов.

Пример 2. Дан двумерный массив А ( матрица ), состоящий из N строк и М столбцов. Найти сумму положительных и произведение отрицательных элементов этого массива.

Входные данные: двумерный массив А с элементами A_ij, где i – номер строки, j – номер столбца элемента.

Выходные данные: сумма S и произведение P элементов массива. Начальное значение суммы считается равным нулю (S=0), начальное значение произведения – единице (Р=1).

Промежуточные данные: индексы текущих элементов i и j.

Блок-схема приведена на рис.21.

 

нет

да

 

 

Рис. 21. - Блок-схема алгоритма вычисления суммы S и произведения P элементов массива

Итак, рассмотренных примеров вполне достаточно, чтобы выполнить индивидуальные задания.

Вариант 1.

 

1. Составить блок-схему линейного алгоритма вычисления величины работы, совершенной при равномерном подъеме груза массой М кг на высоту H м. Ускорение свободного падения описать как константу G = 9,81.

Составить блок-схему алгоритма процесса ветвления. Дано целое число. Если оно является положительным, то прибавить к нему 1; если отрицательным, то вычесть из него 2; если нулевым, то заменить его на 10. Вывести полученное число.

3. Составить блок-схему алгоритма циклического процесса. Составьте блок-схему программы, которая вычисляет произведение чисел от 1 до N. Значение N вводится с клавиатуры.

 

 

Вариант 2.

 

1. Составить блок-схему линейного алгоритма определения силы тока в проводнике, длина которого l м, а сечение этого проводника – S мм². Проводник выполнен из меди и включен в цепь таким образом, что на его концах наблюдается напряжение U В.