File Hanoi.h

↰ Parent directory (ADS/algorithm)

The towers of Hanoi: moving n disks from the peg source to the peg dest, one at a time and never on a smaller one, with the peg middle as a spare.

Definition (ADS/algorithm/Hanoi.h)

Detailed Description

The recursive procedure moves n - 1 disks on middle, the last one on dest and the n - 1 disks on dest, hence it makes :math:`[

T( n ) = 2 T( n - 1 ) + 1 = 2^n - 1

` moves. The two iterative procedures of the book simulate its calls with a STACK of their parameters: the first one by hand, the second one by the systematic rules that also save the point where a call resumes (START, AFTER1, END, STOP). All of them hand each move to a function f( from , to ), so that the sequence of moves can be checked.

The contracts [see File Contract.h]: n >= 1 disks and three distinct pegs. The functions are defined in Hanoi.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 4.4, https://algoritmicamente.it/materiali/libro/capitoli/cap04.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions