Числа Фибоначчи
Ключевые слова: Фибоначчи, 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;
}
|