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;
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;
|
|
|
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.