Книга знаний

Инф. технологии

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

Числа Фибоначчи, способы решения задач на числа Фибоначчи, примеры кодаРЕШЕНИЕ
Последняя редакция №0 от 17.06.23
URL: http://kb.mista.ru/article.php?id=976

Ключевые слова: Фибоначчи, C++, решение


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


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



Числа Фибоначчи
— это последовательность чисел, которые задаются по определённому правилу. Оно звучит так: каждое следующее число равно сумме двух предыдущих. Первые два числа заданы сразу и равны 0 и 1.

Вот как выглядит последовательность Фибоначчи:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, … , ∞

Задачи на числа Фибоначчи в C++


Метод 1 (используйте рекурсию)


Простой метод, представляющий собой прямую рекурсивную реализацию математического рекуррентного соотношения, приведен выше.

// Fibonacci Series using Recursion

#include <bits/stdc++.h>
using namespace std;
  
int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}
  
int main()
{
    int n = 9;
    cout << fib(n);
    getchar();
    return 0;
}

Способ 2: (Используйте динамическое программирование)


Мы можем избежать повторной работы, проделанной в методе 1, сохранив числа Фибоначчи, рассчитанные до сих пор.

// C++ program for Fibonacci Series  

// using Dynamic Programming 
#include<bits/stdc++.h>
using namespace std;
  
class GFG{
      
public:
int fib(int n)
{
      
    // Declare an array to store 
    // Fibonacci numbers.
    // 1 extra to handle 
    // case, n = 0 
    int f[n + 2]; 
    int i;
  
    // 0th and 1st number of the 
    // series are 0 and 1
    f[0] = 0;
    f[1] = 1;
  
    for(i = 2; i <= n; i++)
    {
          
       //Add the previous 2 numbers 
       // in the series and store it
       f[i] = f[i - 1] + f[i - 2];
    }
    return f[n];
    }
};
  
// Driver code
int main ()
{
    GFG g;
    int n = 9;
      
    cout << g.fib(n);
    return 0;
}


Метод 3: (Метод 2 с оптимизацией пространства)


Мы можем оптимизировать пространство, используемое в методе 2, сохранив предыдущие два числа только потому, что это все, что нам нужно для получения следующего ряда чисел Фибоначчи.

// Fibonacci Series using Space Optimized Method

#include<bits/stdc++.h>
using namespace std;
  
int fib(int n)
{
    int a = 0, b = 1, c, i;
    if( n == 0)
        return a;
    for(i = 2; i <= n; i++)
    {
       c = a + b;
       a = b;
       b = c;
    }
    return b;
}
  
// Driver code
int main()
{
    int n = 9;
      
    cout << fib(n);
    return 0;
}

Способ 4: использование мощности матрицы {{1, 1}, {1, 0}}


Это еще одно значение O (n), основанное на том факте, что если мы n раз умножим матрицу M = {{1,1},{1,0}} для себя (другими словами, вычисляем мощность (M, n)), затем получаем (n + 1)-е число Фибоначчи в качестве элемента в строке и столбце (0, 0) в результирующей матрице.
Матричное представление дает следующее замкнутое выражение для чисел Фибоначчи:

#include<bits/stdc++.h>

using namespace std;
  
// Helper function that multiplies 2 
// matrices F and M of size 2*2, and
// puts the multiplication result 
// back to F[][] 
void multiply(int F[2][2], int M[2][2]);
  
// Helper function that calculates F[][] 
// raise to the power n and puts the
// result in F[][]
// Note that this function is designed 
// only for fib() and won't work as 
// general power function 
void power(int F[2][2], int n);
  
int fib(int n)
{
    int F[2][2] = { { 1, 1 }, { 1, 0 } };
      
    if (n == 0)
        return 0;
          
    power(F, n - 1);
      
    return F[0][0];
}
  
void multiply(int F[2][2], int M[2][2])
{
    int x = F[0][0] * M[0][0] + 
            F[0][1] * M[1][0];
    int y = F[0][0] * M[0][1] + 
            F[0][1] * M[1][1];
    int z = F[1][0] * M[0][0] + 
            F[1][1] * M[1][0];
    int w = F[1][0] * M[0][1] + 
            F[1][1] * M[1][1];
      
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
  
void power(int F[2][2], int n)
{
    int i;
    int M[2][2] = { { 1, 1 }, { 1, 0 } };
      
    // n - 1 times multiply the 
    // matrix to {{1,0},{0,1}}
    for(i = 2; i <= n; i++)
        multiply(F, M);
}
  
// Driver code
int main()
{
    int n = 9;
      
    cout << " " <<  fib(n);
      
    return 0;
}

Метод 5: (Оптимизированный метод 4)


Метод 4 может быть оптимизирован для работы во временной сложности O (Logn). Мы можем выполнить рекурсивное умножение, чтобы получить мощность (M, n) в предыдущем методе (аналогично оптимизации, выполненной в этом посте)

// Fibonacci Series using Optimized Method 

#include <bits/stdc++.h>
using namespace std;
  
void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);
  
// Function that returns nth Fibonacci number
int fib(int n)
{
    int F[2][2] = {{1, 1}, {1, 0}};
    if (n == 0)
        return 0;
    power(F, n - 1);
  
    return F[0][0];
}
  
// Optimized version of power() in method 4
void power(int F[2][2], int n)
{
    if(n == 0 || n == 1)
       return;
    int M[2][2] = {{1, 1}, {1, 0}};
      
    power(F, n / 2);
    multiply(F, F);
      
    if (n % 2 != 0)
        multiply(F, M);
}
  
void multiply(int F[2][2], int M[2][2])
{
    int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
      
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
  
// Driver code
int main()
{
    int n = 9;
      
    cout << fib(9);
    getchar();
      
    return 0;
}

Способ 6: (O (Log n) время)


Ниже приведена еще одна интересная формула повторения, которая может быть использована для нахождения n-го числа Фибоначчи за O (Log n) времени.

If n is even then k = n/2:

F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)



(-1)n = Fn+1Fn-1 - Fn2

Moreover, since AnAm = An+m for any square matrix A,
the following identities can be derived (they are obtained
from two different coefficients of the matrix product)

FmFn + Fm-1Fn-1 = Fm+n-1         ---------------------------(1)

By putting n = n+1 in equation(1),
FmFn+1 + Fm-1Fn = Fm+n             --------------------------(2)

Putting m = n in equation(1).
F2n-1 = Fn2 + Fn-12
Putting m = n in equation(2)

F2n = (Fn-1 + Fn+1)Fn = (2Fn-1 + Fn)Fn (Source: Wiki)   --------
( By putting Fn+1 = Fn + Fn-1 )
To get the formula to be proved, we simply need to do the following
If n is even, we can put k = n/2
If n is odd, we can put k = (n+1)/2
Ниже приведена реализация вышеупомянутой идеи.

// C++ Program to find n'th fibonacci Number in

// with O(Log n) arithmetic operations
#include <bits/stdc++.h>
using namespace std;
  
const int MAX = 1000;
  
// Create an array for memoization
int f[MAX] = {0};
  
// Returns n'th fibonacci number using table f[]
int fib(int n)
{
    // Base cases
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return (f[n] = 1);
  
    // If fib(n) is already computed
    if (f[n])
        return f[n];
  
    int k = (n & 1)? (n+1)/2 : n/2;
  
    // Applying above formula [Note value n&1 is 1
    // if n is odd, else 0.
    f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1))
           : (2*fib(k-1) + fib(k))*fib(k);
  
    return f[n];
}
  
// Driver program to test above function 
int main()
{
    int n = 9;
    printf("%d ", fib(n));
    return 0;
}

Метод 7: (Другой подход (с использованием формулы Бине))


В этом методе мы непосредственно реализуем формулу для n-го члена ряда Фибоначчи.
Fn = {[(√5 + 1)/2] ^ n} / √5
Примечание: Приведенная выше формула дает правильный результат только до n<71. Поскольку по мере продвижения вперед от n>= 71 ошибка округления становится значительно большей. Хотя использование функции floor вместо функции round даст правильный результат для n = 71 . Но после n = 72 это также приводит к сбою.
Пример: для N = 72 правильный результат равен 498454011879264, но приведенная выше формула дает 498454011879265.

// C++ Program to find n'th fibonacci Number
#include<iostream>
#include<cmath>
  
int fib(int n) {
  double phi = (1 + sqrt(5)) / 2;
  return round(pow(phi, n) / sqrt(5));
}
  
// Driver Code
int main ()
{
  int n = 9;
  std::cout << fib(n) << std::endl;
  return 0;
}

Метод 8: DP с использованием запоминания (подход сверху вниз)


Мы можем избежать повторной работы, проделанной в методе 1, сохранив числа Фибоначчи, вычисленные до сих пор. Нам просто нужно сохранить все значения в массиве.

#include <bits/stdc++.h>

using namespace std;
int dp[10];
int fib(int n)
{
    if (n <= 1)
        return n;
  
    // temporary variables to store
    //  values of fib(n-1) & fib(n-2)
    int first, second;
  
    if (dp[n - 1] != -1)
        first = dp[n - 1];
    else
        first = fib(n - 1);
  
    if (dp[n - 2] != -1)
        second = dp[n - 2];
    else
        second = fib(n - 2);
  
    // memoization
    return dp[n] = first + second;
}
  
// Driver Code
int main()
{
    int n = 9;
  
    memset(dp, -1, sizeof(dp));
  
    cout << fib(n);
    getchar();
    return 0;
  
}

Описание | Рубрикатор | Поиск | ТелепатБот | Захваченные статьи | Установки | Форум
© Станислав Митичкин (Волшебник), 2005-2025 | Mista.ru

Яндекс.Метрика