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

Алгоритмизация / Числа Фибоначчи

 

Числа Фибоначчи – это ряд чисел, в котором каждое последующее число равно сумме двух предыдущих:

1, 1, 2, 3, 5, 8, 13 и т. д.

То есть последовательность всегда начинается с двух единиц. А каждое следующее число является определяется по формуле:

Числа Фибоначчи
Для определения чисел Фибоначчи часто используется рекурсивный алгоритм:

  • Если 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
#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
#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;
}

Результат выполнения - такой же, как в предыдущем случае.


Назад: Алгоритмизация

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *