programme arbres; /* on considere les arbres non vide; */ type arbreptr:^arbre; type arbre:enreg Taille: entier; nombredefils:entier; premierfils:arbreptr; prochainfrere:arbreptr finenreg; type vec:tableau 1..20 de entier; type tab:tableau 1..20 de vec; var AL:tab;/* AL[a][n] sera le nombre de listes de a arbres avec une taille totale de n*/ procedure init(); var i,j,p:entier; debut AL[0][0]:=1; pour i allant de 1 à 20 par pas de 1 faire AL[0][i]:=0; AL[1][i]:=0 finpour; AL[1][1]:=1; pour i allant de 1 à 20 par pas de 1 faire pour j allant de 1 à 20 par pas de 1 faire AL[1][i]:=AL[1][i]+AL[j][i-1] /*racine et j sous-arbres de taille totale i-1*/ finpour; pour j allant de 2 à i par pas de 1 faire /* p taille du premier sous-arbre*/ AL[j][i]:=0; pour p allant de 1 à i-j+1 par pas de 1 faire AL[j][i]:=AL[j][i]+AL[j-1][i-p]*AL[1][p] finpour finpour finpour finprocedure; fonction code(val AP:arbreptr):entier;/*code de AP parmi les arbres de la meme taille*/ var i,j,c,reste:entier; var filsptr:arbreptr; debut c:=0; reste:=AP^.Taille-1; pour i allant de 1 à AP^.nombredefils-1 par pas de 1 faire /* compter les arbres de cette taille avec i fils*/ c:=c+AL[i][reste] finpour; filsptr:=AP^.premierfils; pour i allant de 1 à AP^.nombredefils par pas de 1 faire /*et compter ceux avec le meme taille et nombre de fils que AP et qui sont identiques a AP dans les premiers i-1 sous-arbres mais different dans le i-eme*/ pour j allant de 1 à filsptr^.Taille-1 par pas de 1 faire /* ceux ou le i-eme sous-arbre est plus petit que celui de AP*/ c:=c+AL[1][j]*AL[AP^.nombredefils-i][reste-j]; finpour; reste:=reste-filsptr^.Taille; /*le nombre de sommets dans les sous-arbres a droite de i*/ c:=c+code(filsptr)*AL[AP^.nombredefils-i][reste]; /* et enfin ceux ou le i-eme sous arbre est de la meme taille que celui de AP*/ filsptr:=filsptr^.prochainfrere finpour; retourne c finfonction; fonction decode(val c:entier; /*le code*/ val t:entier /*la taille*/):arbreptr; var AP,filsptr:arbreptr; var reste,f,ts:entier; debut allouer(AP); AP^.Taille:=t; AP^.prochainfrere:=NUL; si t=1 alors AP^.nombredefils:=0; AP^.premierfils:=NUL; retourne AP finsi; reste:=t-1; /*la somme des tailles des sous-arbres*/ AP^.nombredefils:=1; tant que AP^.nombredefils<=reste ET AL[AP^.nombredefils][reste]<=c faire c:=c-AL[AP^.nombredefils][reste]; AP^.nombredefils:=AP^.nombredefils+1 fin tantque; /*le nombre de fils est determine*/ pour f allant de 1 à AP^.nombredefils-1 par pas de 1 faire /* trouver le f-eme sous-arbre*/ ts:=1; /*taille du sous-arbre*/ tant que reste>=ts ET AL[1][ts]*AL[AP^.nombredefils-f][reste-ts]<=c faire c:=c-AL[1][ts]*AL[AP^.nombredefils-f][reste-ts]; ts:=ts+1 fin tantque; reste:=reste-ts; si f=1 alors AP^.premierfils:=decode(c/AL[AP^.nombredefils-f][reste],ts); filsptr:=AP^.premierfils sinon filsptr^.prochainfrere:=decode(c/AL[AP^.nombredefils-f][reste],ts); filsptr:=filsptr^.prochainfrere finsi; c:=c mod AL[AP^.nombredefils-f][reste] finpour; /*et trouver le dernier sous-arbre*/ si AP^.nombredefils=1 alors AP^.premierfils:=decode(c,reste) sinon filsptr^.prochainfrere:=decode(c,reste) finsi; retourne AP finfonction; procedure liberer(val AP:arbreptr); var P1,P2:arbreptr; debut P1:=AP; tant que P1!=NUL faire P2:=P1^.prochainfrere; liberer(P1^.premierfils); desallouer(P1); P1:=P2 fin tantque finprocedure; var AP:arbreptr; var i,f,nom:entier; debut init(); nom:=0; pour i allant de 0 à AL[1][11]-1 par pas de 1 faire AP:=decode(i,11); si code(AP) != i alors printf("Anomalie!!\n"); sinon nom:=nom+1 finsi; liberer(AP) finpour; printf("%i parmi %i corrects \n",nom,AL[1][11]); fin.