§ 10. Циклы

Кто из нас не помнит поучительную историю о том, как Том Сойер по заданию тети Полли красил забор: "Вздыхая, он окунул кисть в ведро, провел ею по доске забора, повторил эту операцию, проделал ее снова..." (Марк Твен. Приключения Тома Сойера).

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

 Подойти к левому краю забора. 
 Покрасить одну доску. 
 Шагнуть вправо на ширину доски. 
 Покрасить одну доску. 
 Шагнуть вправо на ширину доски. 
 Покрасить одну доску. 
 ...

Ясно, что если мы соберемся писать этот алгоритм до конца, покраску забора придется надолго отложить. Если бы мы знали, сколько досок в заборе, мы могли бы завершить составление алгоритма, приписав нужное количество строк. Однако это долгое и однообразное занятие. Да и тетя Полли никогда не считала доски в заборе. Она просто сказала: "Будешь красить, пока забор не кончится". Сама того не зная, она воспользовалась очень распространенным способом организации действий циклом (повтором). Задание тети Полли можно записать в виде следующего алгоритма:

Любуясь Луной, помните: и Луна выполняет циклический алгоритм

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

Вообще, если действия P₁, Р₂, ..., Р_n надо повторять, пока выполняется некоторое условие Q, то мы будем использовать следующую запись:

 Пока Q, повторять: 
 P1 
 Р2 
 ... 
 Рn 
 Конец цикла.

Эта запись означает, что исполнитель сначала проверяет, выполняется ли условие Q. Если да, то совершаются действия P₁, P₂, ..., Р_n (последовательность этих действий называют телом цикла), после чего условие Q проверяется снова и так далее. Если же Q не выполняется, то исполнитель переходит к действию, записанному после строки "Конец цикла". Видно, что слова "Конец цикла" играют здесь ту же роль, что и слова "Конец ветвления" в записи развилки. Может, конечно, случиться и так, что условие Q не выполнено с самого начала (в заборе вообще нет Досок!). Ну что ж, тогда действия, составляющие тело цикла, не совершатся ни разу.

Итак, циклом (повтором) называется такая форма организации действий, при которой одна и та же последовательность действий совершается несколько раз (или ни разу) до тех пор, пока выполняется некоторое условие.

С помощью блок-схемы цикл можно изобразить так, как показано на рисунке 18.

Рис. 18. Блок-схема цикла

Например, блок-схема алгоритма покраски забора выглядит так:

Рис. 19. Блок-схема алгоритма покраски забора

Вопросы

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

2. Как в алгоритмах оформляются циклы?

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

4. Для чего служит указатель "Конец цикла"?

5. Как с помощью блок-схемы изображаются циклы?

Задания для самостоятельного выполнения

1. "Приключения Тома Сойера" начинаются с того, что тетя Полли зовет Тома:

 - Том! 
Нет ответа. 
 - Том! 
Нет ответа. 
 - Том! 
Нет ответа...

Составьте алгоритм вызова Тома.

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

 Найти первое предложение. 
 Перевести его. 
 Записать перевод. 
 Найти следующее предложение. 
 Перевести его. 
 Записать перевод...

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

 Пока не исчезло чувство голода, повторять: 
 Купить пирожок.  
 Конец цикла. 
 Съесть пирожок.

Сумеет ли школьник поесть пирожков? Исправьте алгоритм так, чтобы школьник ушел сытым.

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

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

1азавтра доверчивый школьник получил двойку за домашнее задание. Объясните почему.

4. Дан алгоритм ("решето Эратосфена"):

 Написать все натуральные числа от 2 до n. 
 Пока есть необведенные числа среди невычеркнутых, повторять: 
 Среди невычеркнутых чисел обвести самое маленькое из необведенных. 
 Из необведенных чисел вычеркнуть те, которые кратны последнему обведенному числу. 
 Конец цикла.

а) Выполните алгоритм при n = 6, 12, 100. Какие числа будут обведены после окончания выполнения алгоритма в каждом из этих случаев?

б*) Для решения какой задачи предназначен этот алгоритм? Обоснуйте ваш ответ.

5. Составьте алгоритм нахождения фальшивой монеты среди настоящих монет того же достоинства с помощью чашечных весов, если известно, что фальшивая монета тяжелее настоящей.

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

7. (Продолжение задачи 12 из § 4.) Вслед за разведывательным дозором к той же реке подошел полк. Около берега по-прежнему плавали в лодке два мальчика. Составьте алгоритм переправы полка.