Ханойская Башня

[pdbsoft]

1. Правила игры
Эта головоломка - любимая игра программистов: ее можно найти во многих программистких книжках.
Несколько кружков разных размеров уложены друг на друга, образуя башню. Башня стоит на одном из трех полей. задача - переставить ее на другое поле.
Но просто переставлять башню неинтересно - никакой задачи тут нет. Чтобы задание было не таким простым, нужны какие-то правила:
1) кружки переставляются с одного поля на другое, при этом их укладываюи друг на друга, так что получаются маленькие башни. Нельзя откладывать кружки в сторонуц или ставить один кружок вместо другого;
2) при каждом ходе двигается только один кружок. Нельзя переносить несколько кружков одновременно. Например, запрещено брать по кружку в каждую руку;
3) можно брать кружок лишь с вершины какой-нибудь башни и класть его только на вершину другой башни. Нельзя брать кружок из середины башни или вставлять его в середину другой башни;
4) запрещено класть большой кружок на меньший

[pdbsoft]

2. Легенда

Эту игру изобрел французский математик Люка больше ста лет назад, в 1883 году. И он сам украсил ее романтической и интересной легендой.

Где-то в непроходимых джунглях, недалеко от города Ханоя, есть монастырь бога Брамы. В начале времен, когда Брама создавал Мир, он воздвиг в этом монастыре три высоких алмазных стержня и на один из них возложил 64 диска, сделанных из чистого золота. Он приказал монахам перенести эту башню на другой стержень(в соответствиями с правилами, разумеется). С этого времени монахи работают день и ночь. Когда они закончать свой труд, наступит конец света.

[pdbsoft]

Вскоре будут добавлены разделы:

3. Рекордные результаты
4. Программа
5. Решение задачи Брамы
6. Три отступления
7. Некоторые наблюдения
8. Итог

[BBB]

А что тут решать-то? Эта классическая задача с несложным решением и разобрана в книге "Живая математика" или какой-то подобной.

Для переноса башни из N дисков на другое место требуется сделать:
2^N - 1 ходов.

Практический алгоритм переноса тоже несложен. Его можно назвать рекурсивным. Перенос башни из N дисков сводится к действиям:
1) Перенести "верх", т.е. башню из (N-1) диска на свободное место.
2) Перенести самый нижний диск (который в данный момент остался один) на нужное место.
3) Перенести "верх" (т.е. башню из (N-1) диска) со свободного места на нижний диск.

Т.е., рекурсивная формула количества ходов будет:
f (N) = 2 * f (N - 1) + 1

Для f (1) очевидно:
F (1) = 1

Правда, как из рекурсивнй формулы получить (2^N - 1), признаться, уже не помню

[somewhere]

BBB, ну если в рекурентную формулу вместо F(N-1) под подставить ее саму, то получится что-то вроде
F(N) = 2 * ( 2 * ( 2 * ... * 1 + 1 ) + 1 ) + 1) = 2^(N-1) + 2^(N-2) + 2^(N-3) .... + 1 = 2^N - 1, все просто