|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 30 May 2002 18:06:18
To : Alexander Shmidt
Subject : pancake flipping problem
--------------------------------------------------------------------------------
Replying to a message of Alexander Shmidt to All:
BP>> Представьте, что у вас есть стопка из n блинов разного диаметра.
BP>> Разрешается взять верхнюю "подстопку" из k блинов (k - любое) и
BP>> перевернуть ее. Требуется за минимальное число таких переворотов
BP>> отсортировать блины в стопке согласно их диаметру.
[...]
BP>> P.S. Кстати, pancake flipping problem до сих пор является открытой
BP>> проблемой.
AS> Hеужто, мужики, все так сложно? Динамикой совем не решается?
AS> Да и подозрительно оно на Ханойские башни похоже - переворот
AS> аналогичен перекладанию стопки с перовой оси на вторую, со второй на
AS> третью и с третьей на первую.
Hу-ка реши для начала динамикой "Ханойские башни" в такой постановке: дано
*произвольное* допустимое (т.е. никакой больший диск не лежит на меньшем)
расположение дисков на стержнях, нужно за *минимальное* число перемещений
переложить все их на первый стержень согласно классическим правилам.
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.8
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
pancake flipping problem 
