Урок №17. Циклы с условием. Циклы по переменной.
Цикл — это многократное выполнение одинаковых действий. Любой алгоритм может быть записан с помощью трёх алгоритмических конструкций: последовательного выполнения команд (линейных участков алгоритмов), условных операторов и циклов.
Для того чтобы организовать цикл с заданным числом повторений, необходимо использовать ячейку памяти, в которой будет запоминаться количество выполненных шагов цикла (счётчик шагов). Можно сначала записать в неё ноль (ни одного шага не сделано), а после каждого шага цикла увеличивать значение счётчика на единицу. На псевдокоде (смеси естественного языка и какого-нибудь языка программирования) алгоритм можно записать так (здесь и далее операции, входящие в тело цикла, выделяются отступами):
счётчик = О
пока счётчик != 10
print ("Привет!")
увеличить счётчик на 1
Возможен и другой вариант: сразу записать в счётчик нужное количество шагов и после каждого шага цикла уменьшать счётчик на 1. Тогда цикл должен закончиться при нулевом значении счётчика:
счётчик = 10
пока счётчик > 0
print("Привет!")
уменьшить счётчик на 1
Этот вариант несколько лучше, чем предыдущий, поскольку счётчик сравнивается с нулём, а такое сравнение выполняется в процессоре автоматически (см. главу 4).
В этих примерах мы использовали цикл с условием, который выполняется до тех пор, пока некоторое условие не станет ложным.
Рассмотрим следующую задачу: определить количество цифр в десятичной записи целого положительного числа. Будем предполагать, что исходное число записано в переменной п целого типа.
Сначала нужно разработать алгоритм решения задачи. Для подсчёта количества цифр нужно как-то отсекать эти цифры по одной, с начала или с конца, каждый раз увеличивая счётчик. Начальное значение счётчика должно быть равно нулю, так как до выполнения алгоритма ещё не найдено ни одной цифры.
Для отсечения первой слева цифры необходимо заранее знать, сколько цифр в десятичной записи числа, т. е. нужно заранее решить ту задачу, которую мы решаем. Следовательно, этот метод не подходит.
Отсечь последнюю цифру проще — достаточно разделить число нацело на 10 (поскольку речь идёт о десятичной системе). Операции отсечения и увеличения счётчика нужно выполнять столько раз, сколько цифр в числе. Как же «поймать» момент, когда цифры кончатся? Несложно понять, что в этом случае результат очередного деления на 10 будет равен нулю, это и говорит о том, что отброшена последняя оставшаяся цифра. Изменение переменной п и счётчика для начального значения 1234 можно записать в виде таблицы:
Запишем алгоритм на псевдокоде:
счётчик = 0
пока n > 0
отсечь последнюю цифру числа n
увеличить счётчик на 1
Соответствующая программа на Python выглядит так:
count = О
while n > 0:
n = n // 10
count += 1
Слово while переводится как «пока», т. е. цикл выполняется, пока n > 0. После условия, как и в конце заголовка условного оператора if, ставится двоеточие. Переменная-счётчик имеет имя count.
Обратите внимание, что проверка условия выполняется в начале очередного шага цикла. Такой цикл называется циклом с предусловием (т. е. с предварительной проверкой условия) или циклом «пока». Если в начальный момент значение переменной п будет нулевое или отрицательное, цикл не выполнится ни одного раза.
В данном случае количество шагов цикла «пока» неизвестно, оно равно количеству цифр введённого числа, т. е. зависит от исходных данных. Кроме того, этот же цикл может быть использован и в том случае, когда число шагов известно заранее или может быть вычислено:
к = 0
while к < 10:
print("Привет")
к += 1
Если условие в заголовке цикла никогда не нарушится, цикл будет работать бесконечно долго. В этом случае говорят, что «программа зациклилась». Например, если забыть увеличить переменную к в предыдущем цикле, программа зациклится:
к = 0
while к < 10:
print("Привет")
Вернёмся снова к задаче, которую мы обсуждали в предыдущем параграфе, — вывести на экран 10 раз слово «Привет!». Фактически нам нужно организовать цикл, в котором блок операторов выполнится заданное число раз (в некоторых языках такой цикл есть, например, в школьном алгоритмическом языке он называется «цикл N раз»). На языке Python подобный цикл записывается так:
for i in range(10):
print("Привет!")
Здесь слово for означает «для», переменная i (её называют переменной цикла) изменяется в диапазоне (in range) от 0 до 10, не включая 10 (т. е. от 0 до 9 включительно). Таким образом, цикл выполняется ровно 10 раз. Заметьте, что в конце заголовка цикла ставится двоеточие.
В информатике важную роль играют степени числа 2 (2, 4, 8, 16 и т. д.) Чтобы вывести все степени двойки от 21 до 210, мы уже можем написать такую программу с циклом «пока»:
k = 1
while к <= 10 :
print(2**к)
к += 1
Вы наверняка заметили, что переменная к используется трижды (см. выделенные блоки): в операторе присваивания начального значения, в условии цикла и в теле цикла (увеличение на 1). Цикл с переменной «собирает» все действия с ней в один оператор:
for k in range(1,11):
print(2**к)
Здесь диапазон (range) задаётся двумя числами — начальным и конечным значениями, причём указанное конечное значение не входит в диапазон. Такова особенность функции range в Python.
Шаг изменения переменной цикла по умолчанию равен 1. Если его нужно изменить, указывают третье (необязательное) число в скобках после слова range — нужный шаг. Например, такой цикл выведет только нечётные степени числа 2 (21, 23 и т. д.):
for k in range (1,11,2):
print (2**к)
С каждым шагом цикла переменная цикла может не только увеличиваться, но и уменьшаться. Для этого начальное значение должно быть больше конечного, а шаг — отрицательный. Следующая программа выводит квадраты натуральных чисел от 10 до 1 в порядке убывания:
for k in range (10,0,-1):
print(к**2)
В более сложных задачах часто бывает так, что на каждом шаге цикла нужно выполнять обработку данных, которая также представляет собой циклический алгоритм. В этом случае получается конструкция «цикл в цикле» или «вложенный цикл».
Предположим, что нужно найти все простые числа в интервале от 2 до 1000. Простейший (но не самый быстрый) алгоритм решения такой задачи на псевдокоде выглядит так:
for n in range (2,1001):
if число n простое:
print(n)
Как же определить, что число простое? Как известно, простое число делится только на 1 и само на себя. Если число п не имеет делителей в диапазоне от 2 до n — 1, то оно простое, а если хотя бы один делитель в этом интервале найден, то составное.
Чтобы проверить делимость числа n на некоторое число k, нужно получить остаток от деления n на k. Если этот остаток равен нулю, то n делится на k. Таким образом, программу можно записать так (здесь n, k и count — целочисленные переменные, count обозначает счётчик делителей):
for n in range (2,1001) :
count = 0
for k in range (2,n):
if n % k == 0:
count += 1
if count == 0:
print (n)
Попробуем немного ускорить работу программы. Делители числа обязательно идут в парах, причём в любой паре меньший из делителей не превосходит √n (иначе получается, что произведение двух делителей, каждый из которых больше √n, будет больше, чем n). Поэтому внутренний цикл можно выполнять только до значения √n вместо n — 1. Для того чтобы работать только с целыми числами (и таким образом избежать вычислительных ошибок), лучше заменить условие k ≤ √n на равносильное ему условие k2 ≤ n. При этом потребуется перейти к внутреннему циклу с условием:
count = О
к = 2
while к*к <= n:
if n % к == 0:
count += 1
к += 1
Чтобы ещё ускорить работу цикла, заметим, что, когда найден хотя бы один делитель, число уже заведомо составное, и искать другие делители в данной задаче не требуется. Поэтому можно закончить цикл. Для этого при n%k == 0 выполним досрочный выход из цикла с помощью оператора break (оператор break во вложенном цикле прерывает только внутренний цикл, а внешний продолжает работать), причём переменная count уже не нужна:
к = 2
while к*к <= п:
if п % к == 0:
break
к += 1
if к*к > n:
print(n)
Если после завершения цикла k*k > n (нарушено условие в заголовке цикла), то число п простое.
В любом вложенном цикле переменная внутреннего цикла изменяется быстрее, чем переменная внешнего цикла. Рассмотрим, например, такой вложенный цикл:
for i in range(1,5):
for k in range (1, i + 1) :
print (i, k)
На первом шаге (при i = 1) переменная k принимает единственное значение 1. Далее, при i = 2 переменная к принимает последовательно значения 1 и 2. На следующем шаге при i = 3 переменная к проходит значения 1, 2 и 3, и т. д.
Древнегреческий математик Евклид, живший в III веке до нашей эры, придумал замечательный алгоритм для вычисления наибольшего общего делителя (НОД) двух натуральных чисел. Этот алгоритм и сейчас используется, например, в задачах шифрования. Напомним, что НОД — это наибольшее число, на которое два заданных числа делятся без остатка.
Алгоритм Евклида для натуральных чисел: заменять большее из двух заданных чисел на их разность до тех пор, пока числа не станут равны. Полученное число и есть их НОД.
Алгоритм Евклида можно записать на языке Python так:
while a != b:
if a > b:
a = a - b
else:
b = b - a
print (a)
Этот вариант алгоритма работает довольно медленно, если одно из чисел значительно меньше другого, например для пары чисел 2 и 2014. Значительно быстрее выполняется улучшенный (модифицированный) алгоритм Евклида.
Модифицированный алгоритм Евклида для натуральных чисел: заменять большее из двух заданных чисел на остаток от деления большего на меньшее, пока этот остаток не станет равным нулю. Тогда второе число и есть их НОД.
Фрагмент программы на языке Python запишется так:
while а != 0 and b != 0:
if а > Ь:
а = а % b
else:
b = b % а
print(а + Ь)
Почему в конце выводится на экран сумма а + b? Дело в том, что цикл остановится тогда, когда одно из чисел будет равно нулю, тогда второе и есть их НОД. Но так как первое число равно нулю, сумма а + b равна второму числу.
Возможна и ещё более короткая запись:
while Ь:
a, b = b, а % b
print(а)
Здесь запись while b означает то же самое, что и while b != 0. На каждом шаге цикла значения переменных меняются местами так, чтобы в переменной а оказалось большее из двух чисел. Цикл заканчивается, когда после очередного шага значение переменной b станет равно нулю, тогда в переменной а остаётся последний ненулевой остаток, это и есть НОД исходных чисел.