Рекурсивное нахождение чисел Фибоначчи на C++

Числа Фибоначчи – это ряд чисел, в котором каждое последующее число равно сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13 и т.д.
Формула:
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2
Пример вычисления:
F3 = F2 + F1 = 1 + 1 = 2
F4 = F3 + F2 = 2 + 1 = 3
F5 = F4 + F3 = 3 + 2 = 5
F6 = F5 + F4 = 5 + 3 = 8
и т.д.

Вычисление n-го числа ряда Фибоначчи с помощью цикла

Алгоритм

  1. Ввести два начальных значения ряда (fib1 и fib2).
  2. Ввести номер определяемого элемента.
  3. Выполнять нижеследующие действия количество раз, равное по величине номеру определяемого элемента, уменьшенному на две единицы (т.к. первое и второе значение ряда уже известны).
    1. Сложить fib1 и fib2, присвоив результат третьей переменной (fib_sum).
    2. Поменять начальные значения: fib1 = fib2, а fib2 = fib_sum

Код на Python

fib1 =1 fib2 =1   n =input(«Значение какого элемента ряда \ Фибоначчи вы хотите узнать?

Рекурсивное нахождение чисел Фибоначчи на C++

«) n =int(n)# преобразование в целое число   i =2while i < n: fib_sum = fib2 + fib1 fib1 = fib2 fib2 = fib_sum i +=1print(fib_sum)

Рекурсивное вычисление n-го числа ряда Фибоначчи

Алгоритм

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

Код на Python

def fib(n): if n==1or n==2: return1return fib(n-1) + fib(n-2)
 

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

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

Вычисление чисел Фибоначчи

д.

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


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

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

 

Реализация с использованием рекурсии

Реализация на Си

Результат выполнения

У решения с рекурсией есть большая проблема: пересекающиеся вычисления. Когда вызывается 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

#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;
}

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;
}

Быстрое вычисление Фибоначчи

15.Фибоначчиев поиск.

В этом поиске анализируются элементы, находящиеся в позициях равных числам Фибоначчи.

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

{1,2,3,5,8,13,21,34,55}

Поиск продолжается до тех пор, пока не будет найден интервал между 2-мя ключами, где может располагаться отыскиваемый ключ.

Например:

Дано исходное множество ключей {3,5,8,9,11,14,15,19,21,22,28,33,35,37,42,45,48,54}

Отыскиваемый ключ К=42

1 шаг. kᴜk1

42>3 => отыскиваемый ключ уравнивается с ключом, стоящим в позиции равной числам Фибоначчи.

2 шаг.k ᴜ k2

42>5 => выбирается следующее число Фибоначчи, стоящее в соответствующей позиции.

3 шаг. k ᴜ k3

42>8=> сравнение продолжается

4 шаг. k ᴜ k5

42>11=> сравнение продолжается

5 шаг. k ᴜ k8 42>19

6 шаг. k ᴜ k13 42>35

7 шаг.kᴜk18

42<52 => найден интервал, в котором находится отыскиваемый ключ от 13 до 18.

8 шаг. k ᴜ k1 42>35

9 шаг. k ᴜ k2 42>37

10 шаг. K=42 => найден.

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

Закрыть меню