Числа в цикле Python: суммы, факториалы, Фибоначчи

Три числовые задачи — сумма ряда, факториал и числа Фибоначчи — проходят в каждом учебнике и на каждом собеседовании. Все три решаются одним приёмом. Переменная-накопитель стартует с нейтрального значения, а цикл шаг за шагом вносит в неё вклад. Разница между суммой и произведением — только в стартовом значении и операции; Фибоначчи добавляет к каркасу вторую переменную и одновременное присваивание.

Сумма первых n: цикл против формулы

Сумма чисел от одного до n — первая задача, на которой становится видна разница между «посчитать циклом» и «вычислить формулой». Формула есть: n умножить на n плюс один, пополам. Цикл тоже работает — и медленнее, зато его видно.

n = 10

total = 0
for i in range(1, n + 1):
    total += i
print(total)

55

Пятьдесят пять — так и должно быть. Встроенная sum делает то же самое одной строкой: sum(range(1, 11)). Цикл полезен не скоростью, а тем, что в нём видно каждый шаг: именно поэтому его и просят на собеседованиях. А формулу стоит помнить отдельно — на больших n (миллион) она даёт ответ мгновенно, а цикл будет считать миллион сложений.

Короткие записи из модуля math стоит знать, но это другой навык: они скрывают сам алгоритм. Учебная задача на циклах решается циклом, рабочая задача в программе — встроенной функцией. Одно исключение — когда цикл учит чему-то ещё: попутно считает, фильтрует, ищет.

Возведение в степень

Ещё одна задача на произведение — степень числа. Обычный цикл умножает base на себя нужное число раз, и для небольших показателей этого достаточно.

base = 2
exp = 5

result = 1
for _ in range(exp):
    result *= base
print(result)

32

Два в пятой — 32, всё сошлось. Подчёркивание в заголовке цикла читается «важно количество шагов, а не значение счётчика» — так принято помечать переменную, которую тело не использует. На малых показателях этот цикл проигрывает встроенному 2 ** 5 в разы, и правильно — он здесь не про скорость, а про устройство накопления.

Но у задачи есть версия, где цикл действительно выигрывает: двоичное возведение в степень. Идея та же — накопитель и цикл, — но за половину шагов.

def power(base, exp):
    result = 1
    while exp > 0:
        if exp % 2 == 1:
            result *= base
        base *= base
        exp //= 2
    return result

print(power(2, 10))

1024

Две в десятой — 1024, то же самое, что и 2 ** 10. Но шагов было не десять, а четыре: показатель делится пополам на каждом шаге, а основание возводится в квадрат. На больших показателях разница становится огромной — для тысячи шагов превращаются в десять. Это уже высшая математика, но каркас тот же: накопитель result, изменяемая переменная exp и условие выхода.

Алгоритм Евклида: НОД циклом

Задача посложнее: найти наибольший общий делитель двух чисел. Перебор делителей перебирать не нужно — достаточно одного цикла и присваивания в две переменные.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

print(gcd(48, 18))

6

Работает алгоритм Евклида: пока b не ноль, меняем пару местами и берём остаток от деления a на b. Остаток всегда меньше делителя, значит, числа убывают, и цикл обязательно дойдёт до нуля. Шесть — наибольшее число, на которое делятся и 48, и 18. Обратите внимание на while b: ноль считается ложным, поэтому условие в этой форме проверяет «b ещё не ноль».

Разбор числа на цифры

Классическая задача на два оператора: получить сумму цифр числа. Работают вместе остаток от деления и целочисленное деление — урок про FizzBuzz разбирает их подробнее.

n = 493

total = 0
while n > 0:
    total += n % 10
    n = n // 10
print(total)

16

Остаток от деления на десять отдаёт последнюю цифру, целочисленное деление отбрасывает её. Число 493 отдаёт по цифре за шаг: 3, 9, 4 — и накопитель собирает шестнадцать. Цикл останавливается, когда число стало нулём, а не по счётчику шагов: длина числа заранее неизвестна.

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

Сумма и произведение: одна схема

Начнём с пары, где виден каркас целиком: сложение и умножение всех элементов списка.

numbers = [2, 5, 3, 8]

total = 0
for n in numbers:
    total += n
print(total)

product = 1
for n in numbers:
    product *= n
print(product)

18
240

Сумма стартует с нуля: ноль — нейтральный элемент сложения, прибавление его ничего не меняет. Произведение стартует с единицы — нейтрального элемента умножения. Ошибочный старт ломает всё: произведение, начатое с нуля, навсегда останется нулём, а сумма, начатая с единицы, будет завышена. Выбор стартового значения — половина решения задачи на накопление; сам каркас разобран в уроке про счётчики и аккумуляторы.

numbers = [3, 8, 5, 6, 7]

total = 0
for n in numbers:
    if n % 2 == 0:
        total += n
print(total)

14

Условие внутри цикла отбирает вкладчиков: в сумму попали только чётные, восемь и шесть. Это мостик к генераторам списков: то же самое одной строкой делает sum(n for n in numbers if n % 2 == 0) — пока что держите в голове ручной каркас, он честнее для понимания.

Факториал: произведение до n

Факториал числа n — произведение всех чисел от единицы до n: пять факториал — это 1 × 2 × 3 × 4 × 5. Это тот же аккумулятор произведения, только данные берутся не из списка, а из range:

for n in [0, 1, 2, 5, 10]:
    fact = 1
    for i in range(2, n + 1):
        fact *= i
    print(n, '->', fact)

0 -> 1
1 -> 1
2 -> 2
5 -> 120
10 -> 3628800

range(2, n + 1) перебирает от двойки до n включительно: единица на произведение не влияет, поэтому стартовать можно прямо с неё, а правая граница range не входит в перебор — нужен n + 1. Забытый плюс-один — классическая ошибка: range(2, 5) остановится на четвёрке, и пять факториал занизится до двадцати четырёх. Краевые случаи прошли сами собой: при n равном нулю или единице цикл не делает ни шага, аккумулятор остаётся единицей — так и должно быть, ноль факториал равен единице. Хорошая схема накопления съедает краевые случаи бесплатно.

Фибоначчи: два предыдущих числа

Числа Фибоначчи — ряд, где каждое следующее число равно сумме двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13. Хранить весь ряд не нужно: достаточно окна из двух последних чисел.

how_many = 8

a, b = 0, 1
row = []
for _ in range(how_many):
    row.append(a)
    a, b = b, a + b
print(row)

[0, 1, 1, 2, 3, 5, 8, 13]

Пара a, b — окно из двух последних чисел ряда: на каждом шаге в список уезжает a, а окно сдвигается. Строка a, b = b, a + b — одновременное присваивание: правая часть целиком вычисляется со старыми значениями, и только потом пара записывается в переменные. Подчёркивание в for _ in range(how_many) читается «важно количество шагов, а не значения счётчика» — так принято помечать счётчик, который тело цикла не использует.

a, b = 0, 1

a = b
b = a + b
print('по очереди:', a, b)

a, b = 0, 1
a, b = b, a + b
print('одновременно:', a, b)

по очереди: 1 2
одновременно: 1 1

По очереди не работает: к моменту вычисления a + b переменная a уже стала единицей, и пара уехала на шаг вперёд — вместо нового окна 1 и 1 получились 1 и 2. Одновременное присваивание решает именно эту проблему: старые значения живут до конца вычисления правой части. Приём — тот же, что в распаковке пар в enumerate и zip: справа собирается пара, слева разбирается по переменным.

limit = 50

a, b = 0, 1
row = []
while a < limit:
    row.append(a)
    a, b = b, a + b
print(row)

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

while отвечает на другой вопрос: не «сколько чисел», а «пока число меньше лимита». Пара та же, но вместо счётчика шагов — условие выхода: после тридцати четырёх окно переехало на пятьдесят пять, проверка провалилась, цикл кончился. Связка накопления с while пригодится, когда граница задана значением, а не количеством; while разбирался в своём уроке.

Границы чисел не проблема

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

fact = 1
for i in range(2, 101):
    fact *= i

print(fact)
print(len(str(fact)))

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
158

Сто пятьдесят восемь цифр — и ни одной ошибки: целые числа Python ограничены только памятью компьютера. Пока накопление остаётся целым, оно точное: никаких округлений и хвостов, как бывает с числами с плавающей точкой. Поэтому факториал, суммы и Фибоначчи на Python считают без всяких библиотек больших чисел.

total = sum(n for n in numbers if n % 2 == 0)   # сумма чётных одной строкой