Задачи / Числа / Числа Фибоначчи

Числа Фибоначчи: блок-схема и алгоритм

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

Алгоритм по шагам

Ввести n.
Присвоить a = 0, b = 1.
n раз: c = a + b, a = b, b = c.
Вывести a — это n-е число (F0 = 0).

Открыть блок-схему в редакторе

Пример работы

Вход	n = 7
Шаг 1	(a, b) = (0, 1)
Шаг 2	→ (1, 1) → (1, 2) → (2, 3) → (3, 5) → (5, 8) → (8, 13) → (13, 21)
Результат	13

Решение на Python

n = int(input())
a, b = 0, 1
for _ in range(n):
    a, b = b, a + b
print(a)

Решение на Pascal

var n, i: integer;
    a, b, c: int64;
begin
  readln(n);
  a := 0; b := 1;
  for i := 1 to n do
  begin
    c := a + b;
    a := b;
    b := c;
  end;
  writeln(a);
end.

Код блок-схемы

Схема выше нарисована по этому псевдокоду. Скопируйте его в редактор блок-схем или нажмите «Открыть блок-схему в редакторе».

блок-схема: n-е число Фибоначчи
начало
ввод n
a = 0
b = 1
для i от 1 до n
    c = a + b
    a = b
    b = c
вывод a
конец

Сложность

O(n) шагов и O(1) памяти. Наивная рекурсия F(n) = F(n − 1) + F(n − 2) работает экспоненциально долго.

Частые ошибки

Путаница с нумерацией: с F0 = 0 или с F1 = 1 — уточняйте в условии.
Перезаписать a до вычисления суммы — нужна временная переменная c.
Переполнение: F93 не помещается в int64.