|
Ecrire une procédure récursive Puissance(A,n,B) qui effectue ce calcul.
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.
Proposer un invariant qui pourrait être utilisé pour démontrer que la boucle est correcte.
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
i:=1;
tant que i<n faire
i:=i*10
fintantque;
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;
j:=1;
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.)