помогите найти быстрый алгоритм решения задачи о стопке блинов!!

[Ыыыга]

 :dontknow:кроме тупого перебора, ниче нет

[Вад]

А что за задача?

[Джон]

Ну так, а в чём проблема? Перебирай. Тупо.

[Алексей++]

Ыыыыыы
*ушёл тупо перебирать*


зы докатились

[Ыыыга]

в том то и дело, что нужен более быстрый алгоритм. перебор не катит

[Алексей++]

Ыыыга, ты Ханойскую башню имеешь в виду ?

[Sla]

А что за задача?

[Ыыыга]

да типа башни, только блины нужно на 1 тарелке переворачивать. в итоге нужно их положить по увеличению диаметра

[Вад]

Ну так, а в чём проблема? Перебирай. Тупо.

Offtopic:

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

Поставлю в угол.

[Sla]

я конечно поиском воспользовался... а вдруг не то?

[Алексей++]

с одной тарелкой не получится, надо как минимум 3

[Ыыыга]

почему не получится? берешь блины лопаточкой и переворачиваешь и вот так вот лопаточкой маешься, пока пирамидка не получится

[Вад]

Алексей1153++, ещё как получится.
Ыыыга, помимо "нужно на 1 тарелке переворачивать", есть какие-то ограничения? Механизм поворота блинов не раскрыт. В ханойских башнях перемещали по одному элементу. Тут явно не так.

[Ыыыга]

нет. просто переворачиваешь блины вверх ногами:)

[Ыыыга]

да хотьпо 10 блинов. без разницы. лишь бы уложить их

[Алексей++]

я бы просто съел все блины А потом кучка будет ровная

[Ыыыга]

я б тоже съел. тока как мне это преподу объяснять

[Вад]

А про диаметр блинов всё известно? Если да, самое очевидное напрашивающееся решение - подхватываем самый широкий блин, переворачиваем стопку, чтобы он оказался наверху, потом переворачиваем всё вместе - оп, первый блин внизу. И так 2*n переворотов. На двусвязных списках будет быстро работать.

[Ыыыга]

1-й кто нашел оптимальный способ это Билл

[Sla]

Offtopic:

про Билли
История, рассказанная небезызвестным проф. Пападимитриу.

Когда Пападимитриу только защитился и приступил к преподавательской деятельности в Гарварде, он задал студентам задачку, которая казалась ему не особо сложной, но тем не менее сразу ему не далась. И пообещал тому, кто ее решит, поставить по своему курсу A (5 по-нашему). Задачка (ныне известная как pancake flipping problem) такая:

Представьте, что у вас есть стопка из n блинов разного диаметра. Разрешается взять верхнюю "подстопку" из k блинов (k - любое) и перевернуть ее. Требуется за минимальное число таких переворотов отсортировать блины в стопке согласно их диаметру.

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

W.H.Gates, C.H. Papadimitriou "Bounds for sorting by prefix reversals". - Discrete Mathematics, 27:47-57, 1979. (обзор алгоритма)

Через некоторое время после выхода статьи Пападимитриу позвонил профессор из другого университета и сказал, что он только что познакомился со статьей, она произвела на него сильное впечатление, и он хотел бы пригласить "этого студента" на собеседование на непомнюкакую должность. Пападимитриу ему ответил, что студент к сожалению бросил учебу и организовал компанию Microsoft...

Поставлю в угол.

[Ыыыга]

А про диаметр блинов всё известно? Если да, самое очевидное напрашивающееся решение - подхватываем самый широкий блин, переворачиваем стопку, чтобы он оказался наверху, потом переворачиваем всё вместе - оп, первый блин внизу. И так 2*n переворотов. На двусвязных списках будет быстро работать.

интересно... спасибо попробую. если меня загубят снова зайду

[Вад]

Ага, точнее, там чуть меньше, чем 2*n будет. Сходил в вики - так не интересно, там тот же метод описан.

[Sla]

можно взять уже предложенное

[Ыыыга]

 

[Ыыыга]

эт снова я и снова с блинами
короче препод сказал, что алгоритм Гейтса ему нафиг не нужен. Он хочет, чтобы я как бы оптимизировал алгоритм полного перебора для этих чертовых блинов, т.е. когда перебор начнет "вставать". К примеру полный перебор может работать и для 100 блинов, если 99 из них уже упорядочены, но этот же алгоритм может встать, допустим, на 5 блинах, если они лежат как попало.
Вот такая вот нехорошая штука получается...

[Dimka]

Похоже, преподаватель хочет видеть решение методом "ветвей и границ".

Рассматривай комбинацию блинов в стопке как одно целое. Для комбинации введи весовой коэффициент близости к решению. Дальше строй дерево перестановок, но по дереву (от перестановки к новой перестановке) спускайся так, чтобы на каждом шаге весовой коэффициент улучшался бы. Переходы между комбинациями ограничены условием задачи (переворачивание верхней подстопки). Рекурсивное решение получится.