recherche d'un algorithme comparaison des digits d'un nombre en base trois
Bonjour à tous,
tout d'abord j'espère que je suis dans la bonne section pour poser mes questions.
Voilà ce que je souhaite pour mon algorithme :
Entrée : ensemble des nombres en base trois successifs de 0 à n
Sortie : plus petit ensemble de nombres en base trois tel que n'importe quel nombre en base 3 compris entre 0 et n n'ait pas plus d'un digit différent des nombres présent dans l'ensemble de sortie.
Un petit exemple pour illustrer :
Je prends les nombres de 0 à 9 :
J'ai donc en entrée de mon algorithme :
{000,001,002,010,011,012,020,021,022}
en sortie :
{000,011,022}
Là l'exemple est très simple et je pourrai avoir plusieurs ensembles de sortie possibles mais mon objectif est de minimiser au maximum mon ensemble de sortie.
Etat de mes recherches :
J'ai d'abord fait un algorithme prenant comme premier nombre le nombre 0 puis éliminant tous les nombres ayant un seul digit de différence avec 0, puis j'ai fait pareil pour tous les nombres restant, cela me permet de réduire mon ensemble d'arrivée et de finir avec quelque chose de correct mais qui ne me satisfait pas encore.
Ensuite, j'ai remarqué que si je commençais pas exemple par 4 (012) au lieu de 0, cela me permettait de réduire un peu plus mon ensemble d'arrivée. j'ai donc essayer de commencer mes boucles par tous les nombres allant de 0 à n et mon résultat varie vraiment beaucoup.
Hélas, je n'arrive toujours pas à ce que je souhaite, je sais qu'avec un ensemble de départ des nombres de 0 à 81 je peux arriver à un ensemble d'arrivée avec seulement 9 nombres mais mes meilleurs résultats obtenus tournent autour de 15 nombres.
Voilà, c'est pourquoi je demande votre aide si vous pouvez m'aiguiller vers certaines pistes.
Merci d'avance pour votre aide
Répondre avec citation
Partager