Sujet Précédent Sujet Suivant

Fonction multi-recursive en C

Fermé
J.K.ja - 23 nov. 2010 à 19:21
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 - 29 nov. 2010 à 22:27
Bonjour,

J'ai réalisé cette fonction récursive, mais malheureusement elle ne fonctionne que en conservant un unique appel récursif(peut importe lequel), sinon elle plante. Je n'ai aucune idée de pourquoi, je sèche, pourriez-vous me dire le problème car là....

void AfficheEspaces(int GrilleEcran[TailleMax][TailleMax],int GrilleNb[TailleMax][TailleMax],int Ligne,int Colone,int Taille)
{
GrilleEcran[Ligne][Colone]=('-'-'0');
if(Colone>0)
{
if(GrilleNb[Ligne][Colone-1]==0)
{
AfficheEspaces(GrilleEcran,GrilleNb,Ligne,Colone-1,Taille);
}
else
{
GrilleEcran[Ligne][Colone-1]=GrilleNb[Ligne][Colone-1];
}
}
if(Colone<Taille)
{
if(GrilleNb[Ligne][Colone+1]==0)
{
AfficheEspaces(GrilleEcran,GrilleNb,Ligne,Colone+1,Taille);
}
else
{
GrilleEcran[Ligne][Colone+1]=GrilleNb[Ligne][Colone+1];
}
}
if(Ligne<Taille)
{
if(Colone<Taille)
{
if(GrilleNb[Ligne+1][Colone+1]==0)
{
AfficheEspaces(GrilleEcran,GrilleNb,Ligne+1,Colone+1,Taille);
}
else
{
GrilleEcran[Ligne+1][Colone+1]=GrilleNb[Ligne+1][Colone+1];
}
}
if(GrilleNb[Ligne+1][Colone]==0)
{
AfficheEspaces(GrilleEcran,GrilleNb,Ligne+1,Colone,Taille);
}
else
{
GrilleEcran[Ligne+1][Colone]=GrilleNb[Ligne+1][Colone];
}
if(Colone>0)
{
if(GrilleNb[Ligne+1][Colone-1]==0)
{
AfficheEspaces(GrilleEcran,GrilleNb,Ligne+1,Colone-1,Taille);
}
else
{
GrilleEcran[Ligne+1][Colone-1]=GrilleNb[Ligne+1][Colone-1];
}
}
}
if(Ligne>0)
{
if(Colone<Taille)
{
if(GrilleNb[Ligne-1][Colone+1]==0)
{
AfficheEspaces(GrilleEcran,GrilleNb,Ligne-1,Colone+1,Taille);
}
else
{
GrilleEcran[Ligne-1][Colone+1]=GrilleNb[Ligne-1][Colone+1];
}
}
if(GrilleNb[Ligne-1][Colone]==0)
{
AfficheEspaces(GrilleEcran,GrilleNb,Ligne-1,Colone,Taille);
}
else
{
GrilleEcran[Ligne-1][Colone]=GrilleNb[Ligne-1][Colone];
}
if(Colone>0)
{
if(GrilleNb[Ligne-1][Colone-1]==0)
{
AfficheEspaces(GrilleEcran,GrilleNb,Ligne-1,Colone-1,Taille);
}
else
{
GrilleEcran[Ligne-1][Colone-1]=GrilleNb[Ligne-1][Colone-1];
}
}
}
}


14 réponses

Réponse 1 / 14
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 019
23 nov. 2010 à 22:19
Le principe de la récursivité veut qu'il y ait toujours un cas terminal aux appels récursifs, ce qui implique que chaque appel doit diminuer le degré de difficulté (par exemple décrémenter Taille)

On s'attendrait par exemple à avoir AfficheEspaces(..., Taille-1); dans les appels récursifs et une condition, if (Taille==0) return; qui assurerait la fin des appels.

Or ici, à chaque appel tu fais entre 2 et 4 nouveaux appels, qui en feront aux même entre et 4... et ce à l'infini ! Forcément ça plante...

De plus on ne sait pas ce que tu utilises comme premier appel, quelles valeurs pour Taille, Ligne, Colonne ?

Et puis des commentaires ne seraient pas superflus, que doit faire ton programme ?

PS. utilises les balises de codes pour conserver l'indentation, sinon on comprend rien !
2
Réponse 2 / 14
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 019
24 nov. 2010 à 07:03
Tu dis que la fonction fait un affichage, or il n'y a aucune instructions d'affichages !
De plus je ne vois pas en quoi ('-'-'0') permet de transformer un char... le résultat sera toujours -3
Mais tout ceci ne résout pas ta récursivité infinie... Quels sont tes paramètres d'entrée, et quelle est ta condition d'arrêt ?
1
Réponse 3 / 14
J.K.ja
23 nov. 2010 à 22:49
Merci de ta réponse KX,

Le but de la fonction est un affichage par la suite de la GrilleEcran (transformée en char d'où le " -'0' ")
cette fonction sert donc à "rendre visible" une partie de la GrilleNb (seulement la partie avec des 0 autours de l'endroit [Ligne][Colonne]
0
Réponse 4 / 14
J.K.ja
24 nov. 2010 à 17:26
La condition d'arrêt est GrilleNb[Ligne][Colone]!=0

en entrée je rentre 2 tableaux carrés d'entiers à 2 dimensions de taille Taille, et le repère d'une "case" de ces tableaux par [Ligne][Colone] (mes int)
0

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

Posez votre question
Réponse 5 / 14
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 019
24 nov. 2010 à 17:32
Comme je te l'ai dit, ton affectation ('-'-'0') donne toujours -3, et donc jamais 0 !
De plus tu ne fais jamais ce test GrilleNb[Ligne][Colone]!=0 ... donc tu boucles !
0
Réponse 6 / 14
J.K.ja
Modifié par J.K.ja le 24/11/2010 à 23:19
Dans ce cas, pourquoi lors d'un test avec seulement l'un des appels récursif (peut importe lequel, en mettant les autres en commentaire) cela fonctionne?

Parce-que là la fonction est bien sensée s'arrêter au } final et du coup passer à l'appel d'au "dessus", alors que là ca plante.
0
Réponse 7 / 14
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 019
24 nov. 2010 à 23:35
Le programme s'arrête au } s'il y arrive !

Prenons par exemple le cas où tu gardes juste le premier test.
Tu as if(Colonne>0) ... AfficheEspaces(...Colonne-1,Taille);
Dans ce cas, tu as bien une condition d'arrêt Colonne==0, qui est atteinte parce que tu diminues Colonne à chaque appel.

Mais si tu considères en même temps ton deuxième test if(Colonne<Taille) ... AfficheEspaces(... Colone+1,Taille);
Tu n'atteindras jamais ton }

Exemple simple Afficher(Colonne,Taille) avec ces deux tests.

On appelle Afficher(1,2)
1>0 donc le premier test lance Afficher(0,2)
1<2 donc le deuxième test lance Afficher(2,2)
Et on atteins }

Sauf qu'en fait dans Afficher(0,2) on a 1<2 donc on appelle Afficher(1,2)
De plus dans Afficher(2,2) on a 2>0 donc on appelle Afficher(1,2)

Donc je résume Afficher(1,2) appelle Afficher(0,2) qui appelle Afficher(1,2) qui appelle Afficher(0,2) qui appelle Afficher(1,2)... et au final tu n'atteins pas } car tu as toujours de nouveaux appels qui sont lancés !

Ce serait bien sûr différent si tu diminuais Taille au fur et à mesure et que tu t'arrêtais quand Taille=0...
0
Réponse 8 / 14
J.K.ja
25 nov. 2010 à 00:00
Je comprend bien pourquoi ca plante maintenant, merci de ton explication, mais du coup ca ne résous pas mon algo pour autant ^^

Prenons le autrement, comment peut-on faire pour parcourir un arbre (non pas binaire, mais à 8 fils) en s'arrêtant dès que la valeur du noeud est !=0 et en affichant la valeur de chacun des noeud par lequel on passe (incluant le !=0 )?
il faut d'abord afficher le noeud puis tester s'il est !=0 au quel cas on passe à ses fils mais ca donne quoi en C?
0
Réponse 9 / 14
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 019
25 nov. 2010 à 00:34
Pour ton algo, outre le fait qu'il plante, je n'ai toujours pas compris à quoi il servait...
Et si tu dis que c'est un arbre 8-aire, je comprends encore moins !!!
Je ne vois pas du tout le rapport avec ton code précédent !

Je ne sais pas trop ce qui serait le mieux en C, j'ai plutôt l'habitude du C++
Mais ça donnerait un truc à peu près comme ça (à vérifier) : 

struct Arbre
{
	int noeud;
	struct Arbre *fils[8];
}
Arbre;

Typiquement les conditions d'arrêts de la récursivité sur le parcours d'arbres ne se fait pas comme tu le dis sur la valeur des noeuds (noeud==0) mais sur la valeur du pointeur de l'arbre, qui soit est NULL, soit ne l'est pas.

Par exemple, une fonction qui calcule la somme des noeuds de l'arbre (à vérifier aussi) : 

int sommeNoeuds(struct Arbre *a)
{
	if (a==NULL)
		return 0;
	else
	{
		int i, s=a->noeud;
		for (i=0; i<8; i++)
			s+=sommeNoeuds(a->fils[i]);
		return s;
	}
}

Ici, même si je fais 8 nouveaux appels à sommeNoeuds dans le else, je réduis quand même mon problème car à chaque appel mon arbre est plus petit (je considère les fils).
Donc j'arriverai toujours, à un moment ou à un autre, à ma condition d'arrêt d'arbre NULL, ce qui fera que mon programme temine (à condition que l'arbre en soit bien un !)
De plus comme j'initialise s avec la valeur du noeud de l'arbre, j'aurai bien la somme des noeuds comme résultat.
0
Réponse 10 / 14
J.K.ja
25 nov. 2010 à 22:29
Je vais tenter de t'expliquer mieux ma fonction,
Prenons GrilleNb ainsi:
11000
91000
11000
00111
00191
Taille est donc = à 5 ici.
Si on passe en paramètre Ligne=1 et Colonne=3, je souhaite que GrilleEcran ressemble à ça:
_1- - -
_1- - -
_1- - -
__111
_____
_____
Les underscores étant là juste pour voir les espaces.

Mais je me rend bien compte que ce que j'avais fait ne convient pas car appel sans fin.
0
Réponse 11 / 14
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 019
25 nov. 2010 à 22:45
Quelle est la logique dans l'obtention de ce résultat ?
Tu disais 'cette fonction sert donc à "rendre visible" une partie de la GrilleNb (seulement la partie avec des 0 autours de l'endroit)'

Je m'attendrais plutôt à voir ceci (je ne garde que les nombres voisins d'un 0) 

11000      -1--- 
91000      -1---
11000      11--- 
00111      --111
00191      --1--

Remarque :
Je ne suis pas sûr que la récursivité soit vraiment intéressante, mais j'attends d'être sûr de ce que tu veux faire, c'est encore assez confus (n'hésite pas à mettre d'autres exemples)

Et quel rapport avec les arbres ?
0
Réponse 12 / 14
J.K.ja
25 nov. 2010 à 23:04
Précision: Je ne rentre dans la fontion que si grilleNb[ligne][colonne]=0

Prenons une grilleNb:
0019100
1121100
1910000
2322110
9293921
1229229
0011111
Taille=7 et GrilleEcran serait avec Ligne=2 et Colonne=4:
____1- -
___11- -
__1- - - -
___211-
______1
_______
_______

puis admettons qu'on rappel la fonction avec Ligne=6 et Colonne=0,GrilleEcran serait:
____1- -
___11- -
__1- - - -
___211-
______1
12_____
- -1____
0
Réponse 13 / 14
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 019
25 nov. 2010 à 23:19
Ok, je pense avoir compris, tu fais un jeu du démineur en gros...

Donc initialement ta GrilleEcran est totalement vide ('_' ou autre), puis tu appelles ta fonction sur une ligne ou une colonne (entre 0 et Taille-1) si cette position correspond à un 0 dans GrilleNb tu affiches un '-' dans GrilleEcran et tu propages les 0 sur tous les voisins et c'est là qu'est ton problème.

C'est tout de suite plus simple avec un exemple ^^
0
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 019
25 nov. 2010 à 23:33
Essaye plutôt quelque chose comme ceci (je n'ai pas vérifié) 

void afficheEspaces(char** grilleEcran, char** grilleNb, int ligne, int colonne, int taille) 
{
	if (ligne>=taille || ligne<0 || colonne>=taille || colonne<taille)
		return; // on a dépassé les limites de la grille

	if (grilleNb[ligne][colonne]=='0')
	{
		grilleEcran[ligne][colonne]='-';
		grilleNb[ligne][colonne]='a'; // je marque les cases déjà affichées par la lettre 'a'
		                              // quand on regardera cette case ultérieurement on ne la traitera plus		                            

		afficheEspaces(grilleEcran, grilleNb, ligne+1, colonne, taille); // je propage à droite
		afficheEspaces(grilleEcran, grilleNb, ligne-1, colonne, taille); // à gauche
		afficheEspaces(grilleEcran, grilleNb, ligne, colonne+1, taille); // en haut
		afficheEspaces(grilleEcran, grilleNb, ligne, colonne-1, taille); // en bas
	}
	else if (grilleNb[ligne][colonne]!='a') // si elle n'a pas été déjà traitée, c'est un chiffre >0
	{
		grilleEcran[ligne][colonne]=grilleNb[ligne][colonne]; // on l'affiche mais sans propager
	}
}
0
J.K.ja
29 nov. 2010 à 21:14
ta fonction --> error: conflicting types for 'afficheEspaces'
0
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 019
29 nov. 2010 à 21:25
J'ai changé int GrilleEcran[TailleMax][TailleMax], en char** GrilleEcran, idem pour GrilleNb.

Je pensais qu'il était plus logique de mettre char plutôt que int, pour le changement des [][] en **, je crois que c'était juste un problème de compilation mais je suis pas suffisamment au point en C pour savoir ce qu'il est vraiment correct d'utiliser.

Dans tous les cas ça ne change rien à l'algorithme...
0
J.K.ja
29 nov. 2010 à 21:39
J'avais bien vu et changé ca, mais ca change rien
0
Réponse 14 / 14
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 019
Modifié par KX le 30/11/2010 à 06:44
Bon j'ai fais un programme de test pour voir ce qui ne marchait pas...
J'ai repris un des exemples que tu avais donné.

Remarque :
J'ai dû modifier les deux premières lignes de mon code pour que ça tourne... 

#include <stdio.h>

#define TailleMax 7

void afficheEspaces(char grilleEcran[TailleMax][TailleMax],char grilleNb[TailleMax][TailleMax],int ligne,int colonne,int taille) 
{
	if (ligne>=taille || ligne<0 || colonne>=taille || colonne<0)
		return; // on a dépassé les limites de la grille
// ...
}

int main() 
{
	char GrilleNb[TailleMax][TailleMax]={'0','0','1','9','1','0','0','1','1','2','1','1','0','0','1','9','1','0','0','0','0','2','3','2','2','1','1','0','9','2','9','3','9','2','1','1','2','2','9','2','2','9','0','0','1','1','1','1','1'};
	char GrilleEcran[TailleMax][TailleMax];

	int i, j;
	for (i=0; i<TailleMax; i++)
	{
		for (j=0; j<TailleMax; j++)
			GrilleEcran[i][j]='.';
	}

	afficheEspaces(GrilleEcran,GrilleNb,2,4,TailleMax);

	for (i=0; i<TailleMax; i++)
	{
		for (j=0; j<TailleMax; j++)
			printf("%c",GrilleEcran[i][j]);
		printf("\n");
	}

	return 0; 
}

La confiance n'exclut pas le contrôle
0

Discussions similaires

Recherche multi exp dans pokémon heart gold
tom -
Estebalignon -

6 réponses
2eme multi exp?
sohanejeff30 -
missing you -

1 réponse
Pokémon SoulSilver multi exp
Randy62 -
rieulebg -

8 réponses
Multi Exp dans Pokemon Diamant
Tomoko -
lol -

63 réponses
Remplir une cellule (texte) en fonction d'une autre (texte).
SOMUM -
SOMUM -

4 réponses