Chapter 3 The Efficiency of Algorithms The Fibonacci sequence of numbers is defi

Question

Chapter 3 The Efficiency of Algorithms The Fibonacci sequence of numbers is defined as follows: The first and second numbers are both 1. After that, each number in the sequence is the sum of the two preceding numbers. Thus, the Fibonacc sequence is as follows: 1, 1, 2, 3, 5, 8, 13, 01, lf F(n) stands for the nth value in the sequence, then this definition can be expressed as 1) FOn 2) for n 2 a. The value of Fat position n is defined using the value of F at two smaller positions. Something that is defined in terms of "smaller versions" of itself is said to be recursive, so the Fibonacci sequence is recursive. Using the definition of the Fibonacci sequence, compute the value of F(20). b. A formula for F(n) is F(n)

Explanation / Answer

Answer a)
Using the definition of F(n) for Fibonacii sequence we get
F(1)=1
F(2)=1
F(3)=2
F(4)=3
F(5)=5
F(6)=8
F(7)=13
F(8)=21
F(9)=34
F(10)=55
F(11)=89
F(12)=144
F(13)=233
F(14)=377
F(15)=610
F(16)=987
F(17)=1597
F(18)=2584
F(19)=4181
F(20)=6765

A simple program written in C language for recursive Fibonacci sequence is show below.

So using a recursive algorithm, we get F(20)=6765

#include<stdio.h>
int F(int n)
{
   if(n==1 || n==2)
   {
       return 1;
   }
   else
       return F(n-1)+F(n-2);
}
int main()
{
  
   printf(" F(%d)=%d",20,F(20));
      
}

Answer b:

Using the formula in a calculator also, we get F(20) = 6765

Answer c:

Both the methods give the same answer. But in terms of elegance, recursive method looks neat and clear based on the definition of Fibonacci sequence. But for larger 'n' say 100, the recursion takes a long time to compute as all the previous terms need to be computed. Whereas the formula based method takes the same time no matter what the value of 'n' is . So the formula method is efficient irrespective of 'n'.

Answer d and e

As its not possible to upload an excel sheet here, just showing you the contents of the file. Its simple for entering using the recursion, but for the formula method , this is how its entered , where <cellname> is replaced by the name of cell like C1 , D2 etc whereever you entered the value of n.

=SQRT(5)/5*POWER((1+SQRT(5))/2,<cellname>)-SQRT(5)/5*POWER((1-SQRT(5))/2,<cellname>)

=============================

Hope this answers all the questions. Please rate the answer if you are happy with it.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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