алгоритм и его свойства

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

Различают следующие виды алгоритмов: линейные, разветв-

ляющиеся, циклические.

Линейный алгоритм

Линейным называется такой алгоритм, в котором действия выполняются последовательно сверху вниз в том порядке, в котором они записаны. Такой порядок выполнения действий называется естественным.

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

h	A	=	t	;	h =	t	;	h =	t	,
			2a		B	2b		C	2c
где t = p( p −a)( p −b)( p −c),						p = a +b +c ;

2

a, b, c - стороны треугольника.

Блок-схема линейного алгоритма

Ввод: a, b, c

p =a+2b+c

t = p( p −a)( p −b)( p −c)

hA = 2ta ; hB = 2tb ; hC = 2tc

Вывод: hA, hB, hC

Выполнение линейного алгоритма

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

2.Вычисляется значение переменной р.

3.Вычисляется значение переменной t.

11

4.Вычисляются значения переменных hA, hB, hC.

5.Выводятся значения переменных hA, hB, hC.

Пример 5: Установить порядок выполнения операций для вычисления значения выражения F=2*(X+Y)2-Y.

1F=F-Y

2F=X+Y

3F=F*F

4F=F+F

Решение:

2F=X+Y

3F=F*F = (X+Y)* (X+Y) = (X+Y)2

4F=F+F = (X+Y)2 + (X+Y)2 = 2*(X+Y)2

1F=F-Y = 2*(X+Y)2 – Y.

Пример 6: Установить порядок выполнения операций так, что-

бы при начальных значениях A=2, B=5, C=-5, результирующим стало значение C=5.

1B=A+B

2A=A*B

3C=B+10

4C=C/5

Решение:

2A=A*B = 2*5 = 10

1B=A+B = 10+5 = 15

3C=B+10 = 15+10 = 25

4C=C/5 = 25/5 =5.

Разветвляющийся алгоритм

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

Задача 2. Составить алгоритм вычисления значения функции Y для заданных значений а, х:

	x,		если x ≥ 0
a
Y =
	2	,	если x < 0
ax

12

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

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

Y = a x

Y = ax2

Вывод: Y

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

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

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

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

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

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

Пример 7: При X=8, Y=2 после выполнения фрагмента алго-

ритма чему будет равно значение A?
если X<Y, то A=X*Y
иначе A=X/Y
если A>Y, то A=A/2
иначе A=A*2
если A< X то A=A+X
Решение:				False,
Условие X<Y	(8<2)	принимает	значение		поэтому
А = X/Y = 8/2 = 4.				True,
Условие A>Y	(4>2)	принимает	значение		поэтому
А = А/2 = 4/2 = 2.				True,
Условие A<Х	(2<8)	принимает	значение		поэтому
А = А+Х = 2+8 = 10.

13

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

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

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

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

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

Тело цикла – это повторяющаяся группа действий.

Условие окончания цикла – это количество повторений тела цикла.

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

ций 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;

-вывод текущего значения угла и соответствующих ему значений функций;

-изменение текущего значения угла на величину шага.

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

Цикл с предусловием – это цикл, в котором условие окончания цикла расположено перед телом цикла.

14

Блок-схема цикла с предусловием

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

ϕ = ϕn

Нет			Да					ϕ ≤ ϕk
								ϕr =		ϕ π
								180
								y1 = Sin(ϕr), y2 = Cos(ϕr)
								Вывод: ϕ, y1, y2
								ϕ = ϕ + h

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

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

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

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

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

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

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

15

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

Цикл с постусловием – это цикл, в котором условие окончания цикла расположено после тела цикла.

Блок-схема цикла с постусловием

Ввод: ϕ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 (Да), происходит выход из цикла и завершение выполнения алгоритма.

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

16

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

Цикл с параметром – это цикл, в котором количество повторений тела цикла определено по условию задачи.

Блок-схема цикла с параметром

Ввод: ϕ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.Каждый раз после выполнения тела цикла осуществляется возврат на начало цикла, переменная цикла автоматически изменяется на величину шага и вновь сравнивается с конечным значением.

17

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

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

Пример 8: Чему равно значение переменной d После выполнения фрагмента алгоритма?

b := 10; d := 40

нц пока d >= b d := d - b

кц Решение: d := 40

Выражение d >= b (40>=10) принимает значение True, поэтому выполняется тело цикла d:=d–b=40-10=30. Возврат на начало цикла.

Выражение d >= b (30>=10) принимает значение True, поэтому выполняется тело цикла d:=d–b=30-10=20. Возврат на начало цикла.

Выражение d >= b (20>=10) принимает значение True, поэтому выполняется тело цикла d:=d–b=20-10=10. Возврат на начало цикла.

Выражение d >= b (10>=10) принимает значение True, поэтому выполняется тело цикла d:=d–b=10-10=0. Возврат на начало цикла.

Выражение d >= b (0>=10) принимает значение False, поэтому выполнение цикла заканчивается. Значение d=0.

Пример 9: Какие значения примут переменные n, s в результате выполнения фрагмента алгоритма;

s=1; n=1

НЦ для i=2 до 5 (начало цикла) n=n+1; s=s+i

КЦ (конец цикла)

Решение: s=1; n=1

Для i=2 выполняется тело цикла: n=n+1=1+1=2; s=s+i=1+2=3. Для i=3 выполняется тело цикла: n=n+1=2+1=3; s=s+i=3+3=6. Для i=4 выполняется тело цикла: n=n+1=3+1=4; s=s+i=6+4=10. Для i=5 выполняется тело цикла: n=n+1=4+1=5; s=s+i=10+5=15.

Для i=6 выполнение цикла заканчивается. Значения n=5; s=15.

18

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

Вычисление суммы и количества элементов последовательности

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

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

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

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

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

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

Ввод: n

Sum = 0, Kol = 0

А

19

А

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

Вывод: Sum, Kol

Поиск максимального элемента последовательности

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

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

(Мах).

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

20