Задачи по вычислению числа из ряда чисел Фибоначчи очень часто встречаются при изучении программирования на языке C++. В этой статье я расскажу об одном алгоритме, который может решить эту задачу. Если Вас интересуют другие задачи, то загляните в раздел с решениями задач по программированию.
Числа Фибоначчи — это числовая последовательность, в которой каждый следующий член равен сумме двух предыдущих. Первые два члена равны единице. Нулевой член равен нулю, но чаще всего его не рассматривают как элемент последовательности, и тогда ряд чисел Фибоначчи имеет вид: 1, 1, 2, 3, 5, 8, 13, 21, … — такой вид он имеет и в отрицательную сторону с отрицательным знаком.
Пример последовательности от -5-го до 5-го члена: -5, -3, -2, -1, -1, 0, 1, 1, 2, 3, 5
В задачах обычно требуется найти n-ый член последовательности.
Рекурсивное решение на C++
Рекурсия
Очень часто рекурсию в программировании показывают на примере вычисления чисел Фибоначчи рекурсивным алгоритмом. Такой алгоритм довольно прост, но время выполнение растет по экспаненте при увеличении n. Поэтому алгоритм работает медленно при больших n, а также может произойти переполнение стека(Stack Overflow).
Для решения создадим функцию f(n), в качестве аргумента она будет получать число n. Эта функция будет возвращать число, которое будет равно f(n-1) + f(n-2). То есть она вызывает себя 2 раза из самой себя.
|
5 6 7 8 9 |
unsigned long long int f(int n) { return f(n-1)+f(n-2); } |
Теперь добавим возвращемое значение для f(0), f(1), f(2), чтобы при вызове функции с такими агрументами функция прекращала вызывать себя и выдавала значение. Для f(0) возвращаемое значение будет 0. Для f(1) и f(2) — 1.
|
5 6 7 8 9 10 11 |
unsigned long long int f(int n) { if(n == 0) return 0; if(n == 1 || n == 2) return 1; return f(n-1)+f(n-2); } |
Обратите внимание, функция возвращает значение с типом unsigned long long int. Это позволит ей выводить огромные числа (от 0 до 18 446 744 073 709 551 615), а значит она сможет работать с большими n.
Таким образом данная функция вычисляет n-ое число из ряда чисел Фиббоначи. Функция работает только с n >= 0.
В ходе работы функция вызывает сама себя, раскладывается, пока не вызовет f(1) или f(2), которые тут же возвратят 1 и не будут делать больше ничего. После этого функция обратно «складывается».
Для примера напишем программу с вызовом функции f() с аргументом 5 и выведем результат.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> using namespace std; unsigned long long int f(int n) { if(n == 0) return 0; if(n == 1 || n == 2) return 1; return f(n-1)+f(n-2); } int main() { cout << f(5) << endl; return 0; } |
Результат выполнения программы
Вычисленное число Фибоначчи
Под капотом всё происходило примерно так: функция f(5) вызвала 2 функции f(4) и f(3); функция f(4) вызвала функции f(3) и f(2), а функция f(3) вызвала функции f(2) и f(1) и так далее… Но, для наглядности посмотрите на рисунок.
Вызовы функции f()
Стрелочка, выходящая из прямоугольника с функцией, показывает возвращаемое значение.
