fork download
copy 
  1. class Scratch {
  2.   public static final int INITIAL_CACHE_CAPACITY = 8;
  3.   private static int[] cache = new int[INITIAL_CACHE_CAPACITY];
  4.   private static int currentMax = 1;
  5.  
  6.   static {
  7.     cache[1] = 1;
  8.   }
  9.  
  10.   public static void main(String[] args) {
  11.     System.out.printf("fib(10) = %d%n", fib(10));
  12.     System.out.printf("fib(20) = %d%n", fib(20));
  13.     System.out.printf("fib(30) = %d%n", fib(30));
  14.     System.out.printf("fib(40) = %d%n", fib(40));
  15.   }
  16.  
  17.   static int fib(int n) {
  18.     if (n < 0) {
  19.       throw new IllegalArgumentException("n must be >= 0");
  20.     }
  21.     if (n <= currentMax) {
  22.       return cache[n];
  23.     }
  24.     if (n >= cache.length) {
  25.       resizeCache(n);
  26.     }
  27.     for (int index = currentMax + 1; index <= n; ++index) {
  28.       cache[index] = cache[index - 1] + cache[index - 2];
  29.     }
  30.     if (currentMax < n) {
  31.       currentMax = n;
  32.     }
  33.     return cache[n];
  34.   }
  35.  
  36.   private static void resizeCache(int minCapacity) {
  37.   	int newCapacity = calculateNewCacheCapacity(minCapacity);
  38.     int currentCapacity = cache.length;
  39.     if (newCapacity < currentCapacity) {
  40.       throw new IllegalArgumentException("newCapacity must be larger than the current capacity");
  41.     }
  42.     int[] newCache = new int[newCapacity];
  43.     System.arraycopy(cache, 0, newCache, 0, currentCapacity);
  44.     cache = newCache;
  45.   }
  46.  
  47.  
  48.   private static int calculateNewCacheCapacity(int minCapacity) {
  49.     int newSize = cache.length;
  50.     while (newSize <= minCapacity) {
  51.       newSize *= 2;
  52.     }
  53.     return newSize;
  54.   }
  55. }
Success #stdin #stdout 0.1s 48388KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
fib(10) = 55
fib(20) = 6765
fib(30) = 832040
fib(40) = 102334155
https://ideone.com/4ciLWk
language:
Java (HotSpot 12)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!