Anagramme, arbre et recursivite

Soyez le premier à donner votre avis sur cette source.

Snippet vu 16 193 fois - Téléchargée 30 fois

Contenu du snippet

Bonjour,

Ce programme donne tous les anagrammes d'un mot y compris ceux inférieurs aux nombres de lettres. N'y connaissant strictement rien à la programmation avec des "arbres" (et debutant en C), j'ai essayé de réaliser le programme avec un fonction récursive.

Exemple : "nico" donne :

n ni nic nico nio nioc nc nci ncio nco
ncoi no noi noic noc noci i in inc inco
ino inoc ic icn icno ico icon io ion ionc
ioc iocn c cn cni cnio cno cnoi ci cin
cino cio cion co con coni coi coin o on
oni onic onc onci oi oin oinc oic oicn oc
ocn ocni oci ocin

Source / Exemple :


#include <iostream.h>
#include <stdlib.h>

void Arbre(char *word, int n, int lg, char *solution, int taille_solution)	// Fonction recursive
{
	char *comb;
	int i,j,k,m;

	if (lg!=0)
	{
		comb = (char *)malloc((lg)*sizeof(char)+1);		//Voir plus bas

		taille_solution++;		// On est descendu d'un étage dans l'arbre => taille de la solution +1
		for (i=0;i<lg;i++)		// Pour chaque lettre du nouveau mot on réalise autant d'arbre pour l'étage suivant
		{
			solution[n]=word[i];	// On ajoute la nouvelle lettre à la fin de la solution (n = étage)
			for (m=0;m<(taille_solution);m++) cout << solution[m];	// Affiche la solution en cours
			cout.flush() << "	";

			k=0;				// ICI on définit la nouvelle combinaison COMB avec les lettres restantes
			for (j=0;j<lg;j++)
			{
				if (j!=i)
				{
					comb[k] = word[j];	// Donc comb prend toutes les lettres restantes
					k++;
				}
			}

			Arbre(comb, n+1, lg-1, solution, taille_solution);	// Puis on descend d'un étage dans l'arbre en reinjectant le nouveau comb
		}
	}
	else taille_solution--;	// On remonte d'un étage dans l'arbre
}

void main()
{
	char *word;
	char *solution;
	char TEMP[25]={"########################"};

	int n_arbre=1;
	int taille_solution=0;
	int long_anagram;

	cout << "BIENVENU DANS ANAGRAMME\n\n"; cout << "Entrer l'anagramme : ";
	cin >> TEMP;

	for (long_anagram=0;TEMP[long_anagram]!='#';long_anagram++);	// Ici, on compte juste le nombre de caractères
	word = (char *)malloc(long_anagram*sizeof(char)+1);
	solution = (char *)malloc(long_anagram*sizeof(char)+1);			// Là ou seront stockées les différentes solutions
	for (int m=0;m<long_anagram;m++) word[m]=TEMP[m];

	cout << "RECHERCHE DES ANAGRAMMES DE " << word << "\n\n";

	Arbre(word,0,long_anagram-1,solution,taille_solution);			// On rentre dans le premier étage de l'arbre

	if (word) free(word);
	if (solution) free(solution);
}

Conclusion :


Bon, pour exemple, je rentre le mot "manger". Le programme appelle une première fois la fonction arbre(manger). On commence par la première lettre 'm' et on appelle de nouveau la fonction arbre(anger). Ainsi de suite. Quand il n'y a plus de lettre, on remonte d'un étage et on passe à la lettre suivante.

m a n ...............
(arbre anger) (arbre mnger) (arbre mager)
a n ...... ................. .......................
(arbre nger)
etc...

Bon, sinon le programme ne tient pas compte des lettres à répétition (ex : dada) et donne donc plusieurs fois le même anagramme...

A voir également

Ajouter un commentaire Commentaires
Messages postés
29
Date d'inscription
dimanche 4 mai 2003
Statut
Membre
Dernière intervention
15 juillet 2009

Pour ceux qui sont interéssé , j'ai adapté cet algorithme en java à l'adresse http://www.javafr.com/code.aspx?ID=37025
Messages postés
5
Date d'inscription
jeudi 23 septembre 2004
Statut
Membre
Dernière intervention
22 mars 2005

Bon, l'explication n'est pas très bien passé, tous les espaces ont été supprimé. J'espère que ca reste compréhensible néanmoins.... Peut-être plus clair comme ça :

m -> arbre (anger) -> a -> arbre(nger) -> ...
a -> arbre (mnger) -> m -> arbre (nger) -> ...
n ->....
g ->...
e -> arbre(mangr) -> m -> arbre (angr) -> ...
r ->...

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.