public static long terribleFibonacci (int n) if (n 1) return n; return terribleF
ID: 3587578 • Letter: P
Question
public static long terribleFibonacci (int n) if (n 1) return n; return terribleFibonacci (n -1) + terribleFibonacci (n -2); x * * PROBLEM 4: The impLementation of terribleFibonacci is TERRIBLE! Write a * more efficient version of fibonacci. Do not change runFibonacciLoop or runFibonacciSomeValues * To make fibonacci run faster, you want it so that each call to * fibonacci (n) computes the fibonacci numbers between and n once, not k over and over again. Comment: You will want to use a local variable of type "long" rather than * type "int", for the reasons discussed above. * Comment: At some point, your fibonacci numbers might become negative. * This is normal and expected. * http://en.wikipedia.org/wiki/Integer_overflow We discuss this at length * in our systems classes * You may not use any"fields" to solve this problem (a field is a variable - either before that is declared "outside" of thefunction declaration- * or after). public static void runFibonacciLoop )t for (int N = 0; NExplanation / Answer
package algs11;
import java.util.Arrays;
import stdlib.*;
/**
* This is a skeleton file for your homework. Edit the sections marked TODO. You
* may add new functions. You may also edit the function "main" to test your
* code.
*
* You must not add static variables. You MAY add static functions, just not
* static variables.
*
* It is okay to add functions, such as
*
* <pre>
* public static double sumHelper (double[] list, int i, double sumSoFar) {
* </pre>
*
* but it is NOT okay to add static variables, such as
*
* <pre>
* public static int x;
* </pre>
*
* As for homework 1, you must not change the declaration of any method.
*
* You can edit the main function all you want. I will not run your main
* function when grading.
*/
public class MySecondHomework {
/**
* PROBLEM 4: Run runTerribleLoop for one hour. You can stop the program using
* the red "stop" square in eclipse. Fill in the OUTPUT line below with the
* numbers you saw LAST --- edit the line, replacing the two ... with what
* you saw:
*
* OUTPUT: terribleFibonacci(56)=225851433717 // TODO
*
* Comment: the code uses "long" variables, which are like "int", but
* bigger. It's because fibonacci numbers get really big really fast.
*/
public static void runTerribleLoop () {
for (int N = 0; N < 100; N++)
StdOut.format ("terribleFibonacci(%2d)=%d ", N, terribleFibonacci (N));
}
public static void runTerribleSomeValues () {
StdOut.format ("terribleFibonacci(%2d)=%d ", 13, terribleFibonacci (13));
StdOut.format ("terribleFibonacci(%2d)=%d ", 7, terribleFibonacci (7));
StdOut.format ("terribleFibonacci(%2d)=%d ", 21, terribleFibonacci (21));
}
public static long terribleFibonacci (int n) {
if (n <= 1) return n;
return terribleFibonacci (n - 1) + terribleFibonacci (n - 2);
}
public static void runFibonacciLoop () {
for (int N = 0; N < 100; N++)
StdOut.format ("fibonacci(%2d)=%d ", N, fibonacci (N));
}
public static void runFibonacciSomeValues () {
StdOut.format ("fibonacci(%2d)=%d ", 13, fibonacci (13));
StdOut.format ("fibonacci(%2d)=%d ", 7, fibonacci (7));
StdOut.format ("fibonacci(%2d)=%d ", 21, fibonacci (21));
}
public static long fibonacci (int n) {
long num1 = 0;
long num2 = 1;
long big = 0;
if (n == 0) return 0;
if (n == 1) return 1;
for (int k=2; k <= n; k++) {
big = num1+num2;
num1 = num2;
num2 = big;
}
return big; // TODO
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.