Implement Four Fibonacci Algorithms in C++ Fibloop(n) o a straightforward loop t

Question

Implement Four Fibonacci Algorithms in C++ Fibloop(n) o a straightforward loop to add up numbers in the sequence and return the nth number " Note: you do not need an array here. The loop only needs to keep the last two fibonacci numbers to calcular the next one FibRecursive(n) o a straightforward implementation of the recursive Fibonacci function 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) This will be recursive, but it will check the cache for see if Fib(n) has already o been stored there, 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 matrix " 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 simple integer * " calculating using only the multiplication - ...no built-in exponentiation -...with as few multiplications as possible operator and loops or recursion operators or functions!!

Explanation / Answer

Please find my implementation.

Please let me know in case of any issue.

1)
int FibLoop(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;
}

2)

int FibRecursive(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}

3)

#define NIL -1
#define MAX 100

int lookup[MAX];

/* Function to initialize NIL values in lookup table */
void _initialize()
{
int i;
for (i = 0; i < MAX; i++)
lookup[i] = NIL;
}

/* function for nth Fibonacci number */
int FibRecursiveWithCache(int n)
{
if (lookup[n] == NIL)
{
if (n <= 1)
lookup[n] = n;
else
lookup[n] = fib(n-1) + fib(n-2);
}

return lookup[n];
}

4)

/* function that returns nth Fibonacci number */
int FibMatric(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;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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