Problème liste chainé
Résolu
Bonjour à tous,
Je programmais la fonction d'ackerman en algo pour le "fun" et mon programme se plante je comprend pas pourquoi ><
La fonction d'ackerman est défini par A(m, n)
Si m = 0 => A(m,n) = n+1
Si n = 0 => A(m,n) = A(m-1, 1)
Sinon A(m,n) = A(m-1, A(m, n-1))
J'ai pris le programme par une liste chainé avec deux int, un element suivant et un precedant.
Voila mon programme :
#include <stdio.h>
#include <stdlib.h>
typedef struct sA{
int m;
int n;
struct sA* next;
struct sA* prev;
}Ack;
Ack* allouer(int, int);
void calc(Ack*);
void aff(Ack);
int main(int argc, char **argv)
{
int m, n, i, j;
Ack* A;
//~ printf("Donne ton m et n\n");
//~ scanf("%d", &m);
//~ scanf("%d", &n);
m=2;
n=1;
A = allouer(m, n);
while( A->m != 0 )
{
Ack* tmp;
aff(*A);
tmp = A;
while(tmp->next != NULL)
{
tmp = tmp->next;
}
calc(tmp);
}
printf("\n");
printf("Ton Ackerman (%d,%d) est égal à %d :)\n", m, n, A->n);
return 0;
}
Ack* allouer(int m, int n)
{
Ack* pA;
pA = malloc(sizeof(Ack));
pA->m=m;
pA->n=n;
pA->next = NULL;
pA->prev = NULL;
return pA;
}
void calc(Ack* pA)
{
int m = pA->m;
int n = pA->n;
if( n == 0 )
{
pA->m = m -1;
pA->n = 1;
}
else if( m == 0 )
{
pA->prev->n = n+1;
pA->prev->next = NULL;
free(pA);
}
else
{
pA->next = allouer(m, n-1);
pA->next->prev = pA;
pA->m =m-1;
}
}
void aff(Ack A)
{
int j, i=0;
while(A.next != NULL)
{
printf("A(%d, ", A.m);
i++;
A= *(A.next);
}
printf("A(%d, %d", A.m, A.n);
i++;
for(j=0 ; j<i ; j++)
{
printf(")");
}
printf("\n");
}
Je programmais la fonction d'ackerman en algo pour le "fun" et mon programme se plante je comprend pas pourquoi ><
La fonction d'ackerman est défini par A(m, n)
Si m = 0 => A(m,n) = n+1
Si n = 0 => A(m,n) = A(m-1, 1)
Sinon A(m,n) = A(m-1, A(m, n-1))
J'ai pris le programme par une liste chainé avec deux int, un element suivant et un precedant.
Voila mon programme :
#include <stdio.h>
#include <stdlib.h>
typedef struct sA{
int m;
int n;
struct sA* next;
struct sA* prev;
}Ack;
Ack* allouer(int, int);
void calc(Ack*);
void aff(Ack);
int main(int argc, char **argv)
{
int m, n, i, j;
Ack* A;
//~ printf("Donne ton m et n\n");
//~ scanf("%d", &m);
//~ scanf("%d", &n);
m=2;
n=1;
A = allouer(m, n);
while( A->m != 0 )
{
Ack* tmp;
aff(*A);
tmp = A;
while(tmp->next != NULL)
{
tmp = tmp->next;
}
calc(tmp);
}
printf("\n");
printf("Ton Ackerman (%d,%d) est égal à %d :)\n", m, n, A->n);
return 0;
}
Ack* allouer(int m, int n)
{
Ack* pA;
pA = malloc(sizeof(Ack));
pA->m=m;
pA->n=n;
pA->next = NULL;
pA->prev = NULL;
return pA;
}
void calc(Ack* pA)
{
int m = pA->m;
int n = pA->n;
if( n == 0 )
{
pA->m = m -1;
pA->n = 1;
}
else if( m == 0 )
{
pA->prev->n = n+1;
pA->prev->next = NULL;
free(pA);
}
else
{
pA->next = allouer(m, n-1);
pA->next->prev = pA;
pA->m =m-1;
}
}
void aff(Ack A)
{
int j, i=0;
while(A.next != NULL)
{
printf("A(%d, ", A.m);
i++;
A= *(A.next);
}
printf("A(%d, %d", A.m, A.n);
i++;
for(j=0 ; j<i ; j++)
{
printf(")");
}
printf("\n");
}
A voir également:
- Problème liste chainé
- Liste déroulante excel - Guide
- Chaine tnt gratuite sur mobile - Guide
- Liste déroulante en cascade - Guide
- Liste code ascii - Guide
- Chaine radio - Télécharger - Médias et Actualité
5 réponses
Je suppose que le bug n'est pas un plantage du programme, mais simplement que tu n'obtiens pas la valeur espérée ? Si je lance ton programme j'obtiens :
À mon avis il y a une erreur dans ton programme car si j'écris ceci :
...; j'obtiens :
ack(1, 3) est un appel récursif cohérent avec ack(2, 1). Donc je pense que ton programme est globablement juste pour la récursion.
Par contre, je pense que l'erreur se situe moment de calculer le dernier terme (quand m atteint 0, n prend la valeur 4, et donc la valeur attendue est 4+1 = 5).
Bonne chance
A(2, 1) A(1, A(2, 0)) A(1, A(1, 1)) A(1, A(0, A(1, 0))) A(1, A(0, A(0, 1))) A(1, A(0, 2)) A(1, 3) Ton Ackerman (2,1) est égal à 3 :)
À mon avis il y a une erreur dans ton programme car si j'écris ceci :
#include <stdio.h> unsigned ack(unsigned m, unsigned n) { return m == 0 ? n + 1 : n == 0 ? ack(m - 1, 1) : ack(m - 1, ack(m, n - 1)); } int main() { unsigned m = 2, n = 1; printf("ack(%d, %d) = %d\n", m, n, ack(m, n)); return 0; }
...; j'obtiens :
ack(2, 1) = 5
ack(1, 3) est un appel récursif cohérent avec ack(2, 1). Donc je pense que ton programme est globablement juste pour la récursion.
Par contre, je pense que l'erreur se situe moment de calculer le dernier terme (quand m atteint 0, n prend la valeur 4, et donc la valeur attendue est 4+1 = 5).
Bonne chance
Le faire recursivement c'est assez simple en effet, je l'avais fait en scheme.
Je sais pas pourquoi ca bug parce que, comme tu l'as vu, l'affichage donne A(1,3); mais il s'arrete parce qu'il considere que m est égal à 0, or l'affichage montre 1 !
Je comprend aps :x
Je sais pas pourquoi ca bug parce que, comme tu l'as vu, l'affichage donne A(1,3); mais il s'arrete parce qu'il considere que m est égal à 0, or l'affichage montre 1 !
Je comprend aps :x
Moi je ne comprends pas ton code. En fait je n'ai pas compris pourquoi tu stockais des résultats dans une liste chaînée, ni ce que tu stockais dans chaque maillon, ni pourquoi la liste était doublement chaînée.
Mais ce qui me paraît suspect, c'est que tu n'atteins jamais le terme A(0, 4). En fait si tu rajoutes un aff(*A) après ton while tu vas t'apercevoir que ta récursion est arrêtée à A(0, A(1, 2)) ce qui me paraît suspect car il reste encore A(0, A(0, 3)), A(0, 4), et 5 à évaluer.
À mon avis c'est ton critère d'arrêt qui est faux...
Mais ce qui me paraît suspect, c'est que tu n'atteins jamais le terme A(0, 4). En fait si tu rajoutes un aff(*A) après ton while tu vas t'apercevoir que ta récursion est arrêtée à A(0, A(1, 2)) ce qui me paraît suspect car il reste encore A(0, A(0, 3)), A(0, 4), et 5 à évaluer.
À mon avis c'est ton critère d'arrêt qui est faux...
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Parfait problème résolu :-)
Ceci dit il faudrait vérifier que tu désalloues bien tous les maillons. Je trouve qu'il serait plus logique dans ton code d'avoir une fonction qui fait le calcul et une autre qui désalloue la liste chaînée. Car si tu alloues / calcules /désalloues au fil des itérations, la structure de liste chaîne ne sert pas vraiment.
Bonne chance
Ceci dit il faudrait vérifier que tu désalloues bien tous les maillons. Je trouve qu'il serait plus logique dans ton code d'avoir une fonction qui fait le calcul et une autre qui désalloue la liste chaînée. Car si tu alloues / calcules /désalloues au fil des itérations, la structure de liste chaîne ne sert pas vraiment.
void free_ack(ack * pa) { for(; pa; pa = pa->pa_next) { free(pa); } }
Bonne chance