Числа Фибоначчи

Последовательность Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, ...

Каждое следующее число равно сумме двух предыдущих: $F(n) = F(n-1) + F(n-2)$.

Разбор

Главная программа

В цикле выводим первые 20 чисел Фибоначчи:

алг
нач
    цел i
    нц для i от 1 до 20
        вывод фибоначчи(i), " "
    кц
    вывод нс
кон

нц для i от 1 до 20 — цикл от 1 до 20
Для каждого i вызываем функцию фибоначчи и выводим результат через пробел

Функция фибоначчи

алг цел фибоначчи(цел n)
нач
    если n <= 2
    то
        знач := 1
    иначе
        знач := фибоначчи(n - 1) + фибоначчи(n - 2)
    все
кон

Базовый случай: $F(1) = F(2) = 1$
Рекурсивный случай: складываем два предыдущих числа
Функция вызывает сама себя — это называется рекурсия

Для больших $n$ рекурсивный вариант работает медленно, потому что одни и те же числа вычисляются много раз. Например, для $F(5)$ функция $F(3)$ вызывается дважды. Итеративный вариант (через цикл, как в примере с факториалом) работал бы быстрее.

Полная программа

алг
нач
    цел i
    нц для i от 1 до 20
        вывод фибоначчи(i), " "
    кц
    вывод нс
кон

алг цел фибоначчи(цел n)
нач
    если n <= 2
    то
        знач := 1
    иначе
        знач := фибоначчи(n - 1) + фибоначчи(n - 2)
    все
кон