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