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

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Ответить
Аватара пользователя
pdbsoft
Сообщения: 10
Зарегистрирован: 05 фев 2008, 22:52

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

Сообщение pdbsoft » 07 фев 2008, 16:08

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

Аватара пользователя
pdbsoft
Сообщения: 10
Зарегистрирован: 05 фев 2008, 22:52

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

Сообщение pdbsoft » 07 фев 2008, 16:12

2. Легенда

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

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

Аватара пользователя
pdbsoft
Сообщения: 10
Зарегистрирован: 05 фев 2008, 22:52

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

Сообщение pdbsoft » 07 фев 2008, 16:14

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

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

BBB
Сообщения: 1272
Зарегистрирован: 27 дек 2005, 13:37

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

Сообщение BBB » 08 фев 2008, 09:59

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

Для переноса башни из 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
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 16:14
Откуда: 71 RUS
Контактная информация:

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

Сообщение somewhere » 08 фев 2008, 11:52

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, все просто
It's a long way to the top if you wanna rock'n'roll

Ответить