fonction code (ref racine: arbreptr): entier;
var i:entier;
var somme:entier;
debut /* code parmi ceux de la meme taille*/
        si racine = null alors retourne 0 finsi;
        /* compter ceux de la meme taille mais avec un sous-arbre gauche
        plus petit*/
        somme:=0;
        pour i allant de 0 a taille(racine^.gauche)-1 par pas de 1 faire
                somme := somme+T[i]*T[taille(racine)-1-i]
        finpour;
        /*et enfin ceux avec les memes tailles des deux sous-arbres mais qui
        precedent * "racine" dans l'ordre*/
        somme := somme+code(racine^.gauche)*T[taille(racine^.droite)];
        retourne somme+code(racine^.d)
fin
finfonction;

fonction decode(val n,c: entier): arbreptr;
        /* n la taille, c le code*/
var racine: arbreptr;
var i: entier;
debut
        i:=-1;
        si n=0 alors retourne null finsi;
        allouer(racine);
        tantque c>=0 faire i:=i+1;c:=c-T[i]*T[n-1-i] fin tantque;
        c:=c+T[i]*T[n-1-i]; /*i est la taille du sous-arbre gauche*/
        racine^.gauche:=decode(i,c/T[n-1-i]);
        racine^.droite=decode(n-1-i,c mod T[n-1-i]);
        retourne racine
fin
finfonction;

1. Quelle est dans cet ordre, parmi tous les arbres de taille 0 à max, la position de l'arbre de taille n et dont le code c parmi les arbres de cette taille a été établi par la fonction code vue en cours?
   Réponse: c+ la somme pour i de 0 à n-1 du nombre d'arbres de taille i.
2. Modifier le code Exalgo de façon à utiliser cet ordre. On ajoute:

   fonction codetous(ref racine: arbreptr): entier;
   var i,somme:entier;
   début
      somme:=0;
      pour i allant de 0 à taille(racine)-1 par pas de 1 faire
         somme:=somme+T[i]
      finpour;
      retourne somme+code(racine)
   finfonction;
   
   fonction decodetous(val n,c: entier): arbreptr;
   var i:entier;
   debut
      tant que T[i]<=c faire 
         c:=c-T[n];
         n:=n+1
      fintantque;
      retourne decode(n,c)
   finfonction;
   
   

• Le G(n-1) est le nombre d'arbres avec racine et un sous-arbre (forcément de taille n-1)
• Le G(i)*G(n-1-i) est le nombre d'arbres avec deux sous arbres de tailles différentes i et n-1-i où i < n-1-i
• si n est impair il y a aussi la possibilité de deux sous arbres de la même taille (n-1)/2
• soit deux arbres identiques (G((n-1)/2) possibilités)
• soit deux différents (nombre de possibilités le coefficient binomial des choix de 2 parmi G((n-1)/2).

programme coeff;

type vec : tableau 0..20 de entier;
type tab : tableau 0..20 de vec;

var binom: tab;
var T:vec;

procédure init();
var i,j:entier;
debut
   pour i allant de 0 à 20 par pas de 1 faire
      binom[i][0]:=1;
      binom[i][i]:=1;
      pour j allant de 1 à i-1 par pas de 1 faire
         binom[i][j]:=binom[i-1][j-1]+binom[i-1][j]
      finpour
   finpour
finprocedure;

fonction coder(ref T:vec; val n,m:entier):entier;
debut
   selonque
      cas m=0: retourne 0
      cas T[m]=n: retourne coder(T,n-1,m-1)
      autrement: retourne binom[n-1][m-1]+coder(T,n-1,m)
   finselonque
finfonction;

procédure decoder(val c:entier; ref T:vec; val n,m:entier);
début
   printf("decoder(%i,%i,%i)\n",c,n,m);
   si m=0 alors retourne finsi;
   si c<binom[n-1][m-1] alors
      T[m]:=n;
      decoder(c,T,n-1,m-1)
   sinon
      decoder(c-binom[n-1][m-1],T,n-1,m)
   finsi
finprocedure;

var i:entier;
début
init();
pour i allant de 0 a binom[8][5]-1 par pas de 1 faire
   decoder(i,T,8,5);
   printf("vérification %i=%i\n",i,coder(T,8,5))
finpour
fin.