|
Des arbres binaires peuvent être representés par des structures de noeuds,
chaque noeud possédant un champ valeur:entier et deux champs
gauche et droit qui seront des pointeurs vers les sous-arbres
gauche et droit (ou nul).
Ecrire en exalgo
fonction identique(val P,Q: arbreptr):booleen
debut
selon que
cas P=nul ou Q=nul: retourne P=Q
cas P^.valeur!=Q^.valeur: retourne faux
cas !identique(P^.gauche,Q^.gauche): retourne faux
autrement retourne identique(P^.droit,Q^.droit)
finselonque
finfonction
fonction copie(val P: arbreptr): arbreptr
var cop: arbreptr;
debut
si P=nul alors retourne nul finsi;
allouer(cop);
cop^.valeur:=P^.valeur;
cop^.gauche:=copie(P^.gauche);
cop^.droit:=copie(P^.droit);
retourne cop
finfonction
Une procédure récursive aléatoire P(l1,w1,l2,w2)
se comporte comme:
si l1=0 et l2=0 alors retourne finsi;
si l1=0 alors w1:=0 finsi;
si l2=0 alors w2:=0 finsi;
Pause pour une durée aléatoire avec espérance (moyenne) de 1/(w1+w2);
avec probabilité w1/(w1+w2) faire P(l1-1,w1+1,l2,w2)
autrement (donc avec probabilité w2/(w1+w2)) faire P(l1,w1,l2-1,w2+1);
retourne;
On veut calculer la somme en moyenne des durées de toutes les pauses quand
P(100,1,100,1) est appelé.
T(0,y1,0,y2)=0
T(x1,y1,0,y2)=1/y1+T(x1-1,y1+1,0,0)
T(0,y1,x2,y2)=1/y2+T(0,0,x2-1,y2+1)
T(x1,y1,x2,y2)=1/(y1+y2)+(y1*T(x1-1,y1+1,x2,y2)+y2*T(x1,y1,x2-1,y2+1))/(y1+y2)
procedure CALC()
var T:tab; /* un tableau suffisamment grand */
debut
pour y1 allant de 0 a 101 par pas de 1 faire
pour y2 allant de 0 a 101 par pas de 1 faire
T[0][y1][0][y2]:=0
finpour
finpour;
pour x allant de 0 a 100 par pas de 1 faire
pour y1 allant de 0 a 101 par pas de 1 faire
pour y2 allant de 0 a 101 par pas de 1 faire
T[x][y1][0][y2]:=1/y1 + T[x-1][y1+1][0][0]
T[0][y1][x][y2]:=1/y2 + T[0][0][x-1][y2+1]
finpour
finpour
finpour;
pour x1 allant de 1 a 100 par pas de 1 faire
pour x2 allant de 1 a 100 par pas de 1 faire
pour y1 allant de 1 a 101 par pas de 1 faire
pour y2 allant de 1 a 101 par pas de 1 faire
T[x1][y1][x2][y2]:=(1+y1*T[x1-1][y1+1][x2][y2]+y2*T[x1][y1][x2-1][y2+1])/(y1+y2)
finpour
finpour
finpour
finpour;
/* la somme souhaitée est T[100][1][100][1] */
finprocedure
i:=1;
somme:=1;
tant que somme <= m faire
i:=i+1;
somme:=somme+i
fin tantque;
i > 0 et somme=1+...+i et somme < =m+i
Déterminer (en fonction de n à O( ) près) le temps de calcul des boucles
(a), (b), (c) (d), et (e)
(P() est une procédure dont le temps de calcul est constant.)
pour i allant de 1 a n*n*n par pas de 1 faire P(); finpour;
O(n3)
pour i allant de 1 a n par pas de 1 faire
pour j allant de 1 a i par pas de 2 faire P(); finpour;
finpour;
O(n2)
i:=1;
tant que i*i<n faire i:=i*2;
fintantque;
O(logn)
pour i allant de 1 a n par pas de 1 faire
j:=1;
tant que i*j<n faire j:=j+2;
fintantque;
finpour;
O(nlogn) ( ≈ (n+n/2+n/3+...+n/n)/2)
m:=1;
pour k allant de 1 a n par pas de 1 faire
i:=1;
tant que i<k faire
i:=i*2;
m:=m*2;
fintantque;
pour j allant de 1 a m par pas de 1 faire P(); finpour;
finpour;
Difficile. Le temps est dominé par la boucle pour quand k=n et,
donc, le temps est O(derniere valeur de m). Cette dernière valeur de m
est le produit de n nombres qui sont les k arrondi vers le haut à
la prochaine puissance de 2.
O((2n)n) est une assez bonne réponse (vaut le point);
O(n! 2n) est meilleure mais pas la meilleure possible.