Nombre de coups de Hanoï

Exercice · OCaml (option informatique), chapitre 11 — Récursivité et retour sur trace

É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.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.