public class Fib {
  public static int compteur;
  public static int fib(int n,String prefixe) {
    compteur++;
    System.out.println(prefixe+" fib("+n+")");
    if (n==0) return 1;
    if (n==1) return 1;
    return fib(n-1,prefixe+"-")+fib(n-2,prefixe+"-");
  }
  public static void affiche(int []memoire) {
    for (int i=0; i<memoire.length; i++) {
      System.out.print(memoire[i]+" ");
    }
    System.out.println();
  }
  public static int fibMemoisee(int []memoire,int n,String prefixe) {
    System.out.println(prefixe+" fibMemoisee("+n+")");
    compteur++;
    if (memoire[n]!=0) return memoire[n];
    int n1=0,n2=0;
    if (memoire[n-1]!=0) { // valeur déjà calculée
      n1 = memoire[n-1];
    } else { // valeur non calculée précédemment
      n1 = fibMemoisee(memoire,n-1,prefixe+"-");
    }
    if (memoire[n-2]!=0) {
      n2 = memoire[n-2];
    } else {
      n2 = fibMemoisee(memoire,n-2,prefixe+"-");
    }
    memoire[n] = n1+n2;
    affiche(memoire);
    return memoire[n];
  }
  public static void main(String []a) {
    try {
      compteur = 0;
      int n = Integer.parseInt(a[0]);
      int [] memoire = new int[n+1];
      memoire[0] = 1;
      memoire[1] = 1;
      int v = fibMemoisee(memoire,n,"");
      System.out.println("Fibonnacci("+n+")="+v);
      System.out.println("Nombre d'appels = "+compteur);
    } catch(Exception e) {
    }
  }
}