PTT
數位生活區
即時熱門文章
24小時內熱門文章
最新文章
熱門看板
看板列表
我的收藏
最近瀏覽
批踢踢 PTT 搜尋引擎
看板
[
Prob_Solve
]
討論串
[問題] sorting problem轉decision problem
共 2 篇文章
排序:
最舊先
|
最新先
|
留言數
|
推文總分
內容預覽:
開啟
|
關閉
|
只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] sorting problem轉decision problem
推噓
4
(4推
0噓 5→
)
留言
9則,0人
參與
,
最新
作者
mqazz1
(無法顯示)
時間
13年前
發表
(2011/09/09 20:26)
,
編輯
資訊
1篇文章回應此文
1
內文有0個圖片
image
0
內文有0個連結
link
0
內容預覽:
我在看NP-complete的時候. 講義上說凡是NP-complete領域所討論的problem一定是以decision形式出現. 然後他有問一個問題. sorting problem: 將a1, a2, ..., an由小排到大. 請問這種問題要怎麼把它轉成decision的形式?. 謝謝. -
#2
Re: [問題] sorting problem轉decision problem
推噓
1
(1推
0噓 0→
)
留言
1則,0人
參與
,
最新
作者
hcsoso
(索索)
時間
13年前
發表
(2011/09/10 12:58)
,
編輯
資訊
0篇文章回應此文
0
內文有0個圖片
image
0
內文有1個連結
link
1
內容預覽:
這題有不同可能的答案. (最近家教才教到, 提供一些想法!). 當然最直接的 "給定 input A[1..n], 請問是否 A[1] <= ... <= A[n]?" 是一個可能.. 我覺得底下這個方法比較有趣:. 考慮問題 SORT', 給定 input A[1..n], 求一 A 的重排 B[
(還有324個字)
首頁
上一頁
1
下一頁
尾頁