~ Towers of hanoi

» Door Joren op woensdag 10 december 2003 - Reacties(1) - Reageer Een zekere Amit Singh heeft in 108 verschillende programmeertalen het "Towers of hanoi" porbleem opgelost. Op zijn website vind je er meer info over. Hieronder volgt een beschrijving van het probleem:

Problem Definition

Francoise Edouard Anatole Lucas

The object of the problem is to move all the disks over to the rightmost tower, one at a time, so that they end up in the original order on that tower. You may use the middle tower as temporary storage, but at no time during the transfer should a larger disk be on top of a smaller one.

The puzzle was invented by a Frenchman called Francoise Edouard Anatole Lucas (1842 - 1891), although many "legends" (like the one below) are often mentioned regarding the puzzle. The puzzle appeared in 1883 under the name of M. Claus. Notice that Claus is an anagram of Lucas! Lucas' four volume work on recreational mathematics is a classic.

A bit of "history" about the puzzle can be found in the hanoi.el LISP file in the GNU Emacs distribution. Quoting verbatim from there:

The puzzle is called "Towers of Hanoi" because an early popular presentation wove a fanciful legend around it. According to this myth (uttered long before the Vietnam War), there is a Buddhist monastery at Hanoi which contains a large room with three time-worn posts in it surrounded by 21 golden discs. Monks, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle, once every day since the monastery was founded over a thousand years ago. They are said to believe that when the last move of the puzzle is completed, the world will end in a clap of thunder. Fortunately, they are nowhere even close to being done.

There is a similar "myth" about similar towers in the Hindu city of Benaras in India.

Een voorbeeldje in c# maakt alles duidelijk. Nog een quote uit zijn FAQ: