Take this recursive Fibonacci implementation and convert it into the caching bas

Question

Take this recursive Fibonacci implementation and convert it into the caching based version discussed in class. Implement your caching to store a maximum of 5 values. Create 2 variations: one that stores all values and one that only stores even values. Make sure that you don't leave any gaps in your cache — if you have 5 cache entries you must cache 5 unique and valid values.

Compare the caching implementations to the recursive implementation using the time utility. How do the caching implementations affect the results? Why do the different caching strategies show different results? What happens if you increase the maximum number of values to 10? Note that you can define different constants at compile time using something like -DCACHE_SIZE=10. Test the implementations with a variety of values between 32 and 52.

Fibonacci:

Explanation / Answer

Answer

Code for all value of fibonacci :

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Fibonacci_Cache_All {

   private int[] cache = new int[5];
  
   public Fibonacci_Cache_All(){
       // n de 1 = 1;
       cache[1] = 1;
   }

   public int fibonacci_get(int n){
              
       if(cache[n] != 0){
           return cache[n];
       }
  
       // n de 0 = 0
       if(n <= 0){
           return 0;
       }
                      
       int result = fibonacci_get(n-1) + fibonacci_get(n-2);
       cache[n] = result;
       return result;
   }

   public static void main(String[] args) throws Exception{
  
       String inputLine = "";   
      
       InputStreamReader converter = new InputStreamReader(System.in);
       BufferedReader in = new BufferedReader(converter);
       Fibonacci_Cache_All fib = new Fibonacci_Cache_All ();
      
       while (!(inputLine.equals("yes"))){
           System.out.println("Please enter 'yes' to stop: ");
           inputLine = in.readLine();
          
           if (!(inputLine.equals("yes"))){
               int value = Integer.parseInt(inputLine);
               long begin = System.currentTimeMillis();
               System.out.print("Fibonacci for "+ inputLine + " is :: " + fib.fibonacci_get(value) +" ");
               long end = System.currentTimeMillis();
               System.out.print("Time " + (end - begin) + " ");
           }
       }
   }
}

Code for even values in fibonacci:

public class Fibonacci_Cache_Even {

   private int[] cache = new int[5];
  
   public Fibonacci_Cache_Even(){
       // n de 1 = 1;
       cache[1] = 1;
   }

   public int fibonacci_get(int n){
              
       if(cache[n] != 0){
           return cache[n];
       }
  
       // n de 0 = 0
       if(n <= 0){
           return 0;
       }
                      
       int result = fibonacci_get(n-1) + fibonacci_get(n-2);
       if(reult % 2 == 0)
       {
           cache[n] = result;
       }
       return result;
   }

   public static void main(String[] args) throws Exception{
  
       String inputLine = "";   
      
       InputStreamReader converter = new InputStreamReader(System.in);
       BufferedReader in = new BufferedReader(converter);
       Fibonacci_Cache_Even fib = new Fibonacci_Cache_Even ();
      
       while (!(inputLine.equals("yes"))){
           System.out.println("Please enter 'yes' to stop: ");
           inputLine = in.readLine();
          
           if (!(inputLine.equals("yes"))){
               int value = Integer.parseInt(inputLine);
               long begin = System.currentTimeMillis();
               System.out.print("Fibonacci for "+ inputLine + " is :: " + fib.fibonacci_get(value) +" ");
               long end = System.currentTimeMillis();
               System.out.print("Time " + (end - begin) + " ");
           }
       }
   }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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