Разветвляющаяся алгоритмическая конструкция

Линейная алгоритмическая конструкция

Основные алгоритмические конструкции

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

Линейной называют алгоритмическую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого i-го действия (шага) выполняется (i+1)-е действие (шаг), если i-е действие – не конец алгоритма.

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

Псевдокод: 1. Ввод двух чисел а, b. 2. Вычисляем площадь S = а·b. 3. Вывод S. 4. Конец.

начало Ввод а и b S=a*b S конец

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

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

Неполное ветвление предполагает наличие некоторых действий алгоритма только на одной ветви (то), вторая ветвь отсутствует, т.е. для одного из результатов проверки никаких действий выполнять не надо, управление сразу переходит к точке слияния (рис. 5.1 справа).

условие

да

нет

Действие 1

Действие 2

условие

да

нет

Действие 1

Рис. 5.2. Ветвление

Пример 5.2. Найти значение наименьшего из двух чисел и вывести его на экран.

В данном примере реализовано полное ветвление. ЕСЛИ значения входных данных таковы, что а < b, ТО выполняется левая часть ветвления, переменная min примет значение a, ИНАЧЕ, когда
а >b, выполняется левая часть ветвления, переменная min примет
значение b.

Псевдокод: 1. Ввод двух чисел а, b. 2. ЕСЛИ а < b, ТО min=а, ИНАЧЕ min=b 3. Выводим min. 4. Конец.

начало Ввод а и b min конец a<b да нет min=a min=b

Пример 5.3. Вывести на экран для действительного числа x значение √x, если это возможно.

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

Псевдокод: 1. Ввод чисел x. 2. ЕСЛИ x ≥0, ТО 2.1. y=√x. 2.2. Вывести y. 3. Конец.

начало Ввод x y конец x≥0 да нет y=√x

В данном примере реализовано неполное ветвление. ЕСЛИ значение x неотрицательно, ТО выполняется линейный алгоритм по вычислению y.

5.3.3. Алгоритмическая конструкция «Цикл»

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

Рассмотрим три типа циклических алгоритмов: цикл с параметром (который называют арифметическим циклом), цикл с предусловием и цикл с постусловием (их называют итерационными).

Правило изменения параметра i: i =N,K,h означает
1-й шаг цикла	i-N
2-й шаг цикла	i = N + h
3-й шаг цикла	i = N + 2h
и т.д.
последний шаг	i = К

Арифметический цикл. В арифметическом цикле число его шагов (повторений) одно­значно определяется правилом изменения параметра, которое зада­ется с помощью начального (N) и конечного (К) значений параметра и шагом (h) его изменения. Т.е., на первом шаге цикла значение па­раметра равно N, на втором – N + h, на третьем – N + 2h и т.д. На последнем шаге цикла значение параметра не больше К, но та­кое, что дальнейшее его изменение приведет к значению, большему, чем К.

Пример 5.4. Вывести 5 раз «ЧитГУ».

Параметр цикла обозначим i, он будет отвечать за количество выведенных слов. При i = 1 будет выведено первый раз слово, при i = 2 будет выведено второй раз это же слово и т.д. Так как требуется вывести 5 слов, то последнее значение параметра i = 5. В заданном примере требуется 5 раз повторить одно и то же действие: вывести слово «ЧитГУ». Составим алгоритм, ис­пользуя арифметический цикл, в котором правило изменения параметра i = 1, 5, 1. То есть начальное значение параметра i=1; конечное значение i = 5; шаг изменения h = 1. На рис. 5.3 представлена блок-схема алгоритма решения данной задачи.

начало

ЧитГУy

конец

i=1, 10, 1

Рис. 5.3. Блок-схема решения задачи

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

Количество шагов цикла заранее не определено и зависит от входных данных задачи. В данной циклической структуре сначала проверяется значение условного выражения (условие) перед выполнением очередного шага цикла. Если значение условного выражения истинно, исполняется тело цикла. После чего управление вновь передается проверке условия и т.д. Эти действия повторяются до тех пор, пока условное выражение не примет значение ЛОЖЬ. При первом же несоблюдении условия цикл завершается.

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

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

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

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

Пример 5.5. Построить таблицу значений функции y=x³ на интервале [1;3] с шагом 0,1.

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

Псевдокод 1. Определить начальное значение x=1. 2. Пока x≤3 делать. 2.1. Вычислить y=x^3. 2.2. Вывести значения x и y. 2.3. Увеличить x на величину шага. 3. Конец.	начало x, y конец x≤3 x=0 да y=x^3 x=x+0.1 нет	Цикл с предусловием
Псевдокод 1. Определить начальное значение x=1. 2. Повторить действия. 2.1. Вычислить y=x^3. 2.2. Вывести значения x и y. 2.3. Увеличить x на величину шага. пока не выполнится условие x>3 3. Конец.	начало x, y конец x>3 x=0 да y=x^3 x=x+0.1 нет	Цикл с постусловием

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

Пример 5.6. Вычислить = слаг₁+слаг₂+…+слаг_N

Алгоритм на псевдокоде:

1. Ввод N.

2. S = 0.

3. Для i= 1, N, 1 повторить:

3.1. S = S + слагаемое.

4. Вывод S.

5. Конец.

Сформулируем правило суммирования:

начальное значение суммы S = 0;

в теле некоторой циклической конструкции выполнить команду: S = S + <слагаемое>.

Пример 5.7. Подсчет количества элементов. Произведем счет: 1, 2, 3, 4, 5 и т.д., этот процесс является циклическим, так как каждый раз мы со­вершаем одно и то же действие: предыдущее натуральное число увеличиваем на единицу. Обозначив через К - счетчик искомых элементов, легко получить правило счетчика: К = К + 1 (на очередном шаге цикла). Но при первом подсчете должны получить значение К, равное единице, а до начала счета счетчик должен быть пуст, следовательно, начальное значение счетчика равно нулю.

Правило счетчика:

начальное значение счетчика К = 0;

в теле некоторой циклической конструкции выполнить команду: К = К + 1.

Дата добавления: 2014-11-29