Problème de récursivité

Signaler
Messages postés
28
Date d'inscription
mardi 29 avril 2003
Statut
Membre
Dernière intervention
15 janvier 2016
-
Messages postés
28
Date d'inscription
mardi 29 avril 2003
Statut
Membre
Dernière intervention
15 janvier 2016
-
bonjour à tous

J'ai un petit souci dans la fonction récursive
Cette fonction doit permettre de trouver toutes les combinaisons possibles pour un puzzle pour un nombre de piece qui peut varrier, d'où l'utilisation de la récursivité. Les pièces sont des monbres compris entre 0 et le nombre de pièce - 1. (pour 6 pièces de 0 a 5). une contraintes pour le placement des pièces, le numéro de la pièce ne doit pas correspondre a rang dans le tableau (exemple 0 ne peut pas être en case 0)

lors de l'empilage, cela fonctionne correctement, la fonctions s'appelle normalement et exécute ce que je lui demande. C'est lors du dépilage que ca coince et je ne trouve pas pourquoi. en effet, lorsque la fonction la plus basse se termine, elle rend la main à celle immédiatement supérieure et à ma grande surprise, le tableau coteanant la combinaison contient n'importe quoi.

voilà déja un appercu de l'affichage
fonction de rang 0
1
fonction de rang 1
1 0
fonction de rang 2
1 0 3
fonction de rang 3
1 0 3 2
fonction de rang 4
1 0 3 2 5
fonction de rang 5
1 0 3 2 5 4

et lorsqu'on remonte dans la fonction de rang 4, le tableau est le suivant :
0 1 2 4 3.

voici le code
void Calculer(int Puzzle[], int Position)
{
int i; // Indice de boucle


Decalage(Position);
printf("On rentre dans la fonction calculer avec comme position %d\n", Position);


// On prend l'indice
for(i = 0; i < MAX_PIECE; i++)
{
Decalage(Position);
printf("L'indice = %d\n", i);


// SI on est dans le cas du premier passage
if(Position == 0)
{
// i ne doit pas être égal a son rang c'est a dire 0
if(i != 0)
{
Decalage(Position);
printf("On a trouver un indice qui convient : %d\n", i);
Puzzle[Position] = i;
Decalage(Position);
AfficherPuzzle(Puzzle);
printf("\n");


// On rappel la fonction pour la position suivante
Calculer(Puzzle, (Position + 1));
}
else
{
Decalage(Position);
printf("l'indice a la meme valeur que ca position\n");
}
}
else
{


// L'indice doit être différent du rang
if(!Existe(i, Puzzle))
{
// On regarde si l'indice n'existe pas déja
if(i != Position)
{
Decalage(Position);
printf("On a trouver un indice qui convient : %d\n", i);
Puzzle[Position] = i;
Decalage(Position);
AfficherPuzzle(Puzzle);
printf("\n");


// Si on n'est pas a la dernière pièce
if (Position != (MAX_PIECE - 1))
{
// On rappel la fonction pour passé a lindice suivant
Calculer(Puzzle, (Position + 1));
Decalage(Position);
printf("Affichage du puzzle en remontant !\n");
Decalage(Position);
AfficherPuzzle(Puzzle);
printf("\n");
}
}
else
{
Decalage(Position);
printf("l'indice a la meme valeur que ca position\n");
}
}
else
{
Decalage(Position);
printf("L'indice a deja ete utilise !\n");
}
}
}


// Si on est a la dernière position
// On affiche le puzzle
if(Position == (MAX_PIECE - 1))
{
// Si le puzzle est complet
if(Complet(Puzzle))
{
// On affiche le puzzle
Decalage(Position);
AfficherPuzzle(Puzzle);


// On calcule et on affiche le nombre de coup
// de la position
printf("Nombre de coup : %d\n", NbCoup(Puzzle));
}


printf("\n");
Pause();
}


// On remet l'indice a -1
Puzzle[Position] = -1;


Decalage(Position);
printf("On remonte dans la fonction de rang supérieur !\n");



}


int main(int argc, char* argv[])
{
// On crée le tableau du puzzle
int Puzzle[MAX_PIECE];


// On initialise le puzzle
InitPuzzle(Puzzle);


Calculer(Puzzle, 0);
Pause();
return 0;
}

La fonction Decalage affiche des espaces
la fonction AfficherPuzzle affiche le tableau du puzzle
la fonction Complet teste si le puzzle est complet (toutes les pièces ont été entrée)
La fonction Existe teste si l'indice i exsite dans le Puzzle

Merci d'avance

3 réponses

Messages postés
48
Date d'inscription
lundi 29 novembre 2004
Statut
Membre
Dernière intervention
16 mars 2005

Je pense que tu fauis trop complique,
en matiere de fonction recursive tout doit etre tres tres simple
sinon on se perd, et on tue le processeur.
En premier tu mets la condition d'arret de recursivite.
Puis tu code ton traitement.
Ci dessous j'en tente de faire un exemple
pour te donner des idees.

Bien entendu j'assume que "une contraintes pour le placement
des pièces, le numéro de la pièce ne doit pas correspondre a rang dans
le tableau (exemple 0 ne peut pas être en case 0)"

sera verifiee dans la fonction InitPuzzle.

# include <stdio.h>
# define MAX_PIECE 5
main(){
int Puzzle[] = {1,3,5,0,4,2};
int Position = 0;
recurse(Puzzle,Position);
fprintf(stdout,"\n Puzzle termine \n");
}

int recurse( int *p, int Pos){
int i = 0;
if (Pos > MAX_PIECE){
return -1;
}
while ( i < MAX_PIECE){
if(i == p[Pos] ){
fprintf(stdout, "%d ",i);
fflush(stdout);
break ;
}
i++;
}
return (recurse(p,Pos + 1));
}


Yves
Messages postés
28
Date d'inscription
mardi 29 avril 2003
Statut
Membre
Dernière intervention
15 janvier 2016

Merci à toi Yves pour ta réponse.

J'ai oublié de préciser le fonctionnement d'une fonction dans mon post.

La fonction InitPuzzle n'initialise pas le puzzle avec une combinaison. Cette fonction sert uniquement a initialiser le tableau avec des -1 pour qu'il ne soit pas vide. c'est la fonction Calculer qui est chargé de le remplir.
Messages postés
28
Date d'inscription
mardi 29 avril 2003
Statut
Membre
Dernière intervention
15 janvier 2016

pour être plus clair dans ce que je désire faire car je men rend compte que je ne suis pas clair du tout

voilà la fonction itérative qui donne ce que je veux obtenir mais le nombre de pièce est fixe. moi ce que je veu, c'est qu'il soit variable, voilà pourquoi je veu avoir recours a une fonction récursive

int main(int argc, char* argv[])
{



int i, j, k, l, m, n; // les indices de boucles
int nb = 0; // Nombre de possibilité
int Puzzle[MAX_PIECE]; // tablezau du puzzle
ofstream fichier("NbPossibilite.txt"); // Fichier
int nbc; // nombre de coup
int NombreCoup[MAX_PIECE]; // tableau contenan le nombre de puzzle pour chaque nombre de coup


// On initialise le tableau MombreCoup
InitTab(NombreCoup, 0);


if(fichier.is_open())
{
//fichier << "Aucune contrainte";
fichier << "Chaque piece n'apparait qu'une seule fois\n";
fichier << "Le rang doit etre different du numero de la piece \n";
fichier << "Deux pièces de numéro qui se suive ne doivent pas se suivre\n";
for (i = 1; i < 6; i++)
for (j = 0; j < 6; j++)
if ((i != j) && (j != 1) && (j != (i + 1)))
for (k = 0; k < 6; k++)
if ((j != k) && (k != i) && (k != 2) && (k != (j + 1)))
for (l = 0; l < 6; l++)
if((l != k) && (l != j) && (l != i) && (l != 3) && (l != (k + 1)))
for (m = 0; m < 6; m++)
if ((m != l) && (m != k) && (m != j) && (m != i) && (m != 4) && (m != (l + 1)))
for (n = 0; n < 6; n++)
if((n != m) && (n != l) && (n != k) && (n != j) && (n != i) && (n != 5) && (n != (m + 1)))
{
//printf("%d %d %d %d %d %d\n", i, j, k, l, m, n);


fichier << i << " " << j << " ";
fichier << k << " " << l << " ";
fichier << m << " " << n << " ";


// On initialise le puzzle
InitTab(Puzzle, -1);


// On rempli le puzzle
Puzzle[0] = i;
Puzzle[1] = j;
Puzzle[2] = k;
Puzzle[3] = l;
Puzzle[4] = m;
Puzzle[5] = n;


nbc = NbCoup(Puzzle);


fichier << "Nombre de coup : " << nbc << "\n";


// Dans NombreCoup, on ajoute a a la case numéro nbc
NombreCoup[nbc] = NombreCoup[nbc] + 1;


nb++;
}


//printf("il y a %d possibilites !\n", nb);
fichier << "Il y a " << nb << " possibilites !\n";


for(i = 0; i < MAX_PIECE; i++)
{
fichier << "il y a " << NombreCoup[i] << " puzzle(s) à ";
fichier << i << " Coup(s)" << endl;
}


}
fichier.close();
//Pause();
return 0;
}