Forum Clubic

Programme Backtraking JAVA simple pb

Bonjour a tous, je suis étudiant et m’exerce en programmation simple.
Le but du programme est de générer tous les mots possibles avec 2a et 3b ( ex: aabbb ababb babab etc…) sans utiliser la recursion a l’aide d’un mantien de pile.
Voici le code :



import java.util.*;

public class Back{

	final int maxA=2; final int maxB=3;
	int na,nb;
	java.util.Stack<Character>pile;
	
	
	
	public Back(){
		
		this.na=this.nb=0;
		this.pile=new Stack<Character>();
		
	}
	
	public int nextChar(int pos, int nxt){                       //  Sert a établir le prochain charactere a insérer , a l'aide d' entiers :
		                                                                             //    0--> a     1--> b       (-1)--> rien
		if(nxt==0 && na<maxA) return 0;
		if(nxt==1 && nb>=maxB && na<maxA) return 0;
		
		if(nxt==1 && nb<maxB) return 1;
		if(nxt==0 && na>=maxA && nb<maxB) return 1;
		
		return -1;
	}
	

	public void genSol(){
		
  	int nxt=0; int pos=0;
		
		while(pos>=0){
			nxt=nextChar(pos,nxt);
			
			while(nxt>=0){
				
				if(nxt==0) pile.push('a'); else pile.push('b');
				
				if(nxt==0) na++; else nb++;
				
				if(na+nb==maxA+maxB) printSol();
				pos++;
				nxt=nextChar(pos,nxt);				
			}	
		
			if(!pile.empty()){
				
				Character c=pile.pop(); pos--;
				if(c=='a'){ na--;  nxt=1;} else{ nb--; nxt=-1;}                          /* Cette derniere étape est celle qui pose probleme   */
				
			}		
		}		
	}
	
	public void printSol(){
		
		Character[]t=new Character[this.pile.size()];
		for(int i=t.length-1; i>=0; i--) t[i]=this.pile.pop();
		
		for(int i=0; i<t.length; i++){
			System.out.print(t[i]);
			this.pile.push(t[i]);
		}
		System.out.println();	
	}

	public static void main(String[] args) {
		Back b=new Back();
		b.genSol();
	}
}

Le probleme : il me genere aabbb abbba et reste coincé en me generant a l’infini abbba . Je vois bien ou est le probleme, mais je ne sait pas le résoudre.
Si une ame genereuse pouvait m’éclaircir je l’en remercierais! :slight_smile:

Sur ce je vais manger, bon app a tous !

J’avais le même genre de conneries à faire, en C (un vrai langage donc ;))

Deux trois conseils :

  • tu fais certainement du Java 1.5/1.6, alors utilise un tableau de char[] t plutôt que Character[], ça évitera de mettre assez vite à plat la vm (char = 2octets à tout casser, Character = ref = 4octets/8octets). L’auto boxing va faire le cast tout seul, et avec un peu de chance, appeler la méthode charValue() [?] de la classe Character.

  • utilise ++i, ça ne sera que mieux , surtout si tu te sers pas de la post incrémentation

  • L’ensemble {mot ayant 2a, et 3b} est quelques peu infini (même, infini tout court). C’est un brin normal que ton programme ne s’arrête jamais. Je te suggère d’indiquer une taille maximale (genre 1024 caractères, je pense que ça prouvera que ton devoir est correctement fait).

Bon app’, et bon petit déjeuner aussi :smiley:
remarque en passant: la méthode “printSol” est un peu compliquée: tu n’as pas besoin de vider la pile pour voir son contenu puis la reremplir: utilise la méthode “get” de Stack (qui hérite de Vector)

SansNom> non à priori tous les mots font 5 lettres, donc on a déjà la limite :wink:

là pour passer d’un mot à l’autre tu ne mémorise que la variable “next” qui ne peut valoir que 1 ou -1 entre 2 mots. => que 2 cas de mots générés possibles

de plus, la condition de sortie porte sur la variable “pos” qui comporte uniquement la taille de la pile (de 0 à 5) et ne vaut donc jamais -1 (et ne sert pas à grand chose soit dit en passant ) => boucle infinie

J’ai du mal à comprendre l’algo utilsé, à mon avis le problème vient de là: essaye de bien décrire l’algo, et la démarche utilisée pour passer d’un mot au suivant(mémoriser la position des ‘a’, le mot entier …)

De plus, tu peux décrire cet algo même en récursif dans un premier temps, car on peut très bien dérécursifer un algo récursif après coup.
Edité le 05/10/2007 à 10:07

oups.

J’ai confondu avec 2n * a + 3n* b. Autant/Au temps pour moi :slight_smile:
Edité le 05/10/2007 à 11:48