|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Shmidt 2:464/34.74 01 Jun 2002 22:57:53
To : Max Alekseyev
Subject : pancake flipping problem
--------------------------------------------------------------------------------
>< Е >< Е >< Хау, бледнолицый Max! >< Е >< Е ><
(будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
Эй, уважаемые Max Alekseyev и Alexander Shmidt! Что за "pancake flipping
problem", а где же яйца?!
BP>>> Представьте, что у вас есть стопка из n блинов разного диаметра.
BP>>> Разрешается взять верхнюю "подстопку" из k блинов (k - любое) и
BP>>> перевернуть ее. Требуется за минимальное число таких переворотов
BP>>> отсортировать блины в стопке согласно их диаметру.
MA> [...]
BP>>> P.S. Кстати, pancake flipping problem до сих пор является
BP>>> открытой проблемой.
AS>> Hеужто, мужики, все так сложно? Динамикой совем не решается?
AS>> Да и подозрительно оно на Ханойские башни похоже - переворот
AS>> аналогичен перекладанию стопки с перовой оси на вторую, со второй
AS>> на третью и с третьей на первую.
MA> Hу-ка реши для начала динамикой "Ханойские башни" в такой постановке:
MA> дано *произвольное* допустимое (т.е. никакой больший диск не лежит на
MA> меньшем) расположение дисков на стержнях, нужно за *минимальное* число
MA> перемещений переложить все их на первый стержень согласно классическим
MA> правилам.
ОК. Как там оно решается для классического начального положения? Hапомни, а то
подзабыл немного...
Good bye, mister Alekseyev _
/_| _ _ _/
Smith, ( | (/ (- /) / Smith...
_/
... Пiнгвiн - то не win. Щоб стояв у кожнiй хатi!
--- стоппед: СПЛИ - SOS!
* Origin: Я знаю три буквы, три матерных буквы... (2:464/34.74)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
pancake flipping problem 