Материалы по курсу «Основы программирования»

Цикл while

Синтаксис цикла while выглядит так:

while ‹условие›:
    ‹тело цикла›

• ‹условие› — логическое выражение, т.е. выражение, которое может быть истинным или ложным.
• ‹тело цикла› — последовательность операторов с отступом

Если тело цикла состоит из одного оператора, то цикл, также как и if, можно записать в одну строчку:

while ‹условие›: ‹тело цикла›

Но так лучше не писать из стилистических соображений.

Как он выполняется:

• Вычисляется значение выражения ‹условие›.
• Если условие ложное, цикл прерывается, ‹тело цикла› ни разу не выполняется.
• Если условие истинноое, выполняется ‹тело цикла›.
• И потом снова вычисляется ‹условие›.
• Если оно ложное — цикл прерывается, если истинное, снова выполняется ‹тело цикла›.
• И так далее.

Т.е. пока значение ‹условия› истинное, поочерёдно вычисляется ‹условие› и выполняется тело цикла.

Сравним с if:

if ‹условие›:
    ‹блок›

Блок либо выполнится, либо не выполнится.

while ‹условие›:
    ‹блок›

Блок может выполняться много раз.

Итерация — однократное выполнение тела цикла.

Пример. Просуммировать все числа от 1 до 100.

sum = 0
i = 1
while i <= 100:
    sum = sum + i
    i = i + 1

В переменной i находится очередное число. В начале оно равно 1, затем на каждой итерации (проходе, витке) цикла оно увеличивается на 1. В результате на первом витке i равно 1, на втором — i равно 2 и т.д. Таким образом, в переменной i на входе в цикл находится номер текущей итерации.

Переменная sum изначально равна нулю, на каждом витке цикла её содержимое увеличивается на номер этой итерации цикла (значение переменной i). В итоге, значение переменной sum после завершения цикла увеличится на сумму чисел от 1 до 100. Начальным её значением было число 0, поэтому после завершения цикла в ней будет сумма чисел от 0 до 100.

Этот цикл обязательно завершится, т.к. до начала цикла переменная i хранила значение меньше 100, на каждом проходе цикла переменная i увеличивается и поэтому рано или поздно превысит 100 — условие i <= 100 станет ложным и цикл прервётся.

Этот пример можно записать компактнее:

sum = 0
i = 1
while i <= 100:
    sum += i
    i += 1

Здесь мы использовали сокращённую запись операторов присваивания. Вспомним, что запись вида

‹перем›  ‹знак›=   ‹выраж›

является сокращением для

‹перем› = ‹перем›  ‹знак›  ‹выраж›

Вернёмся к циклу while. Для цикла вида

while ‹условие›:
    ‹тело цикла›

если в теле цикла нет явных конструкций прерывания цикла (break, return), можно быть уверенным, что после завершения цикла ‹условие› будет ложным.

А внутри самого цикла ‹условие› истинное.

Пример. Написать функцию is_prime(n), проверяющую число на простоту.

def is_prime(n):
    ‹проверить число на простоту›

Число простое, если оно больше чем 2 и делится только на себя и на единицу. Число делится на другое, если остаток от деления равен нулю.

def is_prime(n):
    ‹перебирать все числа от 2 до бесконечности,
     пока не найдётся делитель›
    ‹сравнить делитель с n›

Считаем, что n у нас не меньше 2. Среди чисел от 2 до бесконечности рано или поздно найдётся делитель числа n — для составного числа это будет один из делителей n, для простого — само n.

def is_prime(n):
    divisor = 2
    while ‹n не делится на divisor›:
        ‹увеличить divisor на 1›

    return divisor == n

Уточняем дальше:

def is_prime(n):
    divisor = 2
    while n % divisor != 0:
        divisor += 1

    return divisor == n

Данная функция зациклится, если n будет отрицательным, нулём или единицей. Она определена только для n >= 2.

Функцию можно оптимизировать, перебирая делители не до бесконечности (фактически, до n), а до √n:

def is_prime(n):
    divisor = 2
    while (divisor <= n**0.5) and (n % divisor != 0):
        divisor += 1

    return ‹а что тут написать?›

Цикл продолжается, пока divisor <= √n и при этом n не делится на divisor без остатка. Соответственно, чтобы цикл прекратился, должно нарушится хотя бы одно из условий:

• divisor > √n,
• n делится на divisor без остатка.

Признаком того, что число простое, является первое условие — очередной кандидат в делители превысил √n.

def is_prime(n):
    divisor = 2
    while (divisor <= n**0.5) and (n % divisor != 0):
        divisor += 1

    return divisor > n**0.5

Пример. Найти сумму цифр целого числа.

Нам нужно разбить число на отдельные цифры и их сложить. Разбивать число будем справа налево: последняя цифра числа — это его остаток от деления на 10, все цифры, кроме последней — результат целочисленного деления на 10.

Целочисленное деление в Python — это операция //, возвращает целую часть частного:

>>> 30 / 4
7.5
>>> 36 / 4
9.0
>>> 30 // 4
7
>>> 36 // 4
9

Назовём функцию sum_digits(n):

def sum_digits(n):
    ‹найти сумму цифр›

Для хранения суммы заведём переменную-аккумулятор sum, которую на каждой итерации будем увеличивать на величину очередной цифры. До цикла положим в неё 0, после завершения цикла в ней будет находиться сумма цифр.

def sum_digits(n):
    sum = 0
    while ‹цифры не кончились›:
        ‹найти очередную (последнюю) цифру›
        ‹увеличить sum на очередную цифру›
        ‹отбросить последнюю цифру числа›
    return sum

Уточняем:

def sum_digits(n):
    sum = 0
    while n != 0:
        last_digit = n % 10
        sum += last_digit
        n //= 10
    return sum

В предпоследней строке мы воспользовались сокращённой записью для n = n // 10.

Приёмы использования цикла while

Перебор всех значений

Решаемая задача. Есть некоторая последовательность значений, нужно перебрать их все и с каждым значением что-нибудь сделать.

Шаблон решения:

‹установка на начало›
while ‹значения не кончились›:
    ‹сделать что-то с текущим значением›
    ‹перейти к следующему›

Под этот шаблон хорошо подходит предыдущий пример — суммирование цифр числа:

def sum_digits(n):
    sum = 0
    while n != 0:
        last_digit = n % 10
        sum += last_digit
        n //= 10
    return sum

• Здесь ‹установки на начало› нет, т.к. в переменной n уже лежит исходное число.
• ‹значения не кончились› — условие n != 0 — цифры в числе не кончились.
• ‹сделать что-то с текущим› — две первые строчки тела цикла:

  last_digit = n % 10
  sum += last_digit
  

• ‹перейти к следующему› — n //= 10 — отбрасывание последней цифры.

Другой пример с сегодняшней лекции:

sum = 0
i = 1
while i <= 100:
    sum += i
    i += 1

• ‹установка на начало› — i = 1,
• ‹значения не кончились› — i <= 100,
• ‹сделать что-то с текущим› — sum += i — увеличение суммы на номер витка,
• ‹перейти к следующему› — i += 1.

Поиск значения при помощи цикла while

Решаемая задача. Есть множество каких-то значений, нужно среди них найти первое, которое удовлетворяет заданным свойствам, в частности, равно чему-либо.

Шаблон решения.

‹установка на первое значение›
while ‹значения не кончились› and ‹текущее — не искомое›:
    ‹переходим к следующему›

if ‹значения кончились›:
    ‹сделать что-то, когда искомого значения нет›
else:
    ‹текущее значение — искомое, сделать что-то с ним›

Пример. Ранее мы рассматривали пример на определение простоты числа. Рассмотрим его ещё раз, но уже с точки зрения приёма поиска при помощи цикла while.

Если число составное, то у него найдутся два делителя: m = n × k, при этом либо n == k, т.е. m = n² = k², либо один из делителей будет меньше √n, а второй — больше, чем √n.

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

def is_prime(n):
    ‹установка на начало›
    while ‹не достигли конца› and ‹не нашли›:
        ‹перейти к следующему›

    if ‹достигли конца›:
        ‹сделать что-то, когда не нашли›
    else:
        ‹сделать что-то, когда нашли›

Немного уточним фразы в псевдокоде:

def is_prime(n):
    ‹установка на первый кандидат в делители›
    while ‹кандидат в делители не больше √n› and ‹это не делитель›:
        ‹перейти к следующему›

    if ‹кандидат в делители больше √n›:
        ‹сделать что-то, когда не нашли›
    else:
        ‹сделать что-то, когда нашли›

Можем уточнить две последние фразы: если делитель найден, число составное, функция возвращает ложь. Если не найден — простое, функция возвращает истину:

def is_prime(n):
    ‹установка на первый кандидат в делители›
    while ‹кандидат в делители не больше √n› and ‹это не делитель›:
        ‹перейти к следующему›

    if ‹кандидат в делители больше √n›:
        return True
    else:
        return False

Кандидата в делители положим в переменную divisor и перепишем на Python ещё несколько фраз в псевдокоде:

def is_prime(n):
    divisor = 2
    while divisor <= n**0.5 and n % divisor != 0:
        divisor += 1

    if divisor > n**0.5:
        return True
    else:
        return False

Получили готовую работающую функцию. Но её можно упростить.

Как мы знаем, конструкцию вида

if ‹условие›:
    return True
else:
    return False

можно упростить до

return ‹условие›

В рассматриваемой функции мы видим похожую конструкцию:

    if divisor > n**0.5:
        return True
    else:
        return False

Теперь мы можем упростить его до одной строчки:

    return divisor > n**0.5

Целиком функция примет вид:

def is_prime(n):
    divisor = 2
    while divisor <= n**0.5 and n % divisor != 0:
        divisor += 1

    return divisor > n**0.5

Пример. Найти наибольший общий делитель. Мы будем рассматривать поиск наибольшего общего делителя именно как задачу поиска, т.е. без алгоритма Евклида.

def gcd(m, n):
    ‹найти НОД›

Делитель числа не превышает модуль (абсолютное значение) этого числа.

Чтобы найти общий делитель, нужно перебирать числа и искать среди них число, на которое делятся два исходных без остатка. Чтобы общий делитель был наибольшим, нужно перебирать числа в порядке убывания.

Поэтому в качестве начального кандидата в делители мы можем взять абсолютное значение одного из двух аргументов.

def gcd(m, n):
    ‹установка на начало›
    while ‹не достигли конца› and ‹текущее — не искомое›:
        ‹перейти к следующему›

    if ‹достигли конца›:
        ‹случай, когда НЕ нашлось›
    else:
        ‹случай, когда нашлось›

Кандидат в делители будем хранить в переменной res. Перебирать числа будем в порядке убывания, начнём с абсолютного значения m. На самом деле, можно и с n, можно выбрать из них наименьшее, но это нам не важно, нам важно рассмотреть поиск.

• ‹установка на начало — res = abs(m)
• ‹не достигли конца› — res > 0
• ‹текущее — не искомое› — НЕ общий делитель. Общий делитель — делится на оба числа без остатка. Т.е. НЕ общий делитель — not (m % res == 0 and n % res == 0).
• ‹перейти к следующему› — res -= 1, т.к. перебираем по убыванию.

Вернёмся к коду:

def gcd(m, n):
    res = abs(m)
    while res > 0 and not (m % res == 0 and n % res == 0):
        res -= 1

    if ‹достигли конца›:
        ‹случай, когда НЕ нашлось›
    else:
        ‹случай, когда нашлось›

Вопрос. А может ли res быть равным нулю? Отрицательным быть не может, т.к. это абсолютное значение числа (res = abs(m)). Нулём может, только когда m сам равен нулю. Но если одно из чисел равно нулю, то наибольший общий делитель — второе число.

В остальных случаях res не будет равен нулю, т.к. искомый элемент (общий делитель) обязательно найдётся — в худшем случае это будет 1.

Поэтому, в случае, когда делителя не нашлось (m == 0), возвращаем n, а в остальных случаях — найденный общий делитель:

def gcd(m, n):
    res = abs(m)
    while res > 0 and not (m % res == 0 and n % res == 0):
        res -= 1

    if res == 0:
        return n
    else:
        return res

Примечание. Часто для результата функции заводят переменную с именем res.