Re: [問題] UVA 120

作者: coconutman (被椰子砸到)   2012-11-29 20:57:39
這題題意沒有要求最佳解。
但如果要求最佳解的話,不曉得有沒有人有辦法解的出來呢?
: : 我想用遞迴的方法做,三個步驟
: : 1.若最上面的元素最大 不反轉
: : 2.若最大元素不在最上面 在最下面 則翻轉一次
: : 3.若最大元素不在最上面 也不在最下面 則翻轉兩次 先翻到最下面再翻到最上面
EX.
若用上上篇的步驟的話:
1243 -> 4213 -> 3124 -> 2134 -> 1234
但最佳解可為:
1243 -> 3421 -> 4321 -> 1234
數列長度限制在 30 以內。
作者: LPH66 (-6.2598534e+18f)   2011-01-29 22:01:00
http://en.wikipedia.org/wiki/Pancake_sorting這裡好像有提到一些研究結果中間一段應該是說這個問題是 NP-hard
作者: coconutman (被椰子砸到)   2011-01-29 22:31:00
wow~謝謝你!!原來已經有論文證明是是NP-hard!

Links booklink

Contact Us: admin [ a t ] ucptt.com