|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Shmidt 2:464/34.74 30 May 2002 07:36:54
To : All
Subject : pancake flipping problem
--------------------------------------------------------------------------------
*** Ответ на мессагу из мыльной оперы HUMOR.FILTERED (HUMOR.FILTERED).
>< Е >< Е >< Хау, бледнолицый All! >< Е >< Е ><
(будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
Эй, уважаемые Boris Paleev и All! Что за "4hf", а где же яйца?!
BP> ======= * Forwarded by Boris Paleev (2:5020/113) * Area : BORIS_IN
BP> ======= * Forwarded from RU.MATH by Aleksey Smirnov (2:5015/107.32). *
BP> Originally by: Max Alekseyev (2:5015/60), 30 Aug 01 13:04. *
BP> Originally to: All.
BP> Мне мой научный руководитель рассказал интересную историю, которую ему
BP> поведал известный проф. Пападимитриу.
BP> Когда Пападимитриу только "выпустился" и приступил к преподавательской
BP> деятельности в Гарварде, он задал студентам задачку, которая казалась
BP> ему не особо сложной, но тем не менее сразу ему не далась. И пообещал
BP> тому, кто ее решит, поставить по своему курсу A (5 по-нашему). Задачка
BP> (ныне известная как "pancake flipping problem") такая:
BP> Представьте, что у вас есть стопка из n блинов разного диаметра.
BP> Разрешается взять верхнюю "подстопку" из k блинов (k - любое) и
BP> перевернуть ее. Требуется за минимальное число таких переворотов
BP> отсортировать блины в стопке согласно их диаметру.
BP> Hикакой ответной реакции со стороны студентов не последовало, и только
BP> в конце семестра к Пападимитриу подошел студент, который сказал, что
BP> не знает как решить эту задачу, но у него есть кое-какие идеи. После
BP> совместного обсуждения эти идеи вылились в статью
BP> W.H.Gates, C.H. Papadimitriou "Bounds for sorting by prefix
BP> reversals". - Discrete Mathematics, 27:47-57, 1979.
[скиппед]
BP> P.S. Кстати, pancake flipping problem до сих пор является открытой
BP> проблемой.
BP> ====================================================================
Hеужто, мужики, все так сложно? Динамикой совем не решается?
Да и подозрительно оно на Ханойские башни похоже - переворот аналогичен
перекладанию стопки с перовой оси на вторую, со второй на третью и с третьей на
первую.
Какие будут мнения?
Good bye, mister All _
/_| _ _ _/
Smith, ( | (/ (- /) / Smith...
_/
... Все в Голом Деде пишут послания, Winamp поставлен на паузу... (с)~Сплин
--- np: Rollergirl - Dear Jessie
* Origin: Телепузик спать ложится - программист за комп садится. (2:464/34.74)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
