Типовые структуры алгоритмов

Блок-схема разветвляющегося алгоритма

				Ввод: a, х
Нет		Да		х ≥ 0

Y = a x

Y = ax2

Вывод: Y

Выполнение разветвляющегося алгоритма

1.Вводятся значения переменных a, х.

2.Если выражение х ≥ 0 принимает значение True (Да), то

вычисляется значение Y по формуле Y = a x

3. Если выражение х ≥ 0 принимает значение False (Нет), то

вычисляется значение Y по формуле Y = ax2 4. Выводится значение переменной Y.

Циклический алгоритм

Циклическим называется такой алгоритм, в котором определенная группа действий выполняется некоторое количество раз.

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

ϕ = 10°, 20°, 30°,40°, 50°, 60°,70°, 80°, 90°,

11

тогда она однозначно определяется своим начальным значением ϕn = 10°, конечным значением ϕk = 90° и шагом h = 10°.

Повторяющаяся группа действий называется телом цикла. Количество повторений тела цикла определяется условием окончания цикла.

Задача. Составить алгоритм для вычисления значения функций y1 = Sin(ϕr ), y2 =Cos(ϕr ) , где ϕ = 0°, 45°, 90°, 135°, 180°, 225°, 270°, 315°, 360°.

При разработке алгоритма необходимо определить параметры переменной цикла и выделить тело цикла.

Переменная цикла ϕ однозначно определяется своим начальным значением ϕn = 0°, конечным значением ϕk = 360° и шагом h = 45°.

Так как значения угла ϕ выражены в градусах, то для вычисления тригонометрических функций необходимо предусмотреть перевод

угла из градусной меры в радианную по формуле ϕr = 180ϕ πo .

Тело цикла включает в себя повторяющуюся группу действий: перевод угла ϕ из градусной меры в радианную (ϕr), вычисление значений функций y1, y2, вывод текущего значения угла и соответствующих ему значений функций, изменение текущего значения угла на величину шага.

Цикл с предусловием

Если условие окончания цикла расположено перед телом цикла, то такой цикл называется циклом с предусловием.

Блок-схема циклического алгоритма (цикл с предусловием)

Ввод: ϕn, ϕk, h

ϕ = ϕn

А

12

А

Нет			Да			ϕ ≤ ϕk
							ϕ π
					ϕr =
							180

y1 = Sin(ϕr), y2 = Cos(ϕr)

Вывод: ϕ, y1, y2

ϕ = ϕ + h

Выполнение цикла с предусловием

1.Вводятся значения переменной цикла (ϕ): начальное значение (ϕn), конечное значение (ϕk) и шаг (h).

2.Переменной цикла присваивается начальное значение.

3.Вычисляется значение логического выражения ϕ ≤ ϕk, которое определяет условие выполнения цикла:

- если выражение принимает значение True (Да), то выполняется тело цикла, затем происходит возврат на проверку условия;

- если выражение принимает значение False (Нет), происходит выход из цикла и завершение выполнения алгоритма.

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

Цикл с постусловием

Если условие окончания цикла расположено после тела цикла, то такой цикл называется циклом с постусловием.

13

Блок-схема циклического алгоритма (цикл с постусловием)

Ввод: ϕn, ϕk, h

ϕ = ϕn

ϕr = ϕ180π

y1 = Sin(ϕr), y2 = Cos(ϕr)

Вывод: ϕ, y1, y2

ϕ = ϕ + h

Нет

ϕ > ϕk

Да

Выполнение цикла с постусловием

1.Вводятся значения переменной цикла (ϕ): начальное значение (ϕn), конечное значение (ϕk) и шаг (h).

2.Переменной цикла присваивается начальное значение.

3.Выполняется тело цикла.

4.Вычисляется значение логического выражения ϕ > ϕk, которое определяет условие выполнения цикла:

- если выражение принимает значение False (Нет), то еще раз выполняется тело цикла;

- если выражение принимает значение True (Да), происходит выход из цикла и завершение выполнения алгоритма.

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

14

Цикл с параметром

Если количество повторений тела цикла определено по условию задачи, то такой цикл называется циклом с параметром.

Блок-схема циклического алгоритма (цикл с параметром)

Ввод: ϕn, ϕk, h

ϕ = ϕn, ϕk, h

ϕr = ϕ180π

y1 = Sin(ϕr), y2 = Cos(ϕr)

Вывод: ϕ, y1, y2

Выполнение цикла с параметром

1.Вводятся значения переменной цикла (ϕ): начальное значение (ϕn), конечное значение (ϕk) и шаг (h).

2.Для переменной цикла устанавливается начальное значение

(ϕn), конечное значение (ϕk) и шаг (h).

3.Переменной цикла присваивается начальное значение и выполняется сравнение с конечным значением:

- если значение переменной цикла не превысило конечного значения, то выполняется тело цикла;

- если значение переменной цикла больше конечного значения, то происходит выход из цикла и завершение выполнения алгоритма.

4.Каждый раз после выполнения тела цикла осуществляется возврат на начало цикла, переменная цикла автоматически

15

изменяется на величину шага и вновь сравнивается с конечным значением.

5. Выполнение цикла продолжается до тех пор, пока на какомлибо шаге изменения значение переменной цикла не превысит конечного значения.

Переменная цикла не должна изменять своего значения в теле цикла, так как она автоматически изменяется на величину заданного шага при каждом возврате на начало цикла после выполнения тела цикла.

КОМБИНИРОВАННЫЕ АЛГОРИТМЫ

Комбинированными называются такие алгоритмы, в которых применяются линейные, разветвляющиеся и циклические алгоритмы.

Задача 1. Задана последовательность из n элементов. Составить алгоритм вычисления суммы и количества отрицательных элементов последовательности.

При разработке алгоритма переменные, в которых будут накапливаться значения суммы (Sum) и количества отрицательных элементов (Kol) необходимо первоначально обнулить.

Для ввода и обработки элементов последовательности можно использовать цикл с параметром, так как количество элементов известно из условия задачи (n) и их нужно обрабатывать последовательно друг за другом: первый элемент, второй, третий и т.д. Таким образом, переменная цикла (i), которая определяет номер обрабатываемого элемента последовательности, будет изменяться от 1 до n с шагом 1.

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

После того, как будут введены и обработаны все n элементов последовательности, необходимо закончить цикл, вывести полученные результаты и завершить алгоритм.

16

Блок-схема алгоритма определения суммы и количества отрицательных элементов последовательности

Ввод: n

Sum = 0, Kol = 0

								i = 1, n, 1
						Ввод: a
Нет		Да						a < 0
						Sum = Sum + a
						Kol = Kol + 1

Вывод: Sum, Kol

Задача 2. Задана последовательность из n элементов. Составить алгоритм определения максимального элемента последовательности.

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

Для ввода и обработки следующих элементов последовательности обычно используется цикл с параметром, так как количество элементов известно из условия задачи (n) и их

17

нужно обрабатывать последовательно друг за другом. Таким образом, переменная цикла (i), которая определяет номер обрабатываемого элемента последовательности, будет изменяться от 2 до n с шагом 1. В теле цикла необходимо осуществлять ввод очередного элемента последовательности (а) и сравнение его с максимальным значением (Мах). Если значение а больше максимального значения, тогда этот элемент нужно принять за максимальный. В противном случае необходимо выполнять возврат на начало цикла для обработки следующего элемента последовательности.

После того, как будут введены и обработаны все n элементов последовательности, необходимо закончить цикл, вывести полученное максимальное значение и завершить алгоритм.

Блок-схема алгоритма определения максимального элемента последовательности

Ввод: n

Ввод: а

Мах = а

i = 2, n, 1

Ввод: a

Нет		Да			a > Max
				Max = a

Вывод: Max

18

Задача 3. Задано натуральное число. Составить алгоритм вычисления количества цифр в записи числа.

Для того чтобы определить количество цифр в заданном числе нужно делить это число на 10 до тех пор, пока частное не станет меньше 1. Количество выполненных делений будет соответствовать количеству цифр.

Например, задано число 1234. Осуществляем поэтапное деление этого числа на 10:

1). 1234 : 10 = 123,4

2). 123,4 : 10 = 12,34

3). 12,34 : 10 = 1,234

4). 1,234 : 10 = 0,1234

Деление прекращается, так как частное стало меньше 1. Таким образом, количество цифр в записи числа 1234 равно 4.

Блок-схема алгоритма определения количества цифр в записи числа

Ввод: b

k = 0

							del =		b
							10
						k = k + 1
						b = del
Нет			Да					del < 1
							Вывод: k

При разработке алгоритма переменная, в которую будет накапливаться количество цифр заданного числа (k) необходимо первоначально обнулить.

19

Для обработки введенного числового значения (b) нужно использовать цикл с постусловием, так как количество повторений тела цикла из условия задачи неизвестно и будет определяться в процессе его выполнения. Переменной цикла будет величина del, которая является частным от деления числового значения b на 10. При каждом выполнении тела цикла счетчик количества цифр (k) увеличивается на 1. Текущее значение переменной b принимается равным очередному частному от деления на 10. Деление продолжается до тех пор, пока частное не станет меньше 1.

После того, как выполнение цикла будет закончено, необходимо вывести полученное количество цифр и завершить алгоритм.

Задача 4. Задано натуральное число. Составить алгоритм вычисления суммы цифр в записи числа.

Для того чтобы вычислить сумму цифр натурального числа нужно последовательно выделять одну цифру за другой, начиная с младшего разряда, и добавлять выделенную цифру в сумму.

Для выделения цифры из числа необходимо: разделить число на 10, целую часть частного умножить на 10 и полученный результат отнять от целой части числа. Полученную цифру добавить в сумму. Эту последовательность действий нужно повторять до тех пор, пока целая часть очередного частного не станет равна 0.

Например, задано число 1234. На каждом шаге необходимо выполнить следующую последовательность действий:

1). 1234 : 10 = 123,4 1234 – 123 10 = 4 s = 4 2). 123 : 10 = 12,3 123 – 12 10 = 3 s = 4 + 3 = 7 3). 12 : 10 = 1,2 12 – 1 10 = 2 s = 7 + 2 = 9

4). 1 : 10 = 0,1 1 – 0 10 = 1 s = 9 + 1 = 10

Деление прекращается, так как целая часть частного стала равна 0. Таким образом, сумма цифр числа 1234 равна 10.

При разработке алгоритма переменная, в которую будет накапливаться сумма цифр заданного числа (s) необходимо первоначально обнулить.

Для обработки введенного числового значения (b) нужно использовать цикл с постусловием, так как количество повторений

20