Вычисление чисел Фибоначчи
💻 Информатика · 8 класс
Что такое числа Фибоначчи
Числа Фибоначчи — это последовательность, в которой каждое следующее число равно сумме двух предыдущих. Первые два числа равны 0 и 1 (в некоторых учебниках — 1 и 1). Дальше идут 0, 1, 1, 2, 3, 5, 8, 13, 21, .... Эта последовательность часто встречается в задачах и в природе — например, в расположении лепестков цветка и семян в подсолнухе.
Вычисление чисел Фибоначчи — наглядная задача на работу с несколькими переменными и их одновременное изменение. Она показывает, как хранить только нужные данные, не запоминая всю последовательность целиком.
Правило построения
Чтобы получить очередной член, складывают два предыдущих: F_n = F_(n-1) + F_(n-2). Поэтому для вычисления достаточно помнить только два последних числа. Их хранят в двух переменных-накопителях и на каждом шаге сдвигают: текущее число становится предыдущим, а вычисленная сумма — текущим.
Правило. Хранить всю последовательность не нужно — достаточно двух переменных для двух последних чисел. Это экономит память и упрощает программу.
Разобранный пример
# Питон, первые n чисел Фибоначчи
n = 7
a = 0 # предыдущее число
b = 1 # текущее число
for i in range(n):
print(a)
a, b = b, a + b # сдвигаем пару значенийСтрока a, b = b, a + b одновременно переносит значение и вычисляет новую сумму, не теряя при этом данных. Сначала вычисляется правая часть, и только потом её значения попадают в переменные. Без такого приёма пришлось бы заводить дополнительную временную переменную.
Как меняются переменные
Проследим значения переменных на нескольких шагах цикла. В переменной a каждый раз находится очередное выводимое число.
| Шаг | a (выводится) | b |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 1 | 1 |
| 3 | 1 | 2 |
| 4 | 2 | 3 |
| 5 | 3 | 5 |
Несколько членов последовательности
| Номер | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Значение | 0 | 1 | 1 | 2 | 3 | 5 | 8 |
Способ через временную переменную
Если язык не поддерживает одновременное присваивание, тот же сдвиг выполняют в три действия с помощью временной переменной.
vsp = a + b # сохраняем сумму
a = b # текущее становится предыдущим
b = vsp # сумма становится текущимГде встречается последовательность
Числа Фибоначчи интересны не только как учебная задача. Их находят в строении растений: число лепестков у многих цветов и расположение семян в соцветиях подчиняются этой последовательности. Отношение соседних чисел Фибоначчи с ростом номера приближается к так называемому золотому сечению — пропорции, которую художники и архитекторы считают особенно гармоничной.
Частая ошибка. При сдвиге значений без одновременного присваивания старое a теряется, если сначала записать в него новое значение. Используйте парное присваивание или временную переменную.
Кратко о главном
- Каждое число Фибоначчи равно сумме двух предыдущих.
- Начинается последовательность с
0и1. - Для вычисления хватает двух переменных-накопителей.
- На каждом шаге пара значений сдвигается одновременным присваиванием.
- Без парного присваивания нужна временная переменная.