2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Сортировка ханойских башен
Сообщение12.08.2012, 16:26 
В ханойской головоломке на первом стержне диски стоят не по правилам (т. е. больший диск может стоять на меньшем). Нужно переложить эти диски так, чтобы они оказались на одном из стержней в порядке возрастания номеров. Класть больший диск на меньший запрещается.

P. S. Решил несколько задач про ханойские башни. Решались нетрудно и, в основном, рекурсией. С этой не могу разобраться.

 
 
 
 Re: Сортировка ханойских башен
Сообщение12.08.2012, 21:48 
Wran в сообщении #605390 писал(а):
Класть больший диск на меньший запрещается.

А при таком условии разве не будет ситуации, когда решений совсем нет? Например, как быть со случаем когда исходная конфигурация - обычная ханойская башня, у которой самый малый диск перемещен в основание?

 
 
 
 Re: Сортировка ханойских башен
Сообщение13.08.2012, 05:41 
Аватара пользователя
_hum_ в сообщении #605502 писал(а):
Например, как быть со случаем когда исходная конфигурация - обычная ханойская башня, у которой самый малый диск перемещен в основание?

А что здесь плохо? Перекладываем диски, кроме двух последних (самого большого и самого маленького) на другую палку, затем самый большой на свободную, затем самый маленький в верхушку пирамиды (в которой все, кроме самого большого), далее очевидно.

 
 
 
 Re: Сортировка ханойских башен
Сообщение13.08.2012, 10:02 
Аватара пользователя
Пусть $s$ - перестановка, соответствующая изначальному упорядочению ханойских башен. Блоком считаем максимальный кусок $s(i), \ldots, s(j)$, для которого $s(i) > s(i+1) > \ldots > s(j)$. Задача сводится к перекладыванию всех блоков, то есть к перемещению блоков с параллельным их упорядочиванием.

 
 
 
 Re: Сортировка ханойских башен
Сообщение13.08.2012, 15:43 
Профессор Снэйп в сообщении #605541 писал(а):
_hum_ в сообщении #605502 писал(а):
Например, как быть со случаем когда исходная конфигурация - обычная ханойская башня, у которой самый малый диск перемещен в основание?

А что здесь плохо? Перекладываем диски, кроме двух последних (самого большого и самого маленького) на другую палку, затем самый большой на свободную, затем самый маленький в верхушку пирамиды (в которой все, кроме самого большого), далее очевидно.

Ясно. Просто не был в курсе, что перестановка ханойской башни допускает это ограничение.
Ну, тогда наверное все можно свести к задаче составления из двух ханойских башень одной.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group