Les tours de Hanoï

2.3. Algorithme général des tours de Hanoï

Nous représenterons ces mots par des lettres grecques et définirons les fonctions suivantes :

Tête(α) : Retourne la première lettre du mot α. Cela correspond à la position du plus grand disque.

Queue(α) : Retourne une copie du mot α à laquelle on a retiré la première lettre.

Empilement(α, β) : Cette fonction n'a de sens que si α et β ont la même longueur n. Elle retourne un mot composé de n - 1 fois le même caractère. Ce dernier, que nous appelerons x, est tel que {Tête(α), Tête(β), x} = {1, 2, 3}

On remarque que α est la concaténation de Tête(α) et Queue(α).

Voici donc l'algorithme général qui permet de passer d'une configuration α vers une configuration β :

Transforme(α, β) {
  Si tête(α) = α Alors
    α → β
  SinonSi tête(α) = tête(β) Alors
    Transforme(queue(α), queue(β))
  Sinon
    γ = Empilement(α, β)
    Transforme(queue(α), γ)
    tête(α) → tête(β)
    Transforme(γ, queue(β))
  FinSi
}

Pages : 1 2 3 4 5 6 7