|
Ecrire une procédure récursive Puissance(A,n,B) qui effectue ce calcul.
réponse
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;
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):
Tab[0]:=1;le temps de calcul sera quadratique au lieu de (au moins) exponentiel.
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;
Proposer un invariant qui pourrait être utilisé pour démontrer que la boucle est correcte.
f:=2;Réponse (f ≥ 2 ou n=1) et f ≤ n et n n'a pas de facteur en [2..f-1]
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
i:=1;Réponse O(logn)
tant que i<n faire
i:=i*10
fintantque;
pour i allant de 1 à n faireRéponse O(n3)
pour j allant de i à n faire
pour k allant de i à j faire
x:=x+1;
finpour
finpour
finpour;
j:=1;Réponse O(n) (j multiplié par 2 au plus une fois par itération de la boucle pour)
pour i allant de 1 à n faire
tant que j<i faire
j:=j*2
fintantque
finpour;
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.)
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;