|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Shmidt 2:464/34.74 02 Jun 2002 00:43:11
To : Alexandr Brezgin
Subject : pancake flipping problem
--------------------------------------------------------------------------------
>< Е >< Е >< Хау, бледнолицый Alexandr! >< Е >< Е ><
(будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
Эй, уважаемые Alexandr Brezgin и Alexander Shmidt! Что за "pancake flipping
problem", а где же яйца?!
AS>> Какие будут мнения?
AB> 1. Знаем положение диска в отсортированной башне.
AB> 2. Выполняем действие:
AB> Переворачиваем k
AB> Переворачиваем k-1
AB> Результат, верхний диск окажется в любом (нужном) месте башни.
Оно бы неплохо, но для ситуации, когда в начале все диски отсортированы снизу
вверх по возрастанию - можно остановиться и на "Переворачиваем k".
Вроде бы мелочь, но в этом и весь прикол - в общем случае не знаешь, когда
остановиться.
Можно попробовать динамикой:
ф-ция от двух параметров - рассматриваемое кол-во "верхних" блинов и "величина"
нижнего из этого набора блина, возвращает минимальное кол-во перестановок. Пока
смутно себе все это представляю, надо еще подумать.
Hо в таком вот виде, когда все сводится к тому, чтобы извратно отсортировать,
кажется, что где-то я это видел. И решалось это не то динамикой (но не такой
простой, как я написал, а с каким-то приколом), не то исключительно в ширину
(что не есть гут).
AB> 3. Hачинаем строить отсортированную последовательность в самом низу
AB> для того чтобы вытеснить все неотсортированные диски на верх (в
AB> сортир:)). 4. Пошли пихать диски в нужное место отсортированной части
AB> башни.
"Сотировка выбором". А "выбором" - это недопузырек, а пузырек можно
оптимизировать, знач "выбором" тоже оптимизируется...
AB> Дохлые у них студенты. :)
Мелкие и мягкие какие-то :)
AB> PS. Если что, то я первый.
Hе - я первый увидел эту задачу :)
Good bye, mister Brezgin _
/_| _ _ _/
Smith, ( | (/ (- /) / Smith...
_/
... ...и не дай Вам Бог в наше тяжелое время родиться пенсионером... (с)KBH
--- стоппед: СПЛИ - SOS!
* Origin: Пепси, пейджер, MTV - наши лучшие друзья! (2:464/34.74)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
