Anagramme, arbre et recursivite

0/5 (2 avis)

Snippet vu 16 723 fois - Téléchargée 32 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
grapevine Messages postés 29 Date d'inscription dimanche 4 mai 2003 Statut Membre Dernière intervention 15 juillet 2009
13 avril 2006 à 11:50
Pour ceux qui sont interéssé , j'ai adapté cet algorithme en java à l'adresse http://www.javafr.com/code.aspx?ID=37025
nico_rigo Messages postés 5 Date d'inscription jeudi 23 septembre 2004 Statut Membre Dernière intervention 22 mars 2005
16 mars 2005 à 17:27
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.