введение. 3 Понятие алгоритма и его свойства. 4 Способы описания алгоритмо

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

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

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

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

Арифметический цикл.

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

Пример 4.

Вывести 10 раз слово «Привет!».

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

Рис. 7. Блок-схема к примеру 4.
Цикл с предусловием.

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

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

Блок-схема данной конструкции представлена на рис. 8 двумя способами: с помощью условного блока а и с помощью блока границы цикла б.

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

Пример 5. Одним из наиболее распространенных алгоритмов, встречающихся в литературе по информатике, является алгоритм Евклида — алгоритм нахождения наибольшего общего делителя двух натуральных чисел m и n (рис. 9).

Рис. 9. Блок-схема алгоритма Евклида.

Опишем его на псевдокоде:

1. Ввод натуральных чисел т и п.

2. Пока т + п делать.

2.1. Если т > п , то т = т — п,

иначе п = п — т .

2.2. Переход к шагу 2.

3. Вывод т (найденный наибольший общий делитель).

4. Конец.
Цикл с постусловием.

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

Рис. 10. Блок-схема цикла с постусловием.
Пример 6.

Составим алгоритм игры «Угадай число». Первый игрок вводит задуманное число от 1 до 50. Второй (угадывающий) вводит другое число и получает один из ответов: «Ваше число меньше», «Ваше число больше» или «Вы угадали». Игра продолжается до тех пор, пока второй игрок не угадает задуманное число.

Составляя алгоритм игры, обозначим х — число, задуманное первым игроком, у — число, вводимое на очередном шаге вторым игроком. Блок-схема алгоритма приведена на рис. 11.

Рис. 11. Блок-схема игры «Угадай число» (пример 6).
Рассмотрим стандартные циклические алгоритмы, такие как вычисление суммы и подсчет количества элементов, удовлетворяющих некоторому признаку.
Суммирование.

Пример 7. Для заданного натурального числа N вычислить сумму:

1 + ½ + ¹/₃ + …+ ¹/_N .

Подсчет суммы осуществляется следующим образом. Сначала считаем, что сумма S есть первое слагаемое (S = 1). Далее к первому слагаемому прибавляем второе, получаем новую сумму S = 1 + ½ . Но на предыдущем шаге S = 1, поэтому можно записать S = S + ½ . К сумме двух первых слагаемых прибавляем третье S = 1+ ½ + 1/3 . Но на предыдущем шагу S = 1 + ½ , поэтому можно записать S = S + 1/3 и т.д.

Получили следующую последовательность шагов:

1) S = 1.

2) S = S + ½ .

3) S = S + 1/3 .

Запишем i-й шаг, опираясь на два предыдущих:

1) S = S + 1/i .

В описанной последовательности i = 1, 2, 3 и т.д. В сумме N слагаемых, поэтому последним значением i будет N. Отсюда нашли правило изменения i = 1, N, 1.

Сверяя инструкции каждого шага, находим, что выражение на первом шаге отличается от других (однотипных). Чтобы оно стало таким как все, в сумму надо добавить S, т.е. записать: S = S+1 (учитываем, что 1 = 1/1). Отсюда для S возникает необходимость задания начального значения, но такого, чтобы S+1=1 (таким должно быть выражение для i = 1), этим числом является нуль, при сложении с нулем сумма не меняется.

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

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

1. Ввод N.

2. S = 0.

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

3.1. S = S + 1/i

4. Вывод S.

5. Конец.

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

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

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

• в теле некоторой циклической конструкции

выполнить команду:

S = S + .

Рис. 12. Алгоритм вычисления суммы.

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

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

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

• в теле некоторой циклической конструкции

выполнить команду:

К=К+ 1.
Пример 8.

Задано 20 чисел. Сколько среди них чисел, больших 10?

Псевдокод:

1. К = 0 {Счетчик чисел, больших 10}.

2. Повторить 20 раз (для i = 1, 20, 1).

2.1. Ввод числа х.

2.2. Если х > 10, то К=К+1.

3. Вывод К.

4. Конец.

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

Замечание: в фигурных скобках {....} принято помещать комментарии к алгоритму.

Рис. 13. Алгоритм примера 8.

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

а — последовательные б — вложенные в — запрещенные

Рис. 14. Расположение циклов.

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

3.4. Рекурсивный алгоритм.

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

4. Простые типы данных: переменные и константы.

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

имени (идентификатора).

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

используемый способ записи информации в ячейки памяти;
необходимый объем памяти для ее хранения.

Объем памяти для каждого типа определяется таким образом, чтобы в него можно было поместить любое значение из допустимого диапазона значений данного типа. Например, тип «байт» может принимать значения от 0 до 255, что в двоичном коде (255₍₁₀₎ = 11111111₍₂₎) соответствует ячейке памяти длиной в 8 бит (или 1 байт).

В описанных выше алгоритмах (примеры 1 - 8) все данные хранятся в виде переменных. Например, инструкция «Ввод двух чисел а, b» означает введение пользователем значений двух переменных, а инструкция «К=К+1» означает увеличение значения переменной К на единицу.

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

Все остальные данные в программе, значения которых не изменяются на протяжении ее работы, называют константами или постоянными. Константы, как и переменные, имеют тип. Их можно указывать явно, например, в инструкции «К = К + 1» 1 есть константа, или для удобства обозначать идентификаторами: рi = 3,1415926536. Только значение рi нельзя изменить, так как это константа, а не переменная.

следующая страница >>