§2. Циклические алгоритмы.

В некотором средневековом городе Буридане жил осёл. Был он до того нерешителен, что умер с голоду, когда перед ним положили 2 охапки сена. Не сумел сделать выбор! С тех пор всех, кто останавливается перед простым выбором, называют буридановыми ослами.

Но мы с вами умеем решать задачи, содержащие выбор. Давайте решим задачу нахождения наибольшего значения среди трёх различных чисел. Построим блок-схему:

С двумя условиями эта задача решается следующим способом:

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

Решение.

Пусть K=1 – первоначальное количество бактерий. Что произойдёт с бактериями после первой минуты? (Количество бактерий увеличится в 2 раза). Чему будет равно К? (К=К*2).

Как вы думаете, сможет ли теперь количество бактерий быть равным N? Превысить число N? (Чтобы ответить на этот вопрос, надо сравнить К и N).

Проверяем: если К=N, то вывести на экран количество минут, когда это произойдёт. Что теперь необходимо сделать? (Опять увеличить число бактерий в два раза).

Получается, что нам необходимо каждый раз повторять одни и те же вычисления. Какое действие нам необходимо повторять? (К:=К*2).

Какие ассоциации у вас возникают со словом «цикл»?

Цикл дословно с греческого означает «круг». Какие действия мы можем назвать циклическими? (Действия, которые повторяются, «выполняются по кругу»). Какие вам известны циклические процессы, например в природе? (Круговорот воды, смена времени года, дня, биоритмы человеческого организма).

Циклический алгоритм – это алгоритм, в котором происходит многократное повторение некоторой последовательности действий.

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

Рассмотрим примеры.

Пример 1: Имеется коробка карандашей. Вам надо поточить все карандаши в этой коробке.

Ход решения:

Вы берёте и точите один карандаш. Откладываете его в сторону. Затем проверяете, остались ли карандаши в коробке. Если обозначить за условие вопрос: «Коробка пуста?», то можно составить следующий алгоритм (рис. 3).

Если коробка не пуста (условие ложно), то снова выполняется действие «заточить карандаш». Как только условие становится истинным (коробка пуста), цикл прекращается. Циклы такого вида называют - циклы с постусловием или определенные циклы (или цикл типа «ДЛЯ»). Общий вид цикла с постусловием следующий (рис. 4).

П ример 2: Вам захотелось купить диск с новой компьютерной игрой, который стоит 140 рублей. Вы проверяете, какая сумма лежит в вашей копилке. Если эта сумма больше или равна 140 рублей, то вы идете покупать игру, иначе продолжаете бросать в копилку монеты до тех пор, пока будет накоплена нужная сумма. Если обозначить за условие вопрос: «В копилке меньше 140 рублей?», то решение этой задачи можно изобразить следующим алгоритмом (рис. 5).

Циклы такого вида называют - циклы с предусловием или неопределенные циклы (или циклы типа «ПОКА»). Общий вид цикла с предусловием следующий (рис.6).

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

Особенности циклов с постусловием:

1. Тело цикла расположено до проверки условия.

2. Цикл выполняется хотя бы 1 раз.

Особенности цикла с предусловием:

1. Тело цикла расположено после проверки условия.

2. Цикл может ни разу не выполниться.

Частным случаем цикла с предусловием является цикл с параметром. Общий вид цикла с параметром (рис.7):

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

Пример 3: На уроке физкультуры вы должны пробежать 9 кругов вокруг стадиона. (рис.8):

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

Также с циклическими алгоритмами мы встречаемся с вами в пословицах и поговорках, например: семь раз отмерь, один раз отрежь; семеро одного не ждут. Циклический алгоритм используется в программах анимации. Например, в программе Microsoft GIF Animator для создания анимации нужно нарисовать 3 фазы движения (3 картинки), собрать пакет из трех картинок, дать команду Цикл. После этого будет воспроизводиться анимация.

Теперь давайте вернёмся к задаче о бактериях.

Если решать эту задачу с использованием цикла с параметром, то нужно точно знать, сколько раз необходимо повторить тело цикла. Можно ли сказать из условия задачи, сколько раз нужно выполнить цикл? Значит, такую задачу нельзя решить с использование цикла c параметром.

Попробуйте переформулировать условие задачи так, чтобы её можно было решить этим способом.

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

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

После того как все справятся с заданием, представителям групп (добровольцам или вызвать по своему усмотрению) потребуется объяснить решение задачи на доске (рис 9, 10, 11)

Вопросы для повторения и задания:

1. Какой алгоритм называется циклическим?

2. Приведите примеры циклических процессов.

3. Что такое тело цикла?

4. Какие циклы называются определенными?

5. Что происходит в циклах типа «ПОКА»?

6. Составить алгоритм (блок-схему) для решения следующей задачи:

Начав тренировки, спортсмен в первый день пробежал 10 км. Каждый последующий день он увеличивает дневную норму на 10% от нормы предыдущего дня. Какой путь пробежит спортсмен на N-й день тренировок? Задачу необходимо решить с использованием всех видов циклов.

7. Подберите задачу из жизни, которую можно решить с помощью

циклического алгоритма и опишите её решение в виде блок-схемы.