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

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

Числа Фибоначчи – это ряд чисел, в котором каждое последующее число равно сумме двух предыдущих:
1, 1, 2, 3, 5, 8, 13 и т. д.
То есть последовательность всегда начинается с двух единиц. А каждое следующее число является определяется по формуле:

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

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

  • Если n = 1 или n = 2, вернуть 1 (поскольку первый и второй элементы ряда Фибоначчи равны 1).
  • Вызвать рекурсивно функцию с аргументами n-1 и n-2.
  • Результат двух вызовов сложить и вернуть полученное значение.

Реализация

#include <stdio.h>
int fibonacci(int N) {
  if (N == 1 || N == 2)
    return 1;
  return fibonacci(N - 1) + fibonacci(N - 2);
}
int main() {
  int N;
  printf("N=");
  scanf("%d", &N);
  for (int i = 1; i <= N; i++)
    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

Реализация

#include <stdio.h>
int main() {
  int N;
  printf("N=");
  scanf("%d", &N);
  int a = 1, b = 1, c;
  if (N <= 2) {
    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 не будет опубликован. Обязательные поля помечены *