Retour

Course à zéro

Les calculs précédents donnent une solution qui semble être optimale, mais comment s'en assurer ?

Une façon de faire est de modéliser ce problème sous la forme d'un graphe.
Soit n un nombre quelconque ; on construit le graphe G ayant comme sommets tous les nombres entiers de 0 à n + 9. Les arêtes relient des nombres que l'on peut déduire les uns des autres. Il suffit alors de trouver un chemin minimal de n à 0 en utilisant par exemple l'algorithme de Djisktra.

Ainsi, par exemple, le graphe de 22 sera :

Il suffit alors de déterminer dans ce graphe un chemin minimal de 22 à 0. L'algorithme donne, par exemple : 22 11 9 0 et le parcours est de longueur 3. On voit, sur cet exemple simple que la réponse n'est pas unique.

Télécharger le fichier Maple (version 8, 24Ko)(Clic droit, puis Enregistrer la cible du lien sous...)

Retour