Числа Фибоначчи – это ряд чисел, в котором каждое последующее число равно сумме двух предыдущих:
1, 1, 2, 3, 5, 8, 13 и т. д.
То есть последовательность всегда начинается с двух единиц. А каждое следующее число является определяется по формуле:{\displaystyle{F_n\ =\ F_{n-1}\ +\ F_{n-2}}}
Для определения чисел Фибоначчи часто используется рекурсивный алгоритм:
- Если n = 1 или n = 2, вернуть 1 (поскольку первый и второй элементы ряда Фибоначчи равны 1).
- Вызвать рекурсивно функцию с аргументами n — 1 и n — 2.
- Результат двух вызовов сложить и вернуть полученное значение.
Реализация с использованием рекурсии
Реализация на Си
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int fibonacci(int N) // рекурсивная функция
{
if (N == 1 || N == 2)
return 1; // первые 2 числа равны 1
return fibonacci(N - 1) + fibonacci(N - 2); // складываем предыдущие 2 числа
}
int main()
{
int N;
printf("N=");
scanf("%d", &N); // вводим число N
for (int i = 1; i <= N; i++) // В цикле выводим N чисел Фибоначчи
printf("%d ", fibonacci(i));
getchar(); getchar();
return 0;
}Результат выполнения
У решения с рекурсией есть большая проблема: пересекающиеся вычисления. Когда вызывается fibonacci(N), то подсчитываются значения функции N-1 и для N-2. Но если требуется вычислить fibonacci(N-1), то значения для N-2 и N-3 вычисляются заново.
Поэтому поставленную задачу определения чисел Фибоначчи можно решить без использования рекурсии.
Реализация с использованием цикла
В этом алгоритме используется свойство, что для определения следующего числа Фибоначчи используются только два предыдущих значения.
Алгоритм при этом будет следующий
- Ввести номер N определяемого элемента.
- Проинициализировать два первых элемента a и b значениями 1, и если N<=2 вывести 1
- Выполнять нижеследующие действия N-2 раза
- Сложить a и b, присвоив результат третьей переменной c.
- Поменять начальные значения: a = b, b = c
- Вывести значение b.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int main()
{
int N;
printf("N="); // вводим число N
scanf("%d", &N);
int a = 1, b = 1, c;
if (N <= 2) // Первые два числа (a и b) равны 1
printf("1 ");
else
{
for (int i = 3; i <= N; i++)
{
c = a + b; // вычисляем следующее число как сумму двух предыдущих
a = b; b = c; // перемещаем два предыдущих числа
}
printf("%d ", b); // выводим последнее число
}
getchar(); getchar();
return 0;
}Результат выполнения — такой же, как в предыдущем случае.