Доклад на тему «Алгоритмическая структура цикл»

Введение

Если открыть любую программу, хоть простенькую игру про змейку, хоть школьный электронный дневник, внутри обязательно найдётся место, где что-то повторяется. Змейка ползёт клетку за клеткой, дневник по очереди выводит оценки за четверть, а исполнитель Робот в КуМире идёт вправо, пока не упрётся в стену. Записывать «шаг вправо» двадцать раз подряд неудобно, поэтому для повторения в алгоритмах существует особая конструкция, цикл.

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

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

Основой стали учебники информатики Л. Л. Босовой и К. Ю. Полякова для седьмого класса, а для более строгих формулировок пригодились книги Никлауса Вирта (того самого, кто придумал язык Паскаль) и Дональда Кнута. Примеры я записывал на Python и на Паскале, так как в школах сейчас используют в основном эти два языка.

С циклами многие впервые встречаются ещё в КуМире, задолго до «настоящих» языков. Там у Робота есть запись нц 5 раз … кц, то есть «повтори пять раз», и запись нц пока справа свободно … кц, где Робот шагает, пока не наткнётся на стену. По сути, это уже два разных вида цикла, только записанные по-русски.

Глава 1. Основные виды циклических алгоритмов

1.1 Виды циклов

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

Удобнее всего сравнить их, поставив рядом, поэтому основные отличия я собрал в таблицу 1. Обратите внимание на третий столбец, про минимальное число выполнений тела, потому что именно в нём чаще всего ошибаются.

Таблица 1 — Сравнение видов цикла

Первый вид называется циклом с предусловием. Название говорит само за себя: условие проверяется перед телом, и если оно истинно, тело выполняется, после чего проверка повторяется. Когда условие с самого начала ложно, программа просто перепрыгивает через цикл, и тело не выполняется ни одного раза.

В качестве житейского примера можно взять такую задачу: на карте у школьника 1000 рублей, на обеды уходит по 150 рублей в день, и нужно понять, на сколько дней хватит денег. Сколько будет повторов, заранее неизвестно, это и есть ответ, поэтому while здесь подходит лучше всего: пока на карте больше нуля, вычитаем 150 и добавляем к счётчику дней единицу. Получится семь дней, хотя на седьмой обед денег хватит уже не целиком (останется только 100 рублей).

У цикла с постусловием проверка стоит в конце, после тела. Из-за этого тело обязательно выполнится хотя бы один раз, даже если условие с самого начала было ложным. В Паскале это конструкция repeat … until, и у неё есть неочевидная особенность, о которой стоит помнить: повторы идут, пока условие ложно, а прекращаются, когда оно стало истинным, то есть ровно наоборот по сравнению с while.

Самым понятным примером такого цикла обычно служит ввод пароля. Спросить пароль нужно в любом случае хотя бы один раз, а проверять, верный ли он, имеет смысл только после ввода. В Python отдельного цикла repeat нет, поэтому его заменяют записью while True с командой break внутри, которая работает так же.

Третий вид называют циклом с параметром или циклом со счётчиком. Здесь число повторов известно ещё до начала, а специальная переменная (параметр) сама по очереди принимает значения от начального до конечного. В Паскале это выглядит как for i := 1 to 10 do, а в Python как for i in range(1, 11), и в обоих случаях тело выполнится десять раз.

Через for удобно выводить таблицу умножения или рисовать черепашкой правильный шестиугольник, где шесть раз подряд надо пройти вперёд и повернуть на 60 градусов. Для новичка у такого цикла большой плюс: счётчик растёт сам, и про него невозможно забыть, как это бывает с while.

Паскаль Никлаус Вирт придумал в 1970 году специально для обучения студентов, и его for намеренно простой: параметр шагает только на единицу, вверх через to или вниз через downto. Python появился в 1991 году у голландца Гвидо ван Россума, и там у range есть третий аргумент, шаг, так что range(0, 100, 5) сразу перебирает числа, кратные пяти. Из-за этой разницы одна и та же школьная задача на двух языках выглядит немного по-разному.

1.2 Особенности использования циклов

Учебник Полякова советует сначала решить, известно ли число повторов, и только потом выбирать цикл. Совет кажется очевидным, однако на уроках чаще пишут тот цикл, который лучше запомнили, и задачу «вводить числа, пока не введут ноль» пытаются уложить в for, а потом долго ищут ошибку.

Про сумму чисел от 1 до N есть известная история. Маленькому Карлу Гауссу учитель будто бы велел сложить числа от 1 до 100, рассчитывая занять класс надолго, а мальчик через пару минут ответил 5050, сложив пары с краёв: 1 и 100, 2 и 99 и так далее. Компьютеру такая хитрость не нужна, и на Python цикл while пишется как s = 0, i = 1, while i <= N: s = s + i, i = i + 1, а вариант с for получается на строчку короче: s = 0 и for i in range(1, N + 1): s = s + i.

У варианта с while есть подвох со счётом шагов: условие i <= N проверяется на один раз больше, чем выполняется тело, потому что выйти из цикла программа может только после проверки, которая дала «ложь». При N = 10 тело сработает десять раз, а сравнений наберётся одиннадцать, как на рисунке 1, и в задаче, где спрашивают именно число сравнений, эта лишняя единица меняет ответ.

Бесконечный цикл получается легче, чем кажется на первый взгляд: стоит забыть строчку i = i + 1, и переменная навсегда останется единицей, условие так и будет истинным, а программа будет складывать единицы, пока кто-нибудь не нажмёт «Стоп». У for этой беды почти нет, ведь счётчик там увеличивает сам язык.

Правая граница в range не входит в диапазон, и range(1, 10) даёт девять чисел, а не десять. Так сделано не случайно: ещё в 1982 году нидерландский учёный Эдсгер Дейкстра в короткой заметке объяснял, почему полуоткрытые промежутки удобнее, и Python последовал этой логике. В Паскале же for i := 1 to 10 доходит ровно до десяти, поэтому тот, кто пересел с одного языка на другой, первое время ошибается на единицу.

Любопытно, что сама идея повторять группу команд старше компьютеров. Ада Лавлейс в 1843 году, описывая вычислительную машину Чарльза Бэббиджа, уже писала о повторении одной и той же последовательности операций для расчёта чисел Бернулли. А в первом массовом языке программирования, Фортране конца 1950-х, цикл со счётчиком записывался словом DO, и в таком виде дожил в этом языке до сих пор.

Если вложить один цикл в другой, число повторов перемножается. Таблица умножения 9 на 9 даёт 81 выполнение тела, а если добавить третий уровень, их станет 729. Компьютер с этим справится мгновенно, но человеку разбираться в трёх этажах вложенности тяжело.

Ещё в циклах бывают команды break и continue: первая сразу выходит из цикла, вторая переходит к следующему повтору. На уроках их обычно советуют не злоупотреблять и по возможности записывать условие остановки прямо в заголовке while, чтобы было видно, когда цикл закончится.

Проверить цикл проще всего на листке в клетку. Берём маленькое N, скажем 3, и после каждого шага пишем в табличку значения i и s: сначала 1 и 1, потом 2 и 3, потом 3 и 6, а дальше i становится 4, и цикл заканчивается. Называется это трассировкой, и в заданиях, где программу дают на бумаге и спрашивают, что она выведет, по-другому просто не получится.

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