LANG·I Язык Глава 4 из 65
Снова и снова
Ткацкая мастерская. Станок Жаккара повторял узор по цепочке перфокарт, а мы научим Python повторять что угодно, от подсчёта сумм до ковров из символов и черепашьих рисунков. Циклы while и for, накопители, цикл в цикле — и цикл, который не останавливается.
Язык
Опирается на: 03 · Развилки
Что вы унесёте из главы
- повторять действия циклами for и while — заданное число раз или пока выполняется условие
- считать суммы, количества и рекорды накопителями, ткать узоры вложенными циклами
- находить бесконечный цикл и ошибку «на единицу» в range
Прошлая глава оставила нас у решётки с кодовым замком. Замок умеет сказать «мало» или «много», но спрашивает один раз: ошиблись — и квест окончен. Спросить снова можно, только скопировав кусок программы, а спрашивать до победы — только копируя его без конца. Эта глава о том, как заставить машину повторять: десять раз, миллион раз или пока что-нибудь не случится.
Вот как выглядит повторение без новых средств. Программа ткёт на экране кусочек шахматной ткани, четыре ряда:
Четыре ряда — четыре строки. Сто рядов — сто строк, и в каждой надо не ошибиться ни в одной клетке. Захотите ткань пошире — переписывайте все сто. Та же беда два века назад мучила ткачей узорного шёлка, и справились они с ней так же, как справимся мы: научили машину повторять.
Лион, 1804: станок, который помнит узор
Бэббидж тогда проектировал Аналитическую машину, и Ада Лавлейс написала для неё программу вычисления чисел Бернулли — с ошибкой, которую мы разбирали в главе 1. Команды машина должна была получать на перфокартах, как станок Жаккара. В Примечании A к своему переводу Лавлейс сформулировала это так (перевод наш):
Можно очень точно сказать, что Аналитическая машина ткёт алгебраические узоры, как станок Жаккара ткёт цветы и листья.
Цепочку карт, замкнутую в кольцо, программист назвал бы циклом: одна и та же последовательность команд выполняется снова и снова. Станком в этой главе будет Python, а узоры мы будем ткать из чисел, символов и линий.
Челнок ходит, пока… Цикл while
В Python два вида циклов. Первый звучит почти как русская фраза: «пока условие верно — повторяй». Запустите программу, а потом нажмите «Шаги» и пройдите её по строке: стрелка после четвёртой строки будет возвращаться ко второй.
Устроено это так же, как if из прошлой главы: заголовок с условием и двоеточием, под ним блок с отступом. Разница одна. Выполнив блок, if идёт дальше, а while возвращается к своему условию и проверяет его снова. Пока условие истинно, блок выполняется ещё раз, и ещё. Как только оно стало ложным, Python перепрыгивает через блок и идёт к первой строке после него.
Такая конструкция называется циклом, блок под заголовком — телом цикла, а один проход по телу — итерацией. Здесь итераций три: при throws, равном 3, 2 и 1. Когда throws стал нулём, условие throws > 0 оказалось ложным, и цикл кончился.
Лавлейс описала это раньше, чем появились машины, способные такое выполнить. В Примечании C она объясняет, что ткацкого способа подавать карты Аналитической машине мало: для неё придумали «отматывать» карты назад, проворачивая призму, на которой висит цепочка, в обратную сторону. Так одну и ту же группу карт можно пускать в дело «сколько угодно раз подряд». А в Примечании E Лавлейс даёт определение: «Под циклом операций следует понимать любую группу операций, которая повторяется больше одного раза».
У каждого цикла while три части, и полезно сразу научиться их видеть: условие, которое решает, крутиться ли дальше; работа, ради которой цикл написан; изменение, которое приближает конец. В нашем челноке изменение — строка throws = throws - 1. Уберите её и подумайте, что будет. Запускать пока не надо: что бывает с циклом без изменения, мы увидим в разделе о бесконечном цикле.
Сила while в том, что число повторов не обязательно знать заранее. Вернёмся к решётке из прошлой главы. Теперь замок спрашивает код, пока не услышит правильный, и после каждой ошибки подсказывает, как раньше:
Сколько раз выполнится тело этого цикла, не знает никто, кроме играющего: ноль раз, если код угадан с первой попытки, и сколько угодно, если игрок упрям. Цикл while нужен как раз тогда, когда повторять надо «до тех пор, пока», а не «столько-то раз». Кстати, если угадывать с умом и каждый раз делить оставшийся промежуток пополам, как в игре из главы 0, любой четырёхзначный код открывается не больше чем за 14 попыток.
Нить за нитью: for и range
Часто число повторов известно: обойти 24 нити основы, напечатать 10 строк, проверить числа от 1 до 1000. Для этого есть второй цикл, for:
Читается так: «для каждого throw из range(5) выполни тело». Счётчик заводить, увеличивать и проверять не нужно: for сам кладёт в переменную throw очередное значение и сам останавливается, когда значения кончились. Выглядит это скромно, но с for не сделать двух частых ошибок while: забыть изменить счётчик и ошибиться в условии.
Пять бросков в выводе пронумерованы от 0 до 4, а не от 1 до 5. Так устроен range: range(5) — это пять чисел, начиная с нуля. У него есть и полная форма, range(start, stop, step): от start шагами по step, пока не дойдём до stop. Сам stop в последовательность не входит никогда. Поиграйте с линейкой: красный кружок — граница, на которую цикл не наступает.
Границу не включают ради удобства, причём сразу в трёх смыслах. В range(n) ровно $n$ чисел. В range(a, b) их $b - a$, без всяких «плюс один». А соседние куски стыкуются без щелей и нахлёстов: range(0, 10) и range(10, 20) вместе дают range(0, 20), и число 10 попадает только во вторую половину. Математики называют такой отрезок полуинтервалом и пишут $[a, b)$. Платить за удобство приходится одной привычкой: когда нужно «от 1 до $n$ включительно», пишут range(1, n + 1). Забытое + 1 — одна из самых частых ошибок с циклами, и у неё есть имя: ошибка на единицу.
Цикл for умеет ходить не только по числам. Строка — тоже последовательность, и for проходит её по одному символу:
Новое здесь — end=" ". Обычно print после своего текста переводит строку, а end говорит, чем закончить вместо этого: здесь пробелом. Пустой print() в конце возвращает перевод строки. Этот приём понадобится нам, чтобы ткать узоры ряд за рядом, а откуда у print берутся такие настройки, станет ясно в следующей главе.
Копилка: накопители
По школьной легенде, маленький Карл Фридрих Гаусс за пару минут сложил все числа от 1 до 100, хотя учитель рассчитывал занять класс надолго. Гаусс догадался, как сложить их без перебора, — способ разобран в «Царице наук». Нам догадка не нужна: машине всё равно, сто слагаемых или миллион.
Запись total += k — сокращение для total = total + k: «прибавь к total число k». Переменная total здесь работает копилкой. Такие переменные называют накопителями, и рецепт у них всегда один:
- до цикла накопитель получает начальное значение: для суммы — ноль;
- в теле цикла он обновляется: к нему прибавляют очередное число;
- после цикла в нём лежит ответ.
Что напечатает программа, если строку total = 0 перенести внутрь цикла, перед total += k?
Каждый проход сначала обнуляет копилку, потом кладёт в неё одно число. После последнего прохода в ней лежит только последнее $k$, то есть 100. Накопитель, объявленный внутри цикла, забывает всё на каждой итерации — это одна из самых частых ошибок новичков.
Начальное значение зависит от того, что копим. Для произведения это единица, иначе всё умножится на ноль. Посчитаем, сколькими способами можно расставить на полке 25 разных книг: первую выбираем из 25, вторую из 24 и так далее, то есть $25 \cdot 24 \cdots 1 = 25!$.
Двадцать шесть цифр, и Python не потерял ни одной: целые числа у него бывают сколь угодно длинными. Счётчик — тоже накопитель, только прибавляет он единицу, и то лишь когда выполнено условие. Сколько чисел от 1 до 1000 делятся на 7?
Сто сорок два. Бывают накопители и для рекордов. Программа ниже читает числа, пока вы не введёте ноль, и запоминает наибольшее; здесь while и копилки работают вместе. Начальное значение рекорда — первое же число: заранее неизвестно, каких чисел ждать, и если все они окажутся отрицательными, ноль в роли рекорда соврал бы.
Ткань: цикл внутри цикла
Один ряд ткани — это цикл по нитям основы. Напечатаем ряд из 24 клеток, где пары закрашенных и пустых клеток идут по очереди:
Чтобы получить полотно, этот ряд нужно повторить. Повторять мы теперь умеем: обернём весь цикл по столбцам ещё одним циклом, по рядам. Это вложенный цикл: на каждую итерацию внешнего цикла внутренний пробегает все нити, от первой до последней. Совсем как в станке Жаккара: внешний цикл — цепочка карт, внутренний — иглы, каждая из которых проверяет свою дырку в карте. Станок, правда, проверяет все дырки разом, а Python — по очереди. Лавлейс в Примечании E называла такое «циклом, который включает в себя цикл, или циклом второго порядка».
Станок ниже работает так же, а узор в нём задаёт одно условие на номер ряда row и номер нити col. Нажмите «Ткать заново» и следите за подсветкой в программе: внутренний цикл обегает все нити ряда, и только потом внешний берёт следующую карту. Под тканью видна перфокарта текущего ряда.
#. показывает то же полотно так, как его напечатает Python. «Шаг» продвигает внутренний цикл на одну нить, «Ряд» — внешний на одну карту.Попробуйте сами: что будет, если в полосках заменить 4 на 3? Как получить горизонтальные полосы вместо вертикальных? Что нарисует row == col, а что — col % (row + 1) == 0? Любой узор здесь — это вопрос «закрашена ли клетка», заданный для каждой пары (ряд, нить). Кнопка под станком переносит программу в ячейку, где её выполнит уже сам Python:
Станок ткёт шахматку 12 на 24, условие (row + col) % 2 == 0. Сколько раз выполнится строка print("#", end="")?
Внутренний цикл проходит 12 × 24 = 288 раз — по разу на каждую клетку. Но print("#") стоит под if и срабатывает только там, где условие истинно, а в шахматке это ровно половина клеток: 144. Остальные 144 раза выполняется ветка else. Вложенные циклы перемножают число итераций, а условие внутри решает, какая из веток получит каждую.
Внутренний цикл не обязан каждый раз проходить одно и то же. Если его граница зависит от номера ряда, полотно получается не прямоугольным. Вот лесенка, где в ряду номер row стоит row клеток:
Та же техника работает и с цветными клетками вместо символов. В песочнице есть холст Canvas: команда rect рисует прямоугольник с левым верхним углом в точке $(x, y)$, причём ось $y$ на холсте смотрит вниз. Клетка в ряду row и столбце col начинается в точке (col * 20, row * 20). Поменяйте условие, цвета (есть p0…p11, ink, paper), добавьте третью ветку — и сотките свой ковёр.
Черепаха за станком
Узоры бывают не только на клетчатой сетке. В главе 0 черепаха нарисовала дерево. Её команды просты: turtle.forward(100) — пройти 100 шагов вперёд, оставляя след, turtle.left(90) — повернуться налево на 90 градусов. Квадрат — это четыре раза «вперёд и налево»:
Первая строка, import turtle, подключает модуль с черепахой — набор готовых команд, которых нет в самом языке. Поменяйте 4 на 6, а 90 на 60, и получится шестиугольник. Обойдя выпуклый многоугольник, черепаха в сумме поворачивается на один полный оборот, поэтому у правильного многоугольника с $n$ сторонами поворот равен $360 / n$ градусов.
Если угол не делит 360 нацело, после первого оборота черепаха в начало не вернётся. Она сделает второй оборот, третий… и замкнётся, только когда сумма поворотов станет кратна 360. Угол 144° даёт пятиконечную звезду: $5 \cdot 144 = 720$, два полных оборота. Угол 89° похож на прямой, но черепаха вернётся в начало лишь через 360 шагов. А если каждый раз удлинять шаг, фигура вообще не замкнётся.
forward и left, с ползунками вместо чисел. Рядом — та же программа на Python. Кнопка под ней отправляет программу в ячейку ниже, и там рисует черепаха на сервере.Вложенные циклы работают и у черепахи. Внутренний цикл рисует квадрат, внешний поворачивает черепаху на 10° и повторяет квадрат 36 раз — получается розетка:
Оборвать нить: break и continue
Иногда цикл нужно остановить посреди дороги: искомое найдено, дальше искать незачем. Для этого есть break — он немедленно выходит из цикла, не дожидаясь, пока кончится range или станет ложным условие. Найдём наименьший делитель числа 1001, больший единицы:
Цикл перебрал 2, 3, 4, 5, 6, на семёрке нашёл делитель и оборвался. Без break он напечатал бы и остальные делители — 11, 13, 77, 91, 143 и само 1001, ведь $1001 = 7 \cdot 11 \cdot 13$. Если бы наименьшим делителем оказалось само $n$, у числа не было бы других делителей, кроме единицы и себя, то есть оно было бы простым. Эта мысль пригодится в задачах.
Второй частый узор — бесконечный цикл с выходом из середины. Условием у такого цикла стоит True, «всегда», а выход один — break. Так удобно переспрашивать, пока ответ неверен: input пишется один раз, а не дважды, перед циклом и в нём, как в кодовом замке выше.
Так же устроены почти все игры: главный цикл читает команду игрока, меняет мир, рисует его и идёт на следующий круг, пока игрок не скажет «выход». Квест из прошлой главы теперь может жить сколько угодно, и из дома можно вернуться на дорогу:
Младший брат break — continue. Из цикла он не выходит: обрывает только текущую итерацию и сразу переходит к следующей. Например, напечатать числа от 1 до 20, пропуская кратные трём:
Одна тонкость. Во вложенных циклах break и continue действуют только на тот цикл, в теле которого стоят, то есть на самый внутренний. Внешний цикл продолжает работать как ни в чём не бывало.
Станок без остановки
Если условие while никогда не станет ложным, цикл будет крутиться вечно. Это называется бесконечным циклом. Запустите программу ниже без страха: песочница даёт каждой программе десять секунд, а потом останавливает её.
Переменная i пробегает 0, 3, 6, 9, 12, 15… и перепрыгивает через десятку. Условие i != 10 истинно всегда. Если заменить != на <, цикл остановится на двенадцати: проверка «меньше» не даёт перепрыгнуть финиш. Вот три самых частых причины бесконечного цикла, все они нарушают правило трёх частей из начала главы:
- изменения нет совсем — забыли
throws = throws - 1; - изменение идёт не в ту сторону —
+ 1вместо- 1; - изменение есть, но перепрыгивает через границу — как
i + 3мимо десятки.
Если такой цикл ещё и печатает, сервер остановит его раньше — по лимиту на объём вывода. На вашем собственном компьютере никто не придёт на помощь через десять секунд: программу останавливают сочетанием Ctrl+C, и Python отвечает трейсбеком KeyboardInterrupt.
Бывают и полезные бесконечные циклы. Сервер, который отдал вам эту страницу, крутится в цикле «дождаться запроса — ответить — дождаться следующего» с момента запуска и не должен останавливаться никогда. Операционная система вашего телефона тоже. Бесконечный цикл — ошибка, только если вы его не планировали.
Проверьте, насколько хорошо вы видите циклы глазами. Ниже одиннадцать коротких программ: для каждой предскажите, сколько раз выполнится отмеченная строка, а потом сверьтесь со счётчиком.
Коллатц своими руками
В главе 0 вы запускали программу про гипотезу Коллатца: если число чётное — делим пополам, если нечётное — умножаем на три и прибавляем единицу, пока не дойдём до единицы. Тогда программа была чёрным ящиком. Теперь соберём её сами, и в ней не будет ни одной непонятной строки: цикл while с условием «пока не единица», развилка if, накопитель-счётчик шагов и накопитель-рекорд высоты.
Сто одиннадцать шагов, вершина 9232, как и в главе 0. Обернём эту программу ещё одним циклом и пройдём все начальные числа от 1 до 10 000. Каждое даст точку на графике: по горизонтали — число, по вертикали — сколько шагов ему понадобилось. Квадратные скобки и append — это списки, о них глава 6; здесь они только собирают точки для графика.
Точки ложатся полосами и струями. Отчасти это понятно: пути разных чисел часто сливаются и дальше идут вместе (путь числа 97, например, на тринадцатом шаге приходит в 94 и с этого места повторяет путь числа 27), поэтому одинаковые длины встречаются целыми семействами. Интереснее другое — внутренний цикл. Для каждого из десяти тысяч чисел он остановился, иначе мы не увидели бы графика. Но остановится ли while n != 1 для любого начального числа, не знает никто: гипотеза Коллатца утверждает, что да, и до сих пор не доказана. Мы написали цикл, о котором неизвестно, бесконечный ли он. Можно ли хотя бы в принципе построить программу, которая смотрит на любой цикл и отвечает, остановится ли он? Ответ — в главе 56.
Задачи
Пять задач. Все они — целые программы: тесты запускают ваш код несколько раз с разным вводом и сравнивают то, что он напечатал, с ожидаемым. Лишние пробелы в конце строк не считаются ошибкой, а лишний текст считается — даже подсказка внутри input(): она тоже попадает в вывод, поэтому в заготовках её нет.
Программа читает число $n$ (от 1 до 20) и печатает таблицу умножения $n \times n$: в строке номер $i$ — произведения $i \cdot 1, i \cdot 2, \ldots, i \cdot n$ через пробел. Например, для $n = 3$:
1 2 3 2 4 6 3 6 9
Внешний цикл — по строкам: for i in range(1, n + 1). Почему n + 1, а не n?
Внутренний цикл печатает одну строку: print(i * j, end=" ") для каждого j. После него — пустой print(), чтобы перейти на новую строку.
Внешний цикл отвечает за строки, внутренний — за числа в строке. Если написать range(n) вместо range(1, n + 1), таблица начнётся со строки нулей и потеряет последнюю строку — классическая ошибка на единицу.
Программа читает неотрицательное целое число — возможно, очень длинное, в тысячу цифр — и печатает сумму его цифр. Для 1843 ответ 16, для 0 — 0.
Последняя цифра числа — остаток от деления на 10: n % 10. Отбросить её можно делением нацело: n // 10.
Повторяйте «прибавить последнюю цифру, отбросить последнюю цифру», пока число не станет нулём: while n > 0.
Можно и не превращать ввод в число: пройти строку циклом for и складывать int(digit) каждого символа. Сумма цифр числа $2^{1000}$ — 1366; проверьте любым способом. Эта копилка вернётся в следующей главе как второй инструмент.
Программа читает число $n$ и печатает в одну строку через пробел все простые числа от 2 до $n$ включительно. Простое число делится только на 1 и на себя; 1 простым не считается. Если простых нет, программа не печатает ничего. Для $n = 20$:
2 3 5 7 11 13 17 19
Для каждого k заведите «флажок» is_prime = True и переберите возможные делители d от 2. Нашёлся делитель — опустите флажок и выйдите из перебора через break.
Делители достаточно перебирать, пока d * d <= k: если у числа есть делитель больше корня, то в пару к нему есть и делитель меньше корня. При $n = 10\,000$ это ускоряет программу в десятки раз, а с ростом $n$ выигрыш растёт.
Переменная is_prime — накопитель особого рода, флажок: до перебора мы считаем число простым, а первый же делитель меняет мнение навсегда. Проверка одного числа заняла почти всю программу, и если простота понадобится ещё где-нибудь, этот кусок придётся копировать. С этой стены начнётся следующая глава. Ещё быстрее все простые до $n$ находит решето Эратосфена, оно в «Царице наук».
Программа читает число $n \ge 1$ и вышивает квадрат $n \times n$: символ # на обеих диагоналях, точка . во всех остальных клетках. Для $n = 5$:
#...# .#.#. ..#.. .#.#. #...#
Клетка лежит на главной диагонали (из левого верхнего угла в правый нижний), если row == col. Проверьте условие на станке выше.
Для второй диагонали проверьте углы: в первой строке (row = 0) закрашена последняя клетка, col = n - 1. Какая сумма row + col у всех клеток этой диагонали?
Подвох — в n - 1: номера идут с нуля, поэтому последняя клетка ряда имеет номер $n - 1$, а не $n$. При чётном $n$ диагонали проходят рядом и общей клетки у них нет — проверьте на $n = 4$.
Программа читает число $N \ge 1$, находит среди чисел от 1 до $N$ то, путь которого до единицы по правилу Коллатца самый длинный, и печатает через пробел это число и длину его пути в шагах. Если рекордсменов несколько, нужно наименьшее. Для $N = 10$ ответ 9 19. А какой рекордсмен среди первых десяти тысяч?
Нужны два накопителя-рекорда: best_steps и best_start. Внешний цикл — for start in range(1, N + 1), внутри — подсчёт шагов для n = start.
Чтобы при равенстве победило наименьшее число, обновляйте рекорд только при строгом неравенстве: if steps > best_steps. С >= рекорд будет переходить к большему из равных.
Среди чисел до 10 000 рекордсмен — 6171, ему нужен 261 шаг. До 20 побеждает 18 с двадцатью шагами, хотя у 19 их тоже двадцать: здесь и пригодилось строгое неравенство.
Куда дальше
В решении задачи про простые числа проверка одного числа заняла семь строк, и они намертво вросли в цикл по всем числам. Понадобится простота в другом месте (скажем, найти простые-близнецы или проверить ввод пользователя) — придётся скопировать эти семь строк, потом ещё раз, потом найти в одной из копий ошибку и чинить её во всех. Циклы избавили нас от повторов во времени, но код всё равно разрастается в стену одинаковых кусков. Нужен способ дать куску работы имя и звать его по имени. Инженеры первых компьютеров упёрлись в эту стену сразу, а в 1949 году в Кембридже подпрограммы стали обычным инструментом. Об этом — глава 5.