拼圖

請問取中間值所需的比較次數 - 拼圖

Valerie avatarValerie · 2009-12-22

Table of Contents

※ [本文轉錄自 Prob_Solve 看板]

作者: JFD (D) 看板: Prob_Solve
標題: [問題] 請問取中間值所需的比較次數
時間: Tue Dec 22 13:58:11 2009

請問有沒有人知道取中間值所需的最少比較次數是多少次？

譬如
3個數字取中間值,最少需要三次
5個數字,最少需要六次
7個數字呢？

有理論公式可推到2n+1個嗎？

--
拼圖

All Comments

Jacky avatarJacky2009-12-25
2n+1...請看一下http://0rz.tw/Fky2Z 吧!
Doris avatarDoris2009-12-29
抱歉,我不知道這有什麼幫助,如果只是演算法,k-selection可以用
但這不是我要問的問題
Mary avatarMary2009-12-31
這題還滿有趣的～:-)
Frederica avatarFrederica2010-01-02
如果我問，5個數字要怎麼六次，會不會很丟臉？>////<
我都要七次耶@@"
Hardy avatarHardy2010-01-06
變成...N^((N+1)/2) - 1 , N為奇數 這樣..=.=+
Rosalind avatarRosalind2010-01-07
錯了，是...2^((N+1)/2) - 1
Poppy avatarPoppy2010-01-10
所以我預計七個數字是15次
Lucy avatarLucy2010-01-11
7個數我知道有12次的作法,但不曉得是否為最少
John avatarJohn2010-01-15
嗯，我剛也覺得怪怪的..但5個數字真的有六次的方法嗎？
Wallis avatarWallis2010-01-17
你是想問幾次以下一定不行?還是給個方法找阿?
Quintina avatarQuintina2010-01-18
上面你說演算法不是你要問的..可是我看你回下一篇又是給方法
Irma avatarIrma2010-01-21
7個數字我猜10次吧...
Jessica avatarJessica2010-01-26
這個問題不是很明確。如果有資料陣列的話，
Isla avatarIsla2010-01-30
n 個資料不就是 (n-1) 次嗎？