作者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