The Fibonacci Numbers Fn are defined by F 0 = 0 F1 1 = 1 Fn = F n-2 + F n- 1 N>1
ID: 674386 • Letter: T
Question
The Fibonacci Numbers Fn are defined by
F0 = 0
F11 = 1
Fn = Fn-2 + Fn-1 N>1
The program is split into two parts.
Part 1
Write a recursive method public static int Fibonacci(int n)
to compute Fn given any nonnegative value of n. Test the program by computing and printing the values of Fn for n = 0,1,....,20. Next instrument a recursive method so that for any one call to the method from the main test program, the method counts the total number of times the method is entered.
Public static int nCalls
"at class level" , meaning before the beginning of public static void main or any other method. Set nCalls = 0 in main before each call to Fibonacci. In Fibonacci add 1 to nCalls. Then print the final value of nCalls as well as the value of Fn after returning from Fibonacci.
Examine the values of nCalls. Estimate how fast nCalls is growing relative to Fn. For example compute the ratios (nCalls / Fn+1), (nCalls / Fn+2), and (nCalls/Fn+3). Does n increase.
Wriete another (nonrecursive method
public static int fastFibonacci(n)
That computes Fn by returning F0 or F1 if n = 0 or 1, otherwise using a loop to compute F2, F3 ......Fn
How many arithmetic operations does fastFibonacci use to compute F20.
Is fastFibonacci faster than FIbonacci for n =20. What is the ratio of their speeds for n=20, or for some arger value of n? Use a value large enough that Fibonacci uses a measurable time interval. By calling System.nanotime().(Divide by 1000 to get milliseconds).
Part 2
Make a semi-log plot of nCals as a function of n, for methods Fibonacci and also for fastFibonacci, along with a set of data for the value of Fn+3 all on the same semi-log graph. Also make a log-log plot of the same three sets of data .
Explanation / Answer
Program for recuresive and non recursive fibonacci series as output:
1.Using recursive function
import java.util.Scanner;
public class fibCalculate {
int ncalls=0;
public static void main(String args[]) {
int n,k;
fibCalculate f1=new fibCalculate();
System.out.println("Enter number to print series of fibonacci numbers: ");
int number = new Scanner(System.in).nextInt();
System.out.println("The series for " + number +" numbers : ");
for(int i=1; i<=number; i++){
n=f1.ncalls++;
System.out.println("fibnumber"+fibRecursive(i) +" ");
System.out.println(("Ratio"+n/fibRecursive(i)));
}
k=f1.ncalls;
System.out.println("time"+System.nanoTime()/1000);
System.out.print("total number of calls"+k);
}
public static int fibRecursive(int l){
if(l == 1 || l == 2){
return 1;
}
return fibRecursive(l-1) + fibRecursive(l -2);
}
/.
public static int fibnonRecursive(int m){
if(m == 1 || m == 2){
return 1;
}
int f1=1, f2=1, fib=1;
for(int i= 3; i<= m; i++){
fib = f1 + f2;
f1 = f2;
f2 = fib;
}
return fib;
}
}
output:
Enter number to print series of fibonacci numbers:
20
The series for 20 numbers :
fibnumber1
Ratio0
fibnumber1
Ratio1
fibnumber2
Ratio1
fibnumber3
Ratio1
fibnumber5
Ratio0
fibnumber8
Ratio0
fibnumber13
Ratio0
fibnumber21
Ratio0
fibnumber34
Ratio0
fibnumber55
Ratio0
fibnumber89
Ratio0
fibnumber144
Ratio0
fibnumber233
Ratio0
fibnumber377
Ratio0
fibnumber610
Ratio0
fibnumber987
Ratio0
fibnumber1597
Ratio0
fibnumber2584
Ratio0
fibnumber4181
Ratio0
fibnumber6765
Ratio0
time100162178842
total number of calls20
2.using nonrecursive function:
import java.util.Scanner;
public class fibCalculate {
int ncalls=0;
public static void main(String args[]) {
int n,k;
fibCalculate f1=new fibCalculate();
System.out.println("Enter number to print series of fibonacci numbers: ");
int number = new Scanner(System.in).nextInt();
System.out.println("The series for " + number +" numbers : ");
for(int i=1; i<=number; i++){
n=f1.ncalls++;
System.out.println("fibnumber"+fibnonRecursive(i) +" ");
System.out.println(("Ratio"+n/fibnonRecursive(i)));
}
k=f1.ncalls;
System.out.println("time"+System.nanoTime()/1000);
System.out.print("total number of calls"+k);
}
public static int fibRecursive(int l){
if(l == 1 || l == 2){
return 1;
}
return fibRecursive(l-1) + fibRecursive(l -2);
}
public static int fibnonRecursive(int m){
if(m == 1 || m == 2){
return 1;
}
int f1=1, f2=1, fib=1;
for(int i= 3; i<= m; i++){
fib = f1 + f2;
f1 = f2;
f2 = fib;
}
return fib;
}
}
sample output:
Enter number to print series of fibonacci numbers:
20
The series for 20 numbers :
fibnumber1
Ratio0
fibnumber1
Ratio1
fibnumber2
Ratio1
fibnumber3
Ratio1
fibnumber5
Ratio0
fibnumber8
Ratio0
fibnumber13
Ratio0
fibnumber21
Ratio0
fibnumber34
Ratio0
fibnumber55
Ratio0
fibnumber89
Ratio0
fibnumber144
Ratio0
fibnumber233
Ratio0
fibnumber377
Ratio0
fibnumber610
Ratio0
fibnumber987
Ratio0
fibnumber1597
Ratio0
fibnumber2584
Ratio0
fibnumber4181
Ratio0
fibnumber6765
Ratio0
time100381941751
total number of calls20
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.