 |
|
Математика: Комбинаторика и перебор.
Ханойские башни.
Есть три стержня A, B, и C. На стержень A надето N дисков, наверху самый маленький, каждый следующий диск больше предыдущего, а внизу самый большой. На другие стержни дисков не надето.
Hеобходимо перенести диски со стержня A на стержень C, пользуясь стержнем B, как вспомогательным, так, чтобы диски на стержне C располагались в том же порядке, в каком они располагаются на диске A перед перемещением.
При перемещении никогда нельзя класть больший диск на меньший.
Решение
Рекурсивный метод
Для того, чтобы переложить всю пирамиду, надо сначала переложить все, что выше самого большого диска, с первого на вспомогательный стержень, потом переложить это самое большой диск с первого на третий стержень, а потом переложить оставшуюся пирамиду со второго на третий стержень, пользуясь первым стержнем, как вспомогательным.
/*
данная процедура переносит N дисков со стержня A на стержень C
пользуясь B как вспомогательным, соблюдая правила
*/
процедура "Перенести" (A, B, C, N)
начало
если N=1
// Если диск всего один, то надо его перенести напрямую
то
снять диск со стержня A и положить на стержень C;
возврат из процедуры;
иначе
// Переносим все диски, кроме самого большога со стежня
// A на стержень B
Перенести (A,C,B,N-1);
// Переносим самый большой диск со стержня A на стержень C
снять диск со стержня A и положить на стержень C;
// Переносим все диски со стержня B на стержень C поверх
// самого большого диска
Перенести (B,A,C,N-1);
возврат из процедуры;
конец если;
конец процедуры "Перенести";
Всего получается 2N-1 перекладываний.
Исходник на Си++
Исходник на Си
Исходник на Паскале
Исходник на Бейсике ;-)
Нерекурсивный метод
Стержню, на котором диски находятся в начале, дадим номер 0; стержню, на который их надо перенести - номер 2; и, соответственно, оставшемуся стержню - номер 1.
Пусть всего дисков N. Занумеруем диски в порядке увеличения радиуса числами 0,1,2,...,N-1.
Как известно, задача решается за 2N-1 ходов. Занумеруем ходы числами 1,2,...,2N-1.
Любое натуральное число i единственным образом представимо в виде i=(2t+1)*2k, где t и k - целые (т.е. как произведение нечетного числа на некоторую степень двойки). Так вот, на i-ом ходе переносится диск номер k со стержня номер ((-1)N-k*t mod 3) на стержень номер ((-1)N-k*(t+1) mod 3).
Пример для N=4.
Ход k(диск) t Со_стержня Hа_стержень Стержни
|)!'
1 0 0 0 1 |)! '
2 1 0 0 2 |) ' !
3 0 1 1 2 |) !'
4 2 0 0 1 | ) !'
5 0 2 2 0 |' ) !
6 1 1 2 1 |' )!
7 0 3 0 1 | )!'
8 3 0 0 1 )!' |
9 0 4 1 2 )! |'
10 1 2 1 0 ! ) |'
11 0 5 2 0 !' ) |
12 2 1 1 2 !' |)
13 0 6 0 1 ! ' |)
14 1 3 0 2 ' |)!
15 0 7 1 2 |)!'
если пpедставить что стержни, на котоpые одеваются диски, pасположены в yглах pавностоpоннего тpеyгольника, то самый маленький диск каждым нечетным ходом движется по (или пpотив, это от пеpвоначального кол-ва дисков зависит) часовой стpелки.
Все четные ходы опpеделяются однозначно. Какой диск меньше - тот и перекладывать (иначе противоречит условию). Т.к. тpогать диск 0 нельзя и класть больший на меньший тоже нельзя.
Отметим две закономерности:
- Hа каждом нечетном ходy происходит перенос наименьшего диска.
- Hаименьший диск всегда переносится циклически: либо A-B-C-A-B-C-... (в слyчае четного количества дисков), либо A-C-B-A-C-B-... (в слyчае нечетного).
А посемy полyчаем алгоритм:
1. Определяем число дисков,
откyда находим как бyдет перемещаться наименьший
диск (данный шаг делается в начале, притом один раз).
2. Смотрим номер хода:
если нечетный - переносим наименьший диск в направлении,
определенном в п.1.
если четный - то возможный ход один единственный -
берем наименьший из двyх верхних дисков и переносим его.
Можно написать немного по другому:
Для N от 1 до 2k-1 выполнять 1. В двоичном представлении N найти самый правый ненулевой разряд. Обозначим номер этого разряда t. 2. Обозначим номер стержня, на котором находится диск t через i. Переместить диск t со стержня i на стержень (i+(-1)t) mod 3.
Кстати, по номеру хода легко можно восстановить положение
дисков на стержнях:
после i-ого хода диск номер j находится на стержне номер
(-1)n-j*((i div 2j)-(i div 2j+1)) mod 3.
Вверх по странице, к оглавлению и навигации.