OCaml (option informatique) · Chapitre 11 · Application directe du cours

Nombre de coups de Hanoï

Récursivité et retour sur trace · niveau 1 (application)

Énoncé

Écrire nb_coups n (sans construire la liste des coups) et établir nb_coups n $= 2^{n} - 1$ .

Corrigé

let rec nb_coups n =
  if n = 0 then 0
  else 2 * nb_coups (n - 1) + 1

Par récurrence : $C (0) = 0 = 2^{0} - 1$ ; et $C (n) = 2 C (n - 1) + 1 = 2 (2^{n - 1} - 1) + 1 = 2^{n} - 1$ . Déplacer $64$ disques demanderait $2^{64} - 1$ coups : astronomique.

Exercices semblables

Les $n$ reines corrigé
Reconstruire le sous-ensemble corrigé
Sortie d'un labyrinthe corrigé
Les parties corrigé
Sous-ensemble de somme donnée corrigé

Le cours du chapitre · Tous les exercices du chapitre