(Votre fonction pourrait très bien avoir d'autres paramètres si vous le jugez utile.)
int f(int n)
{
int somme=0, i;
if (n==1) return 1;
for (i=1;i<n;i++)
if (n%i==0) /*si i est facteur de n*/
somme+=g(f(i)); /*g une fonction definie ailleurs*/
return somme;
}
Je veux savoir combien d'appels récursifs seront effectués quand f(n) est appelé pour des grandes valeurs de n.
Décrire comment la programmation dynamique peut aider à faire ce calcul de façon efficace.
i=1;
j=max;
while (i<=max && j>=1 && T[i][j]!=n)
if (T[i][j]>n)
j--;
else
i++;
/*postcondition: si n est dans T il est a la position [i][j];
* sinon i>max ou j<1 */
pour i allant de 1 a n*n par pas de 1 faire P(); /**/ finpour;
pour i allant de 1 a n par pas de 1 faire pour j allant de 1 a i*i par pas de 1 faire P(); finpour; /**/ finpour;
i:=1; tant que i<n*n faire i:=i*2; /**/ fintantque;
pour i allant de 1 a n par pas de 1 faire j:=1; tant que j<i faire j:=j*2; fintantque; /**/ finpour;
pour k allant de 1 a n par pas de 1 faire
i:=1;
tant que i<k faire
i:=i*2;
pour j allant de 1 a i par pas de 1 faire P(); finpour; /**/
fintantque;
finpour;
(L'espace utilisé pour un noeud est libéré par un appel de desallouer() avec comme paramètre un pointeur au noeud.)