Anagramme, arbre et recursivite

Commenter

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

S'inscrire maintenant

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.