Problème liste chainé

Résolu/Fermé
armasousou Messages postés 1267 Date d'inscription dimanche 16 août 2009 Statut Membre Dernière intervention 30 décembre 2016 - 12 févr. 2013 à 12:49
mamiemando Messages postés 33446 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 décembre 2024 - 15 févr. 2013 à 20:08
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 33446 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 décembre 2024 7 812
Modifié par mamiemando le 14/02/2013 à 02:17
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 1267 Date d'inscription dimanche 16 août 2009 Statut Membre Dernière intervention 30 décembre 2016 83
14 févr. 2013 à 12:28
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 33446 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 décembre 2024 7 812
15 févr. 2013 à 01:21
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 1267 Date d'inscription dimanche 16 août 2009 Statut Membre Dernière intervention 30 décembre 2016 83
15 févr. 2013 à 18:06
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 33446 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 décembre 2024 7 812
15 févr. 2013 à 20:08
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