(Votre fonction pourrait très bien avoir d'autres paramètres si vous le jugez utile.)
Réponse
#define taille 8
#define vrai 1
#define faux 0
int T[taille+1][taille+1];
int bon(int i, int j)
{ /* peut-on mettre une dame a position [i][j] sans conflit avec celles
dans les colonnes plus a gauche? */
int ii,jj;
for ((ii=i,jj=j-1);jj>0;jj--) if (T[ii][jj]) return faux;
for ((ii=i-1,jj=j-1);ii>0&&jj>0;(ii--,jj--)) if (T[ii][jj]) return faux;
for ((ii=i+1,jj=j-1);ii<=taille&&jj>0;(ii++,jj--)) if (T[ii][jj]) return faux;
return vrai;
}
int nombre(int j)
{
int i,somme=0;
if (j==taille) return 1; /*sinon chercher une case dans la colonne j+1*/
for (i=1;i<=taille;i++) /*essayer de mettre la dame dans la ligne i */
if (bon(i,j+1))
{
T[i][j+1]=vrai;
somme+=nombre(j+1); /*et ajouter le nombre de facons de completer
les colonnes j+2..taille*/
T[i][j+1]=faux;
}
return somme;
}
main()
{
int i,j;
for (i=1;i<=taille;i++) for (j=1;j<=taille;j++) T[i][j]=faux;
printf("%i solutions\n",nombre(0));
}
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.
Réponse On peut calculer dans un tableau, disons T, pour chaque entier n (jusqu'à une limite donnée) le nombre d'appels engendrés par un appel de f(n).
T[1]=1;
for (i=2;i<=limite;i++);
{
T[i]=1;
for (j=1;j<i;j++)
if (i%j==0)
T[i]+=T[j];
}
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 */
Réponse i > =1 et j < =max et si n est dans T il est a une position [x][y] telle que x > =i et y < =j
Pour démontrer que cette assertion reste vraie
après une itération, il faut
démontrer que ``assertion plus la condition du while" avant
l'exécution du if (alors) else implique ``assertion"
après;
donc, il faut démontrer que l'assertion reste vraie après
exécution
de la branche (alors) ou de la branche else.
Je prends l'exemple de la branche else:
avant exécution du else les 3 assertions suivantes sont vraies:
assertion invariant; la condition while; négation de la
condition if.
C'est-à-dire i > =1 et j <
=max et si n est dans T il est a une position [x][y] telle que x
> =i et y < =j; et i <
=max et j >
=1 et T[i][j]!=n; et T[i][j] < =n
on conclut:
T[i][j] < n
si y < =j T[i][y] < n
si n est dans T il est a une position [x][y] telle que x
> =i+1 et y < =j
i+1 > =1.
Et des deux dernières conclusions (et le j < =max), on
déduit
que l'invariant reste vraie après le i=i+1 (application
de la règle pour les affectations).
pour i allant de 1 a n*n par pas de 1 faire P(); /**/ finpour;Réponse O(n2)
pour i allant de 1 a n par pas de 1 faireRéponse O(n3)
pour j allant de 1 a i*i par pas de 1 faire P(); finpour; /**/
finpour;
i:=1;Réponse O(logn)
tant que i<n*n faire i:=i*2; /**/
fintantque;
pour i allant de 1 a n par pas de 1 faireRéponse O(nlogn)
j:=1;
tant que j<i faire j:=j*2;
fintantque; /**/
finpour;
pour k allant de 1 a n par pas de 1 faireRéponse O(n2)
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.)
Réponse
struct noeud
{
struct noeud *Succ, *Pred;
};
void liberer(struct noeud *P)
{
if (P==nul) return;
while (P->Pred!=nul) P=P->Pred;
/* P pointe au debut*/
while (P!=nul)
{
struct noeud *temp=P->Succ;
desallouer(P);
P=temp;
}
}