[問題] 請問取中間值所需的比較次數

看板puzzle作者 (D)時間14年前 (2009/12/22 16:56), 編輯推噓7(7推 0噓 6→)
留言13則, 5人參與, 最新討論串1/2 (看更多)
※ [本文轉錄自 Prob_Solve 看板] 作者: JFD (D) 看板: Prob_Solve 標題: [問題] 請問取中間值所需的比較次數 時間: Tue Dec 22 13:58:11 2009 請問有沒有人知道取中間值所需的最少比較次數是多少次？ 譬如 3個數字取中間值,最少需要三次 5個數字,最少需要六次 7個數字呢？ 有理論公式可推到2n+1個嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.96.112.162
→
12/22 16:38,
2n+1...請看一下http://0rz.tw/Fky2Z 吧!
12/22 16:38
→
12/22 16:45,
抱歉,我不知道這有什麼幫助,如果只是演算法,k-selection可以用
12/22 16:45
→
12/22 16:45,
但這不是我要問的問題
12/22 16:45
※ 編輯: JFD 來自: 140.96.112.162 (12/22 16:51) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.96.112.162
推
12/22 17:14, , 1F
這題還滿有趣的～:-)
12/22 17:14, 1F
推
12/22 17:28, , 2F
如果我問，5個數字要怎麼六次，會不會很丟臉？>////<
12/22 17:28, 2F
→
12/22 17:28, , 3F
我都要七次耶@@"
12/22 17:28, 3F
推
12/22 17:33, , 4F
變成...N^((N+1)/2) - 1 , N為奇數 這樣..=.=+
12/22 17:33, 4F
推
12/22 17:34, , 5F
錯了，是...2^((N+1)/2) - 1
12/22 17:34, 5F
→
12/22 17:35, , 6F
所以我預計七個數字是15次
12/22 17:35, 6F
→
12/22 17:43, , 7F
7個數我知道有12次的作法,但不曉得是否為最少
12/22 17:43, 7F
推
12/22 17:44, , 8F
嗯，我剛也覺得怪怪的..但5個數字真的有六次的方法嗎？
12/22 17:44, 8F
推
12/23 00:41, , 9F
你是想問幾次以下一定不行?還是給個方法找阿?
12/23 00:41, 9F
→
12/23 00:42, , 10F
上面你說演算法不是你要問的..可是我看你回下一篇又是給方法
12/23 00:42, 10F
→
12/23 12:19, , 11F
7個數字我猜10次吧...
12/23 12:19, 11F
推
12/25 22:37, , 12F
這個問題不是很明確。如果有資料陣列的話，
12/25 22:37, 12F
→
12/25 22:38, , 13F
n 個資料不就是 (n-1) 次嗎？
12/25 22:38, 13F
‣ 更多 JFD 的文章
文章代碼(AID): #1BC8d4nd (puzzle)
‣ 更多 JFD 的文章
文章代碼(AID): #1BC8d4nd (puzzle)