討論串[問題] sorting problem轉decision problem
共 2 篇文章
首頁
上一頁
1
下一頁
尾頁

推噓4(4推 0噓 5→)留言9則,0人參與, 最新作者mqazz1 (無法顯示)時間13年前 (2011/09/09 20:26), 編輯資訊
1
0
0
內容預覽:
我在看NP-complete的時候. 講義上說凡是NP-complete領域所討論的problem一定是以decision形式出現. 然後他有問一個問題. sorting problem: 將a1, a2, ..., an由小排到大. 請問這種問題要怎麼把它轉成decision的形式?. 謝謝. -

推噓1(1推 0噓 0→)留言1則,0人參與, 最新作者hcsoso (索索)時間13年前 (2011/09/10 12:58), 編輯資訊
0
0
1
內容預覽:
這題有不同可能的答案. (最近家教才教到, 提供一些想法!). 當然最直接的 "給定 input A[1..n], 請問是否 A[1] <= ... <= A[n]?" 是一個可能.. 我覺得底下這個方法比較有趣:. 考慮問題 SORT', 給定 input A[1..n], 求一 A 的重排 B[
(還有324個字)
首頁
上一頁
1
下一頁
尾頁