Problème liste chainé

Résolu
armasousou Messages postés 1268 Date d'inscription   Statut Membre Dernière intervention   -  
mamiemando Messages postés 33772 Date d'inscription   Statut Modérateur Dernière intervention   -
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");
}


A voir également:

5 réponses

mamiemando Messages postés 33772 Date d'inscription   Statut Modérateur Dernière intervention   7 882
 
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 :

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
0
armasousou Messages postés 1268 Date d'inscription   Statut Membre Dernière intervention   83
 
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
0
mamiemando Messages postés 33772 Date d'inscription   Statut Modérateur Dernière intervention   7 882
 
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...
0
armasousou Messages postés 1268 Date d'inscription   Statut Membre Dernière intervention   83
 
Oui bah oui, c'est évident, fallait que le "next" soit vide, jsuis bete ^^'
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
mamiemando Messages postés 33772 Date d'inscription   Statut Modérateur Dernière intervention   7 882
 
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.

void free_ack(ack * pa) {
  for(; pa; pa = pa->pa_next) { 
    free(pa);
  }
}


Bonne chance
0