Débordement de pile irréparable ?

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Débordement de pile irréparable ?

C-user

Bonjour à tous,
c'est ma première demande sur le forum. Je ne m'y connais probablement pas assez, alors j'ai besoin de votre savoir :jap:

Voici mon souci : pour résoudre un problème de trajet sur une grille 10*20 (un genre de labyrinthe si on veut), j'ai tenté d'écrire un programme en c qui liste toutes les possibilités et sélectionne la réponse en fonction de différents critères (de l'énoncé). Du coup j'apprends (enfin ré-apprends ^^) le retour sur trace ...

Évidemment, comme à chaque récursion on met un tableau de 200 entiers en mémoire, et bien la pile déborde :pfff:

Après quelques tests je constate que la boucle 'for' n'est ouverte que 2 ou 3 fois, soit 2 ou 3 récursions, alors qu'il m'en faudrait ... un nombre ÉNORME !! (et pas beaucoup réductible...)

Voici mon code si ça peut aider :

Code :

/* B. Nicolas - fin juillet 2014 */
// inclusion de : stdio.h et stdbool.h
// fonction qui renvoit 0 si case adjacente vide, et modifie X ou Y si on peut y aller :
int deplace (int tab[10][20], int* pX, int* pY, int direction)
{
switch (direction)
{
/* up */ case 1:
if (*pX == 0) return 1;
else {
if (tab[*pX-1][*pY] == 0) return 0;
else return 1;
}
(*pX)--;
break;
/* do */ case 2:
if (*pX == 9) return 1;
else {
if (tab[*pX+1][*pY] == 0) return 0;
else return 1;
}
(*pX)++;
break;
/* L */ case 3:
if (*pY == 0) return 1;
else {
if (tab[*pX][*pY-1] == 0) return 0;
else return 1;
}
(*pY)--;
break;
/* R */ case 4:
if (*pY == 19) return 1;
else {
if (tab[*pX][*pY+1] == 0) return 0;
else return 1;
}
(*pY)++
break;
}
// cas d'erreur si rien n'a été fait :
printf("\n ERREUR dans la fonction 'deplace' \n" );
return 3;
}
bool estValide (int tab[10][20])
{
int i, j, r, X, Y;
/* on cherche la case dont le numéro est le plus grand, stocke ses coordonnées dans X et Y, et sa valeur dans r */
/* on teste les conditions, et si elles sont réunies on affiche la solution puis renvoit 'false' */
// récursion et backtracking :
int direction;
for(direction=1; direction<=4; direction++)
{
// si case vide donc autorisée ...
if (deplace (tab,&X,&Y,direction) == 0)
{
// ... on met cette valeur :
tab[X][Y] = r+1;
if(estValide(tab))
{
return true;
}
tab[i][j] = 0;
}
}
return false;
}
int main ()
{
int tab[10][20] = {{0}}; /* initialise tableau */
tab[7][0] = 1; /* case départ */
estValide(tab); /* résolution */
return 0;
}

Y a-t-il un moyen d'échapper à ce problème, par exemple en agrandissant la pile (quitte à monopoliser toute la machine) ou en modifiant le code pour remplacer la récursion ?
Je me suis renseigné bien sûr avant de vous solliciter, mais le peu de réponse que j'ai trouvées, et surtout comprises (comme les histoires de tail-récursivité) étaient sans effet...

Quelles que soient vos réponses je vous remercie infiniment pour votre aide :bounce:

Message cité 1 fois
Message édité par C-user le 30-07-2014 à 17:47:32

Publicité

tpierron

C-user a écrit :

Évidemment, comme à chaque récursion on met un tableau de 200 entiers en mémoire, et bien la pile déborde :pfff:

Haha, mauvaise supposition. Les tableaux sont toujours transmis par adresse aux fonctions (aucune copie n'est faite). C'est pour les "struct" qu'il y a une copie. Après j'ai un peu de mal à comprendre ce que fait ton algo, mais à mon avis si ton programme se plante, c'est probablement du à un buffer overflow.

dreameddeath

Il y a pleins de pbs dans ce code...

Il semble y avoir:
- pleins de variables non initialisées ( X,Y,i,j,r)
- des mélanges passage par valeur / pointeur s ( la fonction deplace ne deplace rien pour moi car X et Y ne sont jamais modifiées)
- l'init du tableau qui n'initialise que la case [0,0]

Les bases du langage lui même semblent être à revoir car la le code ne fait pas ce que tu veux ( pire il fait aléatoirement n'importe quoi)

ddr555

essaye de faire des pointeurs sur tableau plutôt qu'un tableau directement. la pile, tu ne pourras pas l'agrandir. c'est surement la multiplication d'appels récursifs qui la fait exploser. faut voir de ce coté là si y'a pas un soucis

ddr555

je crois que j'ai compris. ta fonction estvalide recherche toutes les possibilités. mais tu ne l'empêches pas de rechercher là où tu as déjà cherché. donc il n'y a aucune limite. il faut faire en sorte de n'aller que dans un sens de recherche lorsque tu appelles cette fonction

rufo

Pas me confondre avec Lycos!

Pour info, tout algo récursif peut être transformé en algo itératif. L'algo itératif est généralement plus rapide (car pas d'appels successifs à la fonction et empilement du contexte) et on maîtrise mieux les critères d'arrêt, évitant le buffer overflow.

---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta

C-user

Merci beaucoup à tous pour votre oeil neuf. Alors dans l'ordre :

@tpierron : ah oui c'est vrai, bien vu ^^
@dreameddeath : bases acquises voyons, je sais initialiser des variables ne t'inquiète pas (de toute façon le compilo me prévient :whistle: ).
Pour les pointeurs vs adresse, effectivement mes cours remontent un peu, mais de ce que j'ai revu ça devrait aller non ? On a une variable X passée en paramètre, on en stocke l'adresse dans un pointeur [int* pX = &X], et plus tard pour modifier X on fait [*pX = X+1] par exemple pour ajouter 1 à la variable d'entrée (au passage : si j'ai bon on a bien modifié X). > Y a-t-il encore une erreur ?
Init du tableau : en mettant un seul 0 ça remplit tout le tableau de zéros, bien pratique
@ddr555 : Un tableau n'est-il pas déjà un genre de pointeur (pointant sur la 1ère case puis avance dans les cases mémoires) ? Enfin bref je ne connais sûrement pas assez les nuances dans la théorie. Ça a l'air pas mal comme idée mais je vois pas trop ... tu voudrais détailler pour moi ? :jap: Sinon pour "estValide" le but est bien de tout tester, en imposant des conditions pour n'afficher que LE bon chemin.
@rufo : Jackpot, j'ai lu un article là-dessus, et même si le temps d'exécution est pas mon problème, c'est surtout le fait de ne pas stocker à chaque étape qui m'intéresse ! Par contre même en sachant que c'est théoriquement possible, je n'ai aucune idée sur comment faire la transformation... Pour du backtracking aussi c'est possible ?? :pt1cable:

Encore merci à tous pour vos conseils, et n'hésitez pas à continuer :hello:

Message cité 1 fois

gilou

Modérateur
Modzilla

C-user a écrit :

Merci beaucoup à tous pour votre oeil neuf. Alors dans l'ordre :
@dreameddeath : bases acquises voyons, je sais initialiser des variables ne t'inquiète pas (de toute façon le compilo me prévient :whistle: ).
Pour les pointeurs vs adresse, effectivement mes cours remontent un peu, mais de ce que j'ai revu ça devrait aller non ? On a une variable X passée en paramètre, on en stocke l'adresse dans un pointeur [int* pX = &X], et plus tard pour modifier X on fait [*pX = X+1] par exemple pour ajouter 1 à la variable d'entrée (au passage : si j'ai bon on a bien modifié X).
Encore merci à tous pour vos conseils, et n'hésitez pas à continuer :hello:

Pas du tout:
Quand tu fais
int deplace (int tab[10][20], int X, int Y, int direction)
ton paramètre X est passé par copie. Donc X contient une copie de la valeur de la variable passée, et son adresse n'est pas celle de la valeur.
int* pX; pX = &X;
ne fait alors que prendre l'adresse de la copie et non pas de l'original, qui ne sera donc pas modifiée.

Ce que tu voulais probablement faire, c'était:
int deplace (int tab[10][20], int *X, int *Y, int direction)
avec un appel
deplace(tab, &X, &Y, direction);
A+,

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

C-user

Bon sang, mais c'est bien sûr !

Je modifie dans le premier message, on n'a qu'à dire que ma mémoire m'a fait défaut
Merci beaucoup en tout cas

Ce qui nous donne :

Code :

int deplace (int tab[10][20], int* pX, int* pY, int direction)
{
...
...
(*pX)--;
...
}

Et l'appel :

Code :

deplace (tab,&X,&Y,direction)

Message édité par C-user le 30-07-2014 à 17:49:59

C-user

Alors tout le monde, avez-vous encore des idées ?

Je ne vois pas du tout comment se passer dans cet algo de la récursion, qui pourtant pose tant de problèmes

Vous voulez bien m'aider encore ? <3

Publicité

gilou

Modérateur
Modzilla

Code :

switch (direction)
{
/* up */ case 1:
if (*pX == 0) return 1;
else {
if (tab[*pX-1][*pY] == 0) return 0;
else return 1;
}
(*pX)--;
break;
/* do */ case 2:
if (*pX == 9) return 1;
else {
if (tab[*pX+1][*pY] == 0) return 0;
else return 1;
}
(*pX)++;
break;
/* L */ case 3:
if (*pY == 0) return 1;
else {
if (tab[*pX][*pY-1] == 0) return 0;
else return 1;
}
(*pY)--;
break;
/* R */ case 4:
if (*pY == 19) return 1;
else {
if (tab[*pX][*pY+1] == 0) return 0;
else return 1;
}
(*pY)++
break;
}

Ben déjà la je ne sais pas ce que tu veux faire (et ça coute rien de bien indenter et de mettre des blocs partout), mais clairement tu vas jamais passer dans le code avec (*pX)--; et ses potes, vu que tu auras toujours un return avant d'atteindre ce type de ligne...
A+,

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

C-user

Au temps pour moi il y a une coquille !

Voilà le cas 1 corrigé, indenté, et explicité :

Code :

// si case adjacente vide, modifie X ou Y, et renvoit 0 (sinon renvoit 1) :
int deplace (int tab[10][20], int* pX, int* pY, int direction)
{
switch (direction)
{
// HAUT :
case 1:
{
// si X vaut 0 on est en haut du tableau, donc on ne peut pas monter
plus => renvoit 1
if (*pX == 0)
{
return 1;
}
else
{
// sinon on regarde si la case située juste au-dessus ("X-1" ) est
libre, ie si la case contient 0
if (tab[*pX-1][*pY] == 0)
{
// si elle est libre, on peut y aller => on modifie X et
on renvoit 0
(*pX)--;
return 0;
}
else
{
// si elle n'est pas libre, on ne modifie pas X
return 1;
}
break;
}

En fin de compte la fonction se comporte comme une booléenne (0/1), et en plus si 0 elle modifie soit X, soit Y, c'est-à-dire qu'elle déplace le curseur sur la grille.

gilou

Modérateur
Modzilla

Pour continuer à comprendre ton code, et ses appels récursifs, c'est la fonction récursive qu'il faudrait corriger:
bool estValide (int tab[10][20])
{
int i, j, r, X, Y;
/* on cherche la case dont le numéro est le plus grand, stocke ses coordonnées dans X et Y, et sa valeur dans r */
/* on teste les conditions, et si elles sont réunies on affiche la solution puis renvoit 'false' */
// récursion et backtracking :
int direction;
for(direction=1; direction<=4; direction++)
{
// si case vide donc autorisée ...
if (deplace (tab,&X,&Y,direction) == 0)
{
// ... on met cette valeur :
tab[X][Y] = r+1;
if(estValide(tab))
{
return true;
}
tab[i][j] = 0;
}
}
return false;
}

Vu que ni i ni j, ni r ne sont initialisés.
L'emploi de i et j est d'ailleurs incompréhensible dans ce code, et r, s'il était initialisé, n"est jamais modifié...

En ce qui me concerne, je supprimerais déplace dont je n'aime pas l'effet de bord et je collerais directement ce qu'il faut dans est valide

Code :

//
int direction;
for (direction = 1; direction <= 4; direction++) {
bool deplace = false;
switch (direction) {
case 1: // haut
if (X > 0 && tab[X-1][Y] == 0) {
X--;
deplace = true
}
break;
case 2: // bas
if (X < 9 && tab[X+1][Y] == 0) {
X++;
deplace = true;
}
break;
case 3: // gauche
if (Y > 0 && tab[X][Y-1] == 0) {
Y--;
deplace = true;
}
break;
case 4: // droite
if (Y < 19 && tab[X][Y+1] == 0) {
Y++;
deplace = true;
}
break;
}
if (deplace) {
tab[X][Y] = r+1;
.......
}

A+,

Message édité par gilou le 05-08-2014 à 15:06:38

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

C-user

Pardon d'insister mais toutes les variables utilisées sont bien initialisées, dès la première ligne :

Code :

bool estValide (int tab[10][20])
{
int i, j, r, X, Y;

Et le couple i/j sert essentiellement à ça :

Code :

// cherche case dont le numéro est le plus grand :
r = 1;
for(i=0; i<10; i++)
{
for(j=0; j<20; j++)
{
if (tab[i][j] > r)
{
X=i;
Y=j;
r = tab[X][Y];
}
}
}

Code :

// récursion et backtracking :
int direction;
for(direction=1; direction<=4; direction++)
{
// si case libre donc autorisée ...
if (deplace (tab,&X,&Y,direction) == 0)
{
// ... on l'enregistre en tant que case suivante :
r++;
tab[X][Y] = r;
if(estValide(tab))
{
return true;
}
tab[i][j] = 0;
}
}

Voilà. Je ne pensais pas être si brouillon pour vous autres relecteurs, même si c'est souvent le cas quand on lit le code d'un autre.
Merci Gilou

Message cité 1 fois

C-user

Au fait, l'effet de bord de 'deplace' est voulu : en modifiant les coordonnées de la case ciblée, elle permet d'avancer dans la grille.

J'imagine que c'est la sortie de route qui te fait peur, et à moi aussi quand j'ai écrit l'algo. C'est pourquoi avant de faire le moindre changement, la fonction vérifie qu'on n'a pas atteint le la ligne extérieure dudit tableau (d'où les tests X=0 ou 9 et Y=0 ou 19).

J'espère que ça ne te gênera pas trop

Message cité 1 fois

ddr555

elles sont déclarées, mais pas initialisées, c'est à dire que tu leur donnes une valeur

Message édité par ddr555 le 05-08-2014 à 16:18:56

gilou

Modérateur
Modzilla

C-user a écrit :

La sortie de route (ie vérification des paramètres aux limites) est un code standard et n'a aucune raison de faire peur.
Mais il n'y a aucune raison de passer par une fonction a effet de bord alors que le code de ce qui est fait est si direct, c'est une couche de complication inutile.

A+,

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

gilou

Modérateur
Modzilla

C-user a écrit :

Pardon d'insister mais toutes les variables utilisées sont bien initialisées, dès la première ligne :

Code :

bool estValide (int tab[10][20])
{
int i, j, r, X, Y;

Ceci est une déclaration et non une initialisation
Par contre

C-user a écrit :

Et le couple i/j sert essentiellement à ça :

Code :

// cherche case dont le numéro est le plus grand :
r = 1;
for(i=0; i<10; i++)
{
for(j=0; j<20; j++)
{
if (tab[i][j] > r)
{
X=i;
Y=j;
r = tab[X][Y];
}
}
}

Quant à la variable r, elle a bien un rôle : ça permet de reconnaître la dernière case du chemin déjà tracé (r le plus grand), et on l'incrémente à chaque appel.
... Ceci dit, effectivement je ne l'ai pas bien incrémentée :cry:

Voilà. Je ne pensais pas être si brouillon pour vous autres relecteurs, même si c'est souvent le cas quand on lit le code d'un autre.
Merci Gilou

Ici on a effectivement des affectations, mais ce code ne figurait nulle part dans ce que tu avais posté auparavant.
Si tu veux qu'on comprenne ce qui ne va pas dans ton code, peut être faudrait il poster un code complet et non des bribes.

A+,

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

C-user

Ah oui j'ai toujours confondu initialiser et déclarer pour le c, tout simplement parce que la nuance à mon petit niveau n'a jamais eu que peu d'importance ..

Citation :

peut être faudrait-il poster un code complet et non des bribes.

Effectivement j'ai pas mal hésité dans mon premier message entre d'une part tout poster et vous noyer dans les détails de l'énoncé, et d'autre part "masquer" (synthétiser) comme je l'ai fait les petites fonctions qui n'étaient pas censées poser problème à l'exécution. Je comprends que l'absence des détails de ce paragraphe gêne la compréhension vu que je réutilise un peu ces variables, mais je ne peux pas tout poster (je pense surtout à ces quelques lignes simples qui testent les conditions, mais qui n'apporteraient rien pour le coup).

Maintenant, je pense également que le problème n'est pas là.

Citation :

Si tu veux qu'on comprenne ce qui ne va pas dans ton code

Justement, je suis désormais à peu près certain que ce n'est pas un problème de "langage", mais plutôt de méthode ; ainsi (et à part les erreurs de débutant que vous m'avez gentiment corrigées) je pense connaitre suffisamment les bases du c pour écrire ce que j'ai en tête, l’enchaînement des étapes, mais que cette façon de traiter l'énoncé n'est pas pensé de la bonne manière.
Je ne sais pas si ce que je raconte est bien exprimé, vous aurez saisi l'idée :pt1cable:

Ma faible expérience ne me permet pas encore de prendre le recul nécessaire afin de modifier globalement (et si possible efficacement) l'angle d'attaque choisi de prime abord. Je n'ai pas étudié l'ensemble des façons de faire. Le retour sur traces me parlait pas mal suite à un TP réalisé cette année (pour résoudre des labyrinthes), c'est donc par là que j'ai commencé mes recherches (enfin c'est un bien grand mot !).

Concrètement, un prof m'a dit : "les récursions c'est un joli jouet théorique mais à bannir de la programmation efficace".
Avec votre expérience et votre recul, comment attaqueriez-vous le problème ?

PS : je vous remercie pour votre patience avec moi, et désolé pour le pavé ^^

Message cité 1 fois

Yonel

Monde de merde !

C-user a écrit :

Ah oui j'ai toujours confondu initialiser et déclarer pour le c, tout simplement parce que la nuance à mon petit niveau n'a jamais eu que peu d'importance ..

Pourtant elle est fondamentale, et encore plus en C. Dans la plupart des langages maintenant on s'en fiche, mais ici non. En C, par défault, les variables ne sont pas initialisées. Passe ta souris au-dessus de X au premier appel de deplace() tu vas voir des valeurs bizarres genre -32761, puis un segmentation fault.

Mais j'ai l'impression que le problème de base n'est pas le C, mais plutôt l'algo. Tu veux pas écrire en pseudo code ce que tu essayes de faire ?

Message cité 1 fois

gilou

Modérateur
Modzilla

Citation :

Concrètement, un prof m'a dit : "les récursions c'est un joli jouet théorique mais à bannir de la programmation efficace".

C'est juste faux si la récursion en question est de la tail recursion.

Bon, en regardant plus loin dans votre code, il manque un test d'arrêt final dans votre fonction récursive
Par exemple (si j'ai bien compris, l'algo va numéroter de manière croissante toute les cases, sauf la case initiale a valeur 1):
if (r == 10 * 20) { return true; }

D'autre part, votre ordre de parcours pour chercher une case a numéroter haut bas gauche droite n'est pas très efficace (sur quelques tests que j'ai effectué). L'ordre haut gauche bas droite trouve une solution beaucoup plus rapidement.
L'algo a l'air de croitre de manière exponentielle en fonction du nb de cases. Sur ma bécane (vieille et poussive), avec un rectangle 16x10 la solution est quasi instantanée, avec un rectangle 18x10, ça prend de 2 a 3 mn, et je n'ai pas eu la patience de tester avec un rectangle 20x10.

A+,

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

gilou

Modérateur
Modzilla

Yonel a écrit :

Mais j'ai l'impression que le problème de base n'est pas le C, mais plutôt l'algo. Tu veux pas écrire en pseudo code ce que tu essayes de faire ?

Son algo (tel qu'actuellement donné dans son code) numérote de manière croissante les cases d'un tableau rectangulaire. Il part de la case avec le plus grand numero r (au premier pas, c'est la case initialisée a 1 qui est trouvée) et cherche une une case a 0 autour. S'il en trouve une, il y met r+1 et s'appelle récursivement. Si l'appel revient a vrai (ie il a pu numéroter récursivement le reste du tableau), il retourne avec vrai et sinon, il remet la case trouvée a 0 et cherche une autre case voisine a numéroter pour faire la même chose. Si aucune case voisine ne convient, il revient avec faux.

A+,

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

C-user

Promis je fais attention maintenant :ange:

Relis un peu les derniers messages, tu verras que X est bien ... initialisée ^^ ... => On cherche la case dont le contenu est le nombre le plus élevé (au premier appel c'est la case départ, qu'on a initialisée à 1), et une fois qu'on l'a trouvée :
- on stocke ses coordonnées dans X et Y
- on stocke sa valeur dans r (donc on commence par r=1, puis incrémenté à chaque appel).

Citation :

j'ai l'impression que le problème de base n'est pas le C, mais plutôt l'algo

Jackpot !

VOICI LE CODE COMPLET :

Code :

#include <stdio.h>
#include <stdbool.h>
void affiche (int tab[10][20])
{
int i, j;
printf("\n " );
for(i=0; i<10; i++)
{
for(j=0; j<20; j++)
{
if (tab[i][j] == 0)
{
printf(" ." );
}
else
{
if (tab[i][j] < 10)
{
printf(" " );
}
printf("%d", tab[i][j]);
}
}
printf("\n " );
}
printf("\n" );
}
// renvoit 0 si case adjacente vide, et modifie X ou Y si on peut y aller :
int deplace (int tab[10][20], int* pX, int* pY, int direction)
{
switch (direction)
{
// HAUT :
case 1:
// si X vaut 0 on est en haut du tableau, on ne peut plus monter :
if (*pX == 0)
{
return 1;
}
else
{
// sinon on regarde si la case cituée juste au-dessus est libre :
if (tab[*pX-1][*pY] == 0)
{
// si elle est libre, on peut y aller => on modifie X
(*pX)--;
// ... et on renvoit 0:
return 0;
}
else
{
// si elle n'est pas libre, on ne modifie pas X
return 1;
}
}
break;
// BAS :
case 2:
if (*pX == 9)
{
return 1;
}
else
{
if (tab[*pX+1][*pY] == 0)
{
(*pX)++;
return 0;
}
else return 1;
}
break;
// GAUCHE :
case 3:
if (*pY == 0)
{
return 1;
}
else
{
if (tab[*pX][*pY-1] == 0)
{
(*pY)--;
return 0;
}
else return 1;
}
break;
// DROITE :
case 4:
if (*pY == 19)
{
return 1;
}
else
{
if (tab[*pX][*pY+1] == 0)
{
(*pY)++;
return 0;
}
else return 1;
}
break;
}
// cas d'erreur si rien n'a été fait :
printf("\n\n\n ERREUR dans la fonction 'deplace' \n\n\n" );
return 3;
}
// fonction qui vérifie que toutes les cases d'intérêt de l'énoncé sont traversées par le chemin :
bool toutesLesLettresSontPrises (int tab[10][20])
{
// ici je crée plein de petites variables qui retiennent le numéro de chaque case
int A = tab[?][?], H = tab[?][?], N = tab[?][?], T = tab[?][?],
B = tab[?][?], I = tab[?][?], O = tab[?][?], U = tab[?][?],
C = tab[?][?], J = tab[?][?], P = tab[?][?], V = tab[?][?],
D = tab[?][?], K = tab[?][?], Q = tab[?][?], W = tab[?][?],
E = tab[?][?], L = tab[?][?], R = tab[?][?], X = tab[?][?],
F = tab[?][?], M = tab[?][?], S = tab[?][?], Y = tab[?][?],
G = tab[?][?];
// ainsi, "toutes les cases sont incluses" <=> "aucune ne vaut zéro"
if(A*B*C*D*E*F*G*H*I*J*K*L*M*N*O*P*Q*R*S*T*U*V*W*X*Y != 0)
{
return true;
}
else return false;
}
bool estValide (int tab[10][20])
{
int i, j, r, X, Y;
// cherche case dont le numéro est le plus grand :
r = 1;
for(i=0; i<10; i++)
{
for(j=0; j<20; j++)
{
if (tab[i][j] > r)
{
X=i;
Y=j;
r = tab[X][Y];
}
}
}
// [SORTIE] quand les conditions de l'énoncé sont réunies
// (NB : ici on peut modifier à loisir les conditions pour avoir le résultat souhaité) :
/// CONDITION 1 : rang 84 atteint (longueur du chemin)
if (r == 85)
{
printf("\n Rang 84 atteint," );
/// CONDITION 2 : sur la case finale
if((X != /* X de l'arrivée */) || (Y != /* Y de l'arrivée */))
{
printf(" mais pas sur la bonne case ...\n" );
}
else
{
printf(" et au bon endroit," );
/// CONDITION 3 : parcourt toutes les lettres :
if (toutesLesLettresSontPrises(tab))
{
printf(" et passe par toutes les lettres !!\n" );
affiche (tab);
}
else printf (" mais ne passe pas par toutes les lettres :(\n" );
}
return false;
}
// récursion et BACKTRACKING:
int direction;
for(direction=1; direction<=4; direction++)
{
// si case vide, ie autorisée ...
if (deplace (tab,&X,&Y,direction) == 0)
// Rq : on ne sort jamais du tableau grâce aux vérifs de deplace !
{
// ... on enregistre la valeur :
r++;
tab[X][Y] = r;
// et on continue l'arbre des possibilités une case plus loin :
if(estValide(tab))
{
return true;
}
// si on est arrivé au dernier noeud, on réinitialise la case à 0 :
tab[i][j] = 0;
}
}
// et on renvoie 'false' pour remonter au noeud/choix précédent :
return false;
}
int main ()
{
// déclare et initialise tableau :
int tab[10][20] = {{0}};
// initialise case départ :
tab[7][0] = 1;
// résolution :
estValide(tab);
return 0;
}

Voilà, j'espère que ça vous éclaire !

C-user

Gilou a parfaitement expliqué, merci à toi !

Citation :

il manque un test d'arrêt final dans votre fonction récursive

Effectivement, il y en a un dans le code complet (comme on cherche un chemin de longueur fixe 84, dès que cette longueur est atteinte on sort).

Citation :

D'autre part, votre ordre de parcours pour chercher une case a numéroter haut bas gauche droite n'est pas très efficace (sur quelques tests que j'ai effectué). L'ordre haut gauche bas droite trouve une solution beaucoup plus rapidement.

:heink: :heink: Très étonnant ça ! Je ne cherche pas à tout prix la vitesse mais pourquoi pas, il suffira que je change la fonction... ferai ça un d'ces quatre.

Citation :

Sur ma bécane (vieille et poussive), avec un rectangle 16x10 la solution est quasi instantanée, avec un rectangle 18x10, ça prend de 2 a 3 mn

Ah bah m****, c'est pas la première fois que ça me fait le coup !
Alors cette fois je suis convaincu qu'on peut y arriver, merci :wahoo:

Message édité par C-user le 06-08-2014 à 12:13:03

gilou

Modérateur
Modzilla

Citation :

Très étonnant ça ! Je ne cherche pas à tout prix la vitesse mais pourquoi pas, il suffira que je change la fonction... ferai ça un d'ces quatre.

Ça me semblait pas logique, et j'ai compris pourquoi: l'implémentation de l'algo est foireuse!
Faire (*pX)--; pour aller au dessus puis (*pX)++; pour aller en dessous, ca marche pas...
Avec votre algo, si vous êtes allé au dessus, quand vous voulez aller au dessous, en fait, vous revenez à la position de départ...

A+,

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

C-user

Citation :

Faire (*pX)--; pour aller au dessus puis (*pX)++; pour aller en dessous

Je vois, mais on ne fais jamais les deux en principe :
1. après chaque déplacement (après chaque "(*pX/Y)++/--" ) on a un 'return' qui clôt la fonction, donc déjà on ne peut pas faire les deux lors d'un même appel de 'deplace'
2. si on tente de monter d'une case par un "deplace (tab,*px, *pY, 1)", alors il se présente deux cas :
2.1. la case n'est pas libre, tab[][] != 0, et dans ce cas on ne monte pas (false), et il nous reste les autres directions à tester.
2.2. la case est libre, on y va. Dans ce cas il est impossible à l'appel suivant de redescendre, car la case est déjà remplie !

En fait la fonction 'deplace' a son rôle dans le retour sur trace (par sa construction et sa gestion des directions qui autorise la boucle 'for'), elle permet également de connaitre à chaque étape la longueur du chemin, mais elle s'assure surtout qu'à aucun moment le serpent ne se mordra la queue :jap:

C-user

À tout hasard, je vous fais part des pistes explorées en parallèles, en espérant que ça inspire quelqu'un :whistle:
Ça ne mène pas à la solution comme ça mais comme j'aime les chiffres ...

Alors, si on note les mouvements effectués sur le trajet idéal, toujours de 1 à 4, on obtient une combinaison à 84 chiffres (tous de 1 à 4). J'essaie d'en extraire des infos.

On sais qu'il y a 84 chiffres. Or, pour aller de la case départ à la case arrivée, il faut en tout aller de 18 cases vers la droite (on note GD=18), et de 2 cases vers le bas (HB=2). En gros c'est la distance de Manhattan...

on note A le nombre de 1, B de 1, C de 3, D de 4 dans la combinaison
Ça veut donc dire qu'il faut : GD = D-C = 18
HB = B-A = 2
A+B+C+D = 84.

...
Ainsi on peut par exemple exprimer B, C et D en fonction de A.

C'est ce que j'ai fait => A ∈ [0;32] et C ∈ [0;32] avec A+C=32
B ∈ [2;34] et D ∈ [18;50] avec B+D=52

Tout ça nous permet d'exclure beaucoup de combinaisons, et il en reste quand même ... beaucoup ! :sarcastic:

gilou

Modérateur
Modzilla

Bon en tout cas, si vous avez toujours un débordement de pile, c'est que manifestement votre implémentation est viciée (au plus, on a 84 appels récursifs sur la pile, ce qui est minime).

En ce qui me concerne, j'aurais implémenté ce genre de chose ainsi:

Code :

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define RECT_WIDTH 10
#define RECT_HEIGHT 10
void print_table(int tab[RECT_HEIGHT][RECT_WIDTH])
{
int i, j;
for (i = 0; i < RECT_HEIGHT; i++) {
for (j = 0; j < RECT_WIDTH; j++) {
printf("%3d ", tab[i][j]);
}
printf("\n" );
}
}
bool resoudre(int tab[RECT_HEIGHT][RECT_WIDTH], int X, int Y, int currentLength, int exitX, int exitY, int exitLength)
{
tab[X][Y] = currentLength;
if (currentLength == exitLength) {
if (X == exitX && Y == exitY) {
if (/* vos criteres supplementaires */ true) {
return true;
}
}
return false;
}
// récursion et backtracking :
int direction;
for (direction = 1; direction <= 4; direction++) {
switch (direction) {
case 1:
if (X > 0 && tab[X-1][Y] == 0) {
if (resoudre(tab, X-1, Y, currentLength+1, exitX, exitY, exitLength)) {
return true;
}
tab[X-1][Y] = 0;
}
break;
case 2:
if (Y > 0 && tab[X][Y-1] == 0) {
if (resoudre(tab, X, Y-1, currentLength+1, exitX, exitY, exitLength)) {
return true;
}
tab[X][Y-1] = 0;
}
break;
case 3:
if (X < (RECT_HEIGHT-1) && tab[X+1][Y] == 0) {
if (resoudre(tab, X+1, Y, currentLength+1, exitX, exitY, exitLength)) {
return true;
}
tab[X+1][Y] = 0;
}
break;
case 4:
if (Y < (RECT_WIDTH-1) && tab[X][Y+1] == 0) {
if (resoudre(tab, X, Y+1, currentLength+1, exitX, exitY, exitLength)) {
return true;
}
tab[X][Y+1] = 0;
}
break;
}
}
return false;
}
int main ()
{
// données initiales
int tab[RECT_HEIGHT][RECT_WIDTH] = {{0}}; /* initialise tableau */
int initX = 2;
int initY = 0;
int exitX = 9;
int exitY = 9;
int length = 21;
// vérification des conditions initiales
if (initX < 0 || initY < 0 || exitX < 0 || exitY < 0 || initX >= RECT_HEIGHT || initY >= RECT_WIDTH || exitX >= RECT_HEIGHT || exitY >= RECT_WIDTH) {
printf("Erreur dans les coordonnees!\n" );
return 0;
} else if (length < 0) {
printf("Longueur de chaine negative!\n" );
return 0;
} else if (length > RECT_HEIGHT * RECT_WIDTH) {
printf("Pas de solution: Longueur de chaine trop grande!\n" );
return 0;
} else {
// calcul de la longueur minimum
int minLength = 1;
if (initX >= exitX) {
minLength += (initX - exitX);
} else {
minLength += (exitX - initX);
}
if (initY >= exitY) {
minLength += (initY - exitY);
} else {
minLength += (exitY - initY);
}
if (length < minLength) {
printf("Pas de solution: Longueur minimale necessaire; %d\n", minLength);
return 0;
}
}
// résolution et résultat
if (resoudre(tab, initX, initY, 1, exitX, exitY, length)) {
printf("Solution avec la case initiale (%d, %d), la case finale (%d, %d), et la longueur %d:\n\n", initX, initY, exitX, exitY, length);
print_table(tab);
} else {
printf("Pas de solution trouvee avec la case initiale (%d, %d), la case finale (%d, %d), et la longueur %d:\n\n", initX, initY, exitX, exitY, length);
}
return 0;
}

Bon, c'est une variante simplifiée de votre pb, avec un point de départ et un point d'arrivée et une longueur imposés (je me suis amusé a le tester avec un point intermédiaire atteignable ou non comme critère supplémentaire et non vos 26 points).
Ça marche sans pb mais c'est un algo exponentiel en la taille du tableau, et ça peut prendre trop longtemps (pour ma patience) a chercher une solution lorsqu'il n'y en a pas en 10x20 (en 10x16, c'est relativement correct comme temps d’exécution).

A+,

Message édité par gilou le 06-08-2014 à 22:54:33

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

C-user

Ouaip ça marche aussi bien sûr.

Je viens de faire le test chez moi de compiler et exécuter ton code, pas de soucis ça me sort une solution (et on pourrait s'arranger pour les avoir toutes).

En revanche pas d'amélioration pour le mien : toujours rien de notable à la compil, mais comme d'habitude le fameux :
a.out a cessé de fonctionner
Windows cherche une solution au problème...

Au fait, sérieusement, ça lui arrive de TROUVER une solution aux problèmes ? :lol:

Je ne vois pas pourquoi ça déconne comme ça : il n'y a que 2 ouvertures dans la boucle 'for' qui s'initient ! C'est rageant parfois

Message édité par C-user le 06-08-2014 à 23:39:44

gilou

Modérateur
Modzilla

Ben déjà, tracez le nb d'appels récursifs a votre routine estValide.
Pour voir si ça dépasse 84...

A+,

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

C-user

Tiens, je croyais avoir posté un message là-dessus, pas dû cliquer où il fallait...

Apparemment, 'estValide' se lance une seule fois. Elle appelle alors 'deplace' vers le haut (cas 1).

Je rajoute des balises dans la fonction, comme ça :

Code :

bool deplace (int tab[10][20], int* pX, int* pY, int direction)
{
printf("\n DEBUT DEPLACE" );
switch (direction)
{
case 1:
printf("\n entrée 'case 1'" );
if (*pX == 0)
{
return false;
}
else
{
printf("\n repere 1" );
if (tab[*pX-1][*pY] == 0)
{
printf("\n repere 2" );
(*pX)--;
return true;
}
else
{
return false;
}
}
break;

Et en console j'obtiens :

Citation :

DEBUT DEPLACE
entrée 'case 1'
repere 1

Il se passe quelque chose entre les repères 1 et 2 !

=> Y a-t-il un problème dans ma façon de tester la case du tableau ? Est-il interdit d'écrire comme ça avec un passage par adresse ??

Message édité par C-user le 07-08-2014 à 12:54:54

C-user

J'ai donc fait un test :

Code :

int lit_case_supra (int tab[10][20], int X, int Y)
{
int* pX = &X;
int* pY = &Y;
printf("\n Au-dessus de la case [%d;%d], il y a un %d.", X, *pY, tab[*pX-1][Y]);
return 0;
}
int main ()
{
// initialise tableau :
int tab[10][20] = {{0}};
tab[4][9] = 1;
tab[3][9] = 6;
lit_case_supra(tab, 4, 9);
return 0;
}

Et ici il n'y a aucun problème, le chiffre 6 apparaît bien en sortie...
_______________________________________________________________________

Ce soir je teste ton code en l'adaptant à mes dimensions (10*20). Le programme tourne depuis 3 heures. Tant pis pour ce soir :sleep:

Message édité par C-user le 08-08-2014 à 00:35:52

C-user

Cher Gilou, je crois bien qu'il y a dans ton code un souci avec le retour sur traces.

En effet en affichant le tableau à chaque étape on constate que la fonction avance, avance, avance, et quand elle arrive à un cul-de-sac (oui maintenant il y en a :whistle: ), au lieu de revenir aux choix précédents, elle s'arrête !
*pataper*
... Dis-moi ce que tu en penses :hello:

Spoiler :

À mon avis ça pourrait venir de ta construction de la récursion. Concrètement il faudrait renvoyer 'false' si plus aucune case n'est libre (cul-d'sac), et remettre à 0 après avoir testé resoudre(case suivante).

Message cité 1 fois

gilou

Modérateur
Modzilla

C-user a écrit :

Spoiler :

Possible, mais s'il y a maintenant des culs de sac, c'est que les specs initiales ont changé?
Parce que tel que c'est écrit, résoudre renvoie faux quand aucune case adjacente n'est libre, et cette sortie a faux va faire que la ligne suivante du code va être exécutée, et donc (sauf cas du premier appel), la case va être mise à 0.
Bon, ça ne mange pas de pain de rajouter un tab[X][Y] = 0; avant le return false final, mais à priori, ça me semblait inutile.

En fait l'écrire ainsi simplifierait les choses:

Code :

bool resoudre(int tab[RECT_HEIGHT][RECT_WIDTH], int X, int Y, int currentLength, int exitX, int exitY, int exitLength)
{
tab[X][Y] = currentLength;
if (currentLength == exitLength) {
if (X == exitX && Y == exitY) {
if (/* vos criteres supplementaires */ true) {
return true;
}
}
// Pour garder le point de départ a 1
if (currentLength != 1) {
tab[X][Y] = 0;
}
return false;
}
// récursion et backtracking :
int direction;
for (direction = 1; direction <= 4; direction++) {
switch (direction) {
case 1:
if (X > 0 && tab[X-1][Y] == 0) {
if (resoudre(tab, X-1, Y, currentLength+1, exitX, exitY, exitLength)) {
return true;
}
}
break;
case 2:
if (Y > 0 && tab[X][Y-1] == 0) {
if (resoudre(tab, X, Y-1, currentLength+1, exitX, exitY, exitLength)) {
return true;
}
}
break;
case 3:
if (X < (RECT_HEIGHT-1) && tab[X+1][Y] == 0) {
if (resoudre(tab, X+1, Y, currentLength+1, exitX, exitY, exitLength)) {
return true;
}
}
break;
case 4:
if (Y < (RECT_WIDTH-1) && tab[X][Y+1] == 0) {
if (resoudre(tab, X, Y+1, currentLength+1, exitX, exitY, exitLength)) {
return true;
}
}
break;
}
}
if (currentLength != 1) {
tab[X][Y] = 0;
}
return false;
}

Un exemple de conditions initiales aboutissant a cet arrêt alors qu'il ne devrait pas survenir m'aiderait a comprendre.
Parce que c'est surement reproductible en taille 10x16, qui ma machine aboutit a un résultat (solution ou pas de solution) en 1mn environ.

A+,

Message édité par gilou le 10-08-2014 à 00:27:44

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

C-user

Pour la "nouvelle" condition : le tracé ne doit pas se recouper, ça tu le savais, mais également il ne doit même pas revenir à son contact. C'est-à-dire que chaque case non-nulle #n (autre que départ et arrivée) doit être en contact avec exactement 2 cases non-nulles : #(n-1) et #(n+1).

J'ai pas trouvé de façon très futée de le faire : à chaque tour on remplit chaque case nulle jouxtant une case non-nulle d'un "- 1", qui représente un genre de mur (~ labyrinthe).

Dans la fonction d'affichage je représente les -1 par des symboles °° (degré), qui sont mal reconnus par le shell, affichant un carré hachuré.

_______

Ainsi en début de récursion, on met tous les "- 1", on teste 'deplace' (qui est alors limitée par ces murs), et le plus important lorsqu'on revient en arrière c'est de remettre les murs à "0", pour ne pas remplir toute la grille de murs...
Je teste encore tout ça, pas parfaitement au point, alors si tu as des suggestions surtout n'hésite pas

Publicité

FORUM HardWare.fr

Programmation

Débordement de pile irréparable ?

Sujets relatifs
Débordement d'une image en dehors de l'écran	[Java] Liste chaînée - Pile
erreur a supprimer	pile , la fonction qui depile ne marche pas [résolu]
Initialisation d'une pile de réseaux de neurones.	[REXX] Ecritures multiples à partir d'une pile ?
pile et file en pascale	allocation sur le tas vs pile
Tri shell d'une pile	pile et programme
Plus de sujets relatifs à : Débordement de pile irréparable ?

Page générée en 0.442 secondes