OCaml (option informatique) · Chapitre 11 · Exercice de TD

Liste des coups de Hanoï

Récursivité et retour sur trace · niveau 2

Énoncé

Écrire hanoi produisant la liste des déplacements, et donner hanoi 2 "A" "B" "C".

Corrigé

let rec hanoi n depart inter arrivee =
  if n = 0 then []
  else
    hanoi (n - 1) depart arrivee inter
    @ [(depart, arrivee)]
    @ hanoi (n - 1) inter depart arrivee

hanoi 2 "A" "B" "C" $=$ [("A","B"); ("A","C"); ("B","C")] : on pose le petit disque en B, le grand en C, puis le petit en C. Trois coups, comme $2^{2} - 1$ .

Exercices semblables

Permutations corrigé
Compter les sous-ensembles de somme donnée corrigé
Combinaisons corrigé
Les $n$ reines corrigé
Reconstruire le sous-ensemble corrigé

Le cours du chapitre · Tous les exercices du chapitre