2.fibonacci number

PROGRAM - II

(A) Problem Statement :

Write a program to calculate nth Fibonacci
number such that the time complexity as O(n).

(B) Input and Output :

The program takes the n value as input and prints first n Fibonacci numbers and gives nth Fibonacci number.

(i) the input value is 10 then the expected output is

Fibonacci series up to 10th number is
1 1 2 3 5 8 13 21 34 55
10 th Fibonacci number is : 55

(ii) the input value is 4 then the expected output is

Fibonacci series up to 4th number is
1 1 2 3
4th Fibonacci number is : 3

(C) Examples :

(i) f10 is 10th Fibonacci number .

f0 = 0, f1 = 1
f2 = f0 + f1 = 0 + 1 = 1
f3 = f1 + f2 = 1 + 1 = 2
f4 = f2 + f3 = 1 + 2 = 3
f5 = f3 + f4 = 2 + 3 = 5
f6 = f4 + f5 = 3 + 5 = 8
f7 = f5 + f6 = 5 + 8 = 13
f8 = f6 + f7 = 8 + 13 = 21
f9 = f7 + f8 =13 + 21 = 34
f10= f8 + f9 =21 + 34 = 55

(i) f4 is 4th Fibonacci number
f0 = 0, f1 = 1
f2 = f0 + f1 = 0 + 1 = 1
f3 = f1 + f2 = 1 + 1 = 2
f4 = f2 + f3 = 1 + 2 = 3

(D)Algorithm :

Step 1: Start
Step 2: Read the n value
Step 3: initialize f0 and f1 to 1.
Step 4: Repeat the following steps from I value 2 to n
(i) f2 = f0 + f1
(ii) f0 = f1
(iii) f1 = f2
Step 5: print the nth Fibonacci number , which is in f2.
Step 6: Stop

(E) Program :

#include
#include
void fibn(long int n)
{
long int f3,f2,f1,i;
if(n<=1)
printf("\n%ld th fibonacci number is %ld",n); //First fibonacci number is 1
else
{
f2=0;
f1=1; //print the series up to nth fibonacci number
printf("\n fibonaci series upto %ld th number is :",n);
printf("\n%ld",f1); // print first number
for(i=2;i<=n;i++)
{
f3=f2+f1; //calculation of numbers
f2=f1;
f1=f3;
printf("\t%ld",f3); //print the fibonacci number
} //print nth fibonacci number
printf("\n\n %ld th fibonacci number is %ld",n,f3);
}
}
void main()
{
long int n;
clrscr();
do
{ // read the nth value
printf("\n enter which fibonacci number to be displayed(positive no):");
scanf("%ld",&n);
}while(n<0); // read only positive number
fibn(n); // call function
getch();
}


(G) Testing :
S.NO
Aspect to be Tested
Expected Result
1
N value =10
(nth Fibonacci number)
55
Successful
2
N value = -3
Fails
(enter positive number)
3
N value = 47
Wrong result
(due to out of range)








(H) Limitations :

(i) In this program the n is taken as long int . the range
of long int is 2,147,483,647.So, it can calculate up
to 46th Fibonacci number.