Distance entre les mots - Colegiul National Emil Racovita (Cluj, Roumanie) Lycée d’Altitude (Briancon)

Titre du sujet
Distance entre les mots
Établissement
Colegiul National Emil Racovita (Cluj - Roumanie)
Année
2016-2017
Etablissement(s) jumelé(s)
Lycée d’Altitude (Briancon)
Résumé
Nous avons un dictionnaire dont tous les mots ont 5 lettres
parmi l'alphabet {A, B, C, D, E, F, G, H}.
Par exemple : ABCAB ou BDEFG
On vous demande de définir une distance d entre deux mots de ce dictionnaire. Une distance est une application qui a tout couple de mot du dictionnaire associe un nombre réel positif et qui vérifie :
- Pour tout X et Y dans le dictionnaire, d(X,Y)=d(Y,X)
- Pour tout X et Y dans le dictionnaire, d(X,Y)=0 ⇔ X=Y
- Pour tout X, Y et Z dans le dictionnaire, d(X,Z)<=d(X,Y)+d(Y,Z)