This blog article should you how to do Fibonacci calculation using C++ with Matrix. In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation.
Fn = Fn-1 + Fn-2
Below is the code extracted from the resource at the end of the article. This approach is using Matrix to calculate the Fibonacci instead of using recursion.
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);
}
The key part of the calculation liaises with the multiply function. The ultimate output taken is F[0][0].
You can download the code from the link below and execute.
Source code download: https://github.com/chanmmn/cpp/tree/master/ConAppFibonacciMatrix/?WT.mc_id=DP-MVP-36769
Reference: https://www.geeksforgeeks.org/cpp-program-for-fibonacci-numbers/
Pingback: Explaining Memory Leak using C++ | Chanmingman's Blog