Fibonacci Algorithms: Write C++ Program (Linux) for FibRecursiveWithCache(n) and

Question

Fibonacci Algorithms: Write C++ Program (Linux) for FibRecursiveWithCache(n) and FibMatrix(n). Please display program results. See instruction below: FibRecursiveWithCache(n) o a "Dynamic Programming" variation "("dynamic programming" is a fancy term for storing and reusing previously calculated results - in other words, a kind of caching) o This will be recursive, but it will check the cache for see if Fib(n) has already e, rather than calculating it again. o Note: the "cache" should be cleared each time you call the top-level Fib function FibMatrix(n) o This will use the matrix multiplication method from exercise 0.4 o Write a helper function that efficiently calculates powers of a matri:x So MAn should take O(log2(n)) matrix multiplications instead of the naive O(n) .Tip: first forget matrices and think about powers of a calculating using only the multiplication · no built-in exponentiation ...with as few multiplications as possible simple integer operator and loops or recursion operators or functions!!

Explanation / Answer

FibRecursiveWithCache

int FibRecursiveWithCache(int n)
{

int f[n+1];
int i;

f[0] = 0;
f[1] = 1;

for (i = 2; i <= n; i++)
{

f[i] = f[i-1] + f[i-2];
}

return f[n];
}

FibMatrix(n) :

int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if (n == 0)
return 0;
pow(F, n-1);

return F[0][0];
}

void mul(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 pow(int F[2][2], int n)
{
int i;
int M[2][2] = {{1,1},{1,0}};

for (i = 2; i <= n; i++)
mul(F, M);
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.