|
|||||||||||||||||||||||||||||||||||||||||||||
|
TRICHOTOMIE On connait la dichotomie,
un procédé de recherche qui procède par élimination des moitiés. La trichromie suit le même exemple
mais en éliminant deux tiers de l'intervalle. La méthode est plus rapide que
celle de la dichotomie au prix d'une logique ternaire. |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
On se
propose de deviner un nombre (123) sachant qu'il est compris entre 1 et 999. L'intervalle
de recherche va être divisé par 3 à chaque itération. |
Le
segment [0 et 999] est divisé en trois avec un jalon minimum (Jmin = 333) et
un jalon maximum (Jmax = 666) . Le
nombre 123 est inférieur, il est compris entre la borne min (Bmin = 0) et la
borne max (Bmax = 333). Ce
segment, égal au tiers du précédent (333),
est lui-même divisé en tiers (111) avec pour les nouveaux jalons: Jmin = 0 + 111
et Jmax = 333 – 111. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Le nombre
123 est trouvé à l'issue de sept itérations. À chaque
itération la question posée est: est-ce que le nombre est:
Réponse en rouge dans le tableau. Arrêt lorsqu'un jalon est égal à une borne. L'écart est égal à l'entier issu de la fraction
(Jmax – Jmin) / 3. Ce principe de calcul est applicable quelles que soient
les bornes. |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||
|
136 0, 333,
666, 999, 333 0, 111,
222, 333, 111 111, 148,
185, 222, 37 111, 123,
136, 148, 12 123, 127,
132, 136, 4 132, 133,
135, 136, 1 135, 135,
136, 136, 0 7 |
555 0, 333,
666, 999, 333 333, 444,
555, 666, 111 444, 481,
518, 555, 37 518, 530,
543, 555, 12 543, 547,
551, 555, 4 551, 552,
554, 555, 1 554, 554,
555, 555, 0 7 |
789 0, 333,
666, 999, 333 666, 777,
888, 999, 111 777, 814,
851, 888, 37 777, 789,
802, 814, 12 777, 781,
785, 789, 4 785, 786,
788, 789, 1 788, 788,
789, 789, 0 7 |
999 0, 333,
666, 999, 333 666, 777,
888, 999, 111 888, 925,
962, 999, 37 962, 974,
987, 999, 12 987, 991,
995, 999, 4 995, 996,
998, 999, 1 998, 998,
999, 999, 0 7 |
|
|
|
||
|
|
But Deviner
un nombre entre 1 et 999 par trichotomie. Lister les étapes à la manière du
tableau ci-dessus. Programme Maple Initialisation.
Indication du nombre à analyser. Positionnement d'une variable binaire à 0 et
d'un compteur à 0. Initialisation
des bornes et des jalons. Boucle
continue tant que la variable binaire est à 0. Calcul de l'écart. Mise
à jour des bornes selon l'emplacement du nombre à deviner dans l'un des trois
tiers. Mise
à jour des jalons en fonction des nouvelles bornes. Incrémentation
du compteur d'itérations. Arrêt
avec t = 1 si le jalon est égal à la borne. Impression
des bornes et des jalons ainsi que de l'écart d. Résultat Lors
de l'exécution, on retrouve les sept lignes d'itérations, précédées du nombre
n et suivi de la quantité d'itérations kt. |
|
Voir Programmation – Index
|
Suite |
|
|
Voir |
|
|
DicoNombre |
|
|
Cette page |
