package memo; import java.util.HashMap; // suite de Fibonacci public class Fib { static long fib(int n) { if (n <= 1) return n; return fib(n - 2) + fib(n - 1); } // mémoïsation static HashMap<Integer, Long> memo = new HashMap<Integer, Long>(); // static { memo.put(0, 0L); memo.put(1, 1L); } static long fibMemo(int n) { //if (n <= 1) return n; Long l = memo.get(n); if (l != null) return l; if (n <= 1) l = (long)n; else l = fibMemo(n - 2) + fibMemo(n - 1); memo.put(n, l); return l; } // programmation dynamique static long fibDP(int n) { long[] f = new long[n + 1]; f[1] = 1; for (int i = 2; i <= n; i++) f[i] = f[i - 2] + f[i - 1]; return f[n]; } // et avec deux entiers seulement static long fibDP2(int n) { int a = 0, b = 1; // a = F(k), b = F(k+1) while (n-- > 0) { b = b + a; a = b - a; } return a; } public static void main(String[] args) { assert fibDP(10) == 55; assert fibDP2(10) == 55; long start = System.currentTimeMillis(); System.out.println(fibMemo(80)); System.out.println((System.currentTimeMillis() - start) + " ms"); // 42 2s // 43 3s // 44 5s // 45 8s // 46 13s // 50 = F11s = 89s } }