`:
`;
`!
`?
|
Ecrire une procédure récursive Puissance(A,n,B) qui effectue ce calcul.
réponse
Expliquer comment la programmation dynamique permet de faire ce calcul de façon
beaucoup plus efficace qu'une fonction récursive appliquant directement
la récurrence.
Réponse
En calculant une seule fois et stockant dans un tableau les valeurs
de Arb(i) (en ordre croissant de i):
Proposer un invariant qui pourrait être utilisé pour démontrer que la boucle
est correcte.
le type listep est un pointeur vers une structure qui contient un entier (premier)
et un pointeur du même type
vers le prochain elément (reste); la liste vide est représentée par le pointeur NULL.
On suppose que deux variables de ce type
A et B pointent, toutes les deux vers des listes où les entiers sont triés en ordre
strictement croissant. Ecrire des instructions pour décider si c'est le cas que
tous les entiers de A sont aussi présents en B. (Une solution correcte et
efficace est souhaitée.)
Je veux calculer An, c'est-à-dire la n-ème puissance d'une matrice (de taille m×m) A;
je dispose d'une procédure Matmult(X,Y,Z) qui calcule en Z le produit
des deux matrices X et Y. Au lieu de faire n-1 multiplications, je veux
utiliser le fait que An pour n > 1 est soit le produit de An/2 avec lui-même
(quand n est pair), soit le produit de An-1 avec A (à utiliser
quand n est impair.)
procédure Puissance(val AA:matrice; val n:entier; ref B:matrice);
/* "AA" parce que "A" est un mot réservé d'Exalgo!*/
/* n>=1 */
var C:matrice;
debut
si n=1 alors
pour i allant de 1 à m par pas de 1 faire
pour j allant de 1 à m par pas de 1 faire
B[i][j]:=AA[i][j]
finpour
finpour
sinon
Puissance(AA,n/2,C); /*n/2 arrondi vers le bas*/
Matmult(C,C,B);
si n mod 2 > 0
alors
Matmult(AA,B,B)
finsi
finsi
finprocédure;
Je peux calculer le nombre de formes possibles d'un arbre binaire de n sommets,
en utilisant la récurrence Arb(n)=∑g=0n-1Arb(g)*Arb(n-1-g)
(où g est la taille du sous-arbre gauche et n-1-g celle de celui de droite);
avec la condition Arb(0)=1.
Tab[0]:=1;
pour i allant de 1 à max par pas de 1 faire
somme:=0;
pour g allant de 0 à n-1 par pas de 1 faire
somme:=somme+Tab[g]*Tab[n-1-g]
finpour;
Tab[i]:=somme
finpour;
le temps de calcul sera quadratique au lieu de (au moins) exponentiel.
le code qui suit est censé déterminer si le nombre positif n est premier
(c'est-à-dire qu'il n'existe pas de facteur f de n tel que 2 ≤ f < n.)
f:=2;
tant que f < n et (n/f)*f < n faire // f n'est pas facteur de n
f:=f+1
fintantque;
// n est premier si (et seulement si) f=n
Réponse
(f ≥ 2 ou n=1) et f ≤ n et n n'a pas de facteur en [2..f-1]
Donner le temps de calcul des boucles qui suivent en termes de O(fonction de n):
i:=1;
tant que i<n faire
i:=i*10
fintantque;
Réponse O(logn)
pour i allant de 1 à n faire
pour j allant de i à n faire
pour k allant de i à j faire
x:=x+1;
finpour
finpour
finpour;
Réponse O(n3)
j:=1;
pour i allant de 1 à n faire
tant que j<i faire
j:=j*2
fintantque
finpour;
Réponse O(n) (j multiplié par 2 au plus une fois
par itération de la boucle pour)
Réponse
tantque AA != NULL faire
selonque
cas B=NULL: retourne faux;
cas B^.premier<AA^.premier: B:=B^.prochain;
cas B^.premier=AA^.premier: AA:=AA^.prochain;B:=B^.prochain;
autrement: retourne faux
finselonque
fintantque;
retourne vrai;