Discussion :

[Mika2008]

Bonjour, j'ai fais cet algo, mais j'ai un peu de mal à voir si ça correspond, quelqu'un peut me dire si il est correct et si il est possible d'optimisé ?

L'énoncé

Deux mots son anagrammes l'un de l'autre si l'un peut être obtenu par transposition des lettres de l'autre.
Exemple : "MARIE" et "AIMER" sont anagrammes l'un de l'autre ce qui n'est pas le cas pour "BON" et "BONBON".
écrire un algo qui entre deux chaines de caractères de lettres majuscules et sort "OUI" si ces deux chaines sont anagramme l'une de l'autre et "NON" dans le cas contraire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
ActionAnagramme
		Var CH1:CH2:C = Chaine de caractére
		LongCH1:LongCH2:i:j = Numerique
		Final1 : Final2 = Bouléen
 
Début
		Entrée CH1
		Entrée CH2
		LongCH1 = long(CH1)
		LongCH2 = long(CH2)
		i=j=0
		Final1 = Final2 = FALSE
 
	%Coparaison des longeurs des lettres%
	Si LongCH1 <> LongCH2
		Sortir "NON"
	Sinon	
		Tant que Final1 = false ou i <= LongCH1
			i = i + 1
			Final1 = False
			j = 0
			C = Schain(CH1, i , 1) % On copie une lettre du mot dnas la variable C %
				Tant que j <= LongCh2 ou Final2 = TRUE
					j = 1 + j 
					SI C = Schaine(CH2,j,1) % si la lettre contenu dans la variable c est trouver on arrete la boucle%
						Final2=TRUE
					FinSI
				FINTantQUE
			Si j  > Long(CH2) % si j > au nombre de lettre contenue dans la chaine de caractére alors les mots ne sont pas anagramme%
				Final1 = TRUE
			FinSI
		FINTantQUE
	FinSI
 
	Si Final1 = TRUE
		Sortir "NON"
	Sinon 
		Sortir "OUI"
	FinSI
 
FinAction

[Jedai]

C'est incorrect, tu ne vérifies pas si CH2 est une permutation des lettres de CH1 mais simplement si les lettres contenues dans CH1 existent dans CH2, par exemple si CH1 = "ooo" et CH2 = "non", ton algorithme déclarera que CH2 et CH1 sont des anagrammes.

Le plus simple pour vérifier si deux chaînes de caractères sont des anagrammes est de trier leur contenu et de vérifier si leurs contenus triés sont égaux.

Autres critiques :

• Tu utilises toujours long() pour la fonction Longueur(), ça va te jouer des tours.
• bouléen s'écrit Booléen (évite d'écorcher le nom de Bool please).

--
Jedaï

[Mika2008]

C'est incorrect, tu ne vérifies pas si CH2 est une permutation des lettres de CH1 mais simplement si les lettres contenues dans CH1 existent dans CH2, par exemple si CH1 = "ooo" et CH2 = "non", ton algorithme déclarera que CH2 et CH1 sont des anagrammes.

Ok merci de ta réponse, j'y ai passé du temps, et j'avais même pas pensé et vue ça

Le plus simple pour vérifier si deux chaînes de caractères sont des anagrammes est de trier leur contenu et de vérifier si leurs contenus triés sont égaux.

Stp tu as pas un texte pour développer ça, car je n'arrive pas à imaginer
comment trier le contenu de ces deux mots. En fais je n'arrive pas à imaginer comment faire ça

* Tu utilises toujours long() pour la fonction Longueur(), ça va te jouer des tours.

En fais, si sur le livre que j'ai pour apprendre l'algo, la définition dans mon livre
est long("ch").
Donc ok pour les prochaines fois et désolé pour monsieur Bool

[souviron34]

une simple recherche ici-meme t'aurait amene :

ici

http://www.developpez.net/forums/sho...ight=anagramme

ou

http://www.developpez.net/forums/sho...ight=anagramme

et quelques autres....

[Davidbrcz]

Deux mots sont des anagrames si il ya le même nombre de même lettres d'un mot à l'autre nom ?
Ca devient plus compliqué si tu dois vérifier que tes mots on un sens valide d'après un dico de référence.

[droggo]

Diu,

Stp tu à pas un texte pour développer sa, car je n'arrive pas à imaginer
comment trier le contenu de ces deux mots. En fais je n'arrive pas à imaginer comment faire sa

Il faut trier chaque chaîne séparément:

AIMER va donner AEIMR

et MARIE la même chose, ce qui montre que ce sont des anagrammes.

======================

Mais attention : dans les anagrammes, il ne faut jamais tenir compte des signes diacritiques (accents, cédille), et ne jamais faire la différence entre majuscules/minuscules.

En tenant compte de cette remarque, il faut donc faire :

- pour chaque chaîne, remplacer tous les caractères avec signe diacritique par leur équivalent simple (par exemple, éàe devient eaeA)

- passer toutes les lettres en majuscules ou minuscules, au choix

- et alors seulement

- trier les 2 chaînes

- comparer les 2 chaînes ainsi obtenues

- Si elles sont identiques, alors anagrammes = VRAI.

[Alp]

(trier signifie par exemple de classer les lettres de chacun des mots dans l'ordre alphabétique... ainsi si tu obtiens deux chaines identiques, hop c'est fini )

[b_reda31]

(trier signifie par exemple de classer les lettres de chacun des mots dans l'ordre alphabétique... ainsi si tu obtiens deux chaines identiques, hop c'est fini )

Bonjour,
Pour faire ça tu peux utiliser la fonction ORD:
Ord(a)<Ord(b)<...<Ord(z)

[droggo]

Gio,

Bonjour,
Pour faire ça tu peux utiliser la fonction ORD:
Ord(a)<Ord(b)<...<Ord(z)

Il s'agit ici d'algorithme, alors que ce genre de détail concerne l'implémentation.

[b_reda31]

Gio,

Il s'agit ici d'algorithme, alors que ce genre de détail concerne l'implémentation.

Je suis tout à fait d'accord avec vous .
je voulais juste préciser que dans le code ASCII les lettres sont classées "alphabétiquement",ce qui facilite donc le tri.

[droggo]

Fie,

Je suis tout à fait d'accord avec vous .
je voulais juste préciser que dans le code ASCII les lettres sont classées "alphabétiquement",ce qui facilite donc le tri.

D'accord, mais on parle d'algorithme, et l'algorithme n'a pas à présumer qu'on utilisera des chaînes de caractères encodées en ASCII, c'est là encore un détail qui ne concerne que l'implémentation.

[Alp]

C'est du chipotage tout ça, hein ?

L'auteur est-il satisfait des réponses ?

[Alp]

Fie,

Ça ne me fait pas râler, mais c'est l'occasion de rappeler que si on fait une supposition comme celle-là, il faut le préciser par une petite note au début de la description de l'algorithme, comme tu le précises, sinon il ne faut présupposer de rien.
Et dans le pseudo-code proposé n'apparaissait rien de tel.

pour b_reda31, ne t'en fait pas, il faut bien qu'on augmente notre nombre de posts.

Je ne vois pas de quoi tu veux parler pour le nombre de posts


Sinon, oui, un algo doit être décrit de manière aussi générique que possible, indépendamment de n'importe quel langage, framework ou je ne sais quoi.

[Davidbrcz]

Sinon, oui, un algo doit être décrit de manière aussi générique que possible, indépendamment de n'importe quel langage, framework ou je ne sais quoi.

Sauf bien sur mention contraire et explicite en début de sujet.
Mais je crois qu'on s'éloigne du sujet non ? A moins qu'il ne soit résolu.

[Alp]

Oui oui, sauf mention contraire, cf plus haut.
Et oui, on s'éloigne.

Mais je pense qu'il y a tous les éléments de réponse nécessaires à l'auteur du topic pour résoudre son problème.

[Mika2008]

merci de vos réponse, je suis toujours en trein d'essayer de résoudre, ce problème, je n'est pas eu le tps de me pencher dessus, mais je n'oublie pas le topic, dés que j'ai résolu,

oui on utlise ASCII, car dans le livre il nous apprenne sa.
et la fonction ord(), n'a pas été vue dans mon livre, donc je dois pas l'utiliser.



merci à vous


edit: je vais passer pour un idiot, mais j'ai pas réussi à faire l'algo, je chercher toujours à le résoudre :'(

j'ai essayer de prendre un mot et de le classer par odre alphabetique pour ensuite comparer les deux mots, ce qui donnerrais :

//Entrées la Chaine de caractére1
//Entrées la Chaine de caractére2
//classé les lettres du premier mot par ordre croissant
//classé les lettres du deuxième mot par ordre croissant
// si les deux mots en les même lettres c'est OUI
sinon NON

donc maintenant il faut que j'arrive à écrire un algo permettant de classer les lettres d'un mot par orde croissant!
donc voila ou j'en suis dans mon étape de résolution de cette algo.

j'avoue avoir du mal avec cette algo!
:'(

[b_reda31]

donc maintenant il faut que j'arrive à écrire un algo permettant de classer les lettres d'un mot par orde croissant!
donc voila ou j'en suis dans mon étape de résolution de cette algo.

j'avoue avoir du mal avec cette algo!
:'(

Salut Mika2008,pour ce qui est du classement des mots dans l'ordre alphabetique,le principe et le même que celui du tri d'un vecteur de valeurs numériques :

Pour chaque lettre comparer celle-ci avec tous ses successeurs.
Si l'un de ses successeur est inférieur * à la lettre courante alors Permuter.


(*): Pour ce qui est d'inférieur Il s'agit ici de détails d'implémentation .Tout dépend de la forme dont la chaine est en entrée.

[droggo]

Coe,

donc maintenant il faut que j'arrive à écrire un algo permettant de classer les lettres d'un mot par orde croissant!

Compte tenu de la petite taille des données à trier, tu peux sans problème te contenter d'utiliser un tri à bulles.

[pseudocode]

Compte tenu de la petite taille des données à trier, tu peux sans problème te contenter d'utiliser un tri à bulles.

Arg !

La meilleure solution (à mon avis) a déjà été donnée:

http://www.developpez.net/forums/sho...37&postcount=9

Complexité: O(2*L), avec L la taille d'une des 2 chaines

[Trap D]

Tiens, pendant qu'on y est, une méthode "à la C" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
%tab est un tableau d'entiers indicé par les lettres, initialisé à 0
pour chaque lettre l du premier mot faire
  tab(l) <- tab(l) + 1
fin pour
pour chaque lettre a du deuxième mot faire
  tab(l) <- tab(l) - 1
fin pour

Si a la fin tous les éléments du tableau sont nuls, les deux mots sont anagrammes sinon non.