We do not always find visible happiness in proportion to visible virtue

梦幻白桦林

SHARE

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  14 Posts :: 58 Stories :: 62 Comments :: 0 Trackbacks

公告

常用链接

留言簿(5)

搜索

  •  

最新随笔

最新评论

阅读排行榜


有5户人家A,B,C,D,E,每户人家都养了5只鸽子,一共25只。

这5户人家想从一共这25只鸽子中挑出飞的最快的前5只鸽子。

大家选定了一个出发点和到达点,每次只能放飞5只鸽子,在这样情况下可以看到每次从出发地到目的地5只鸽子到达的先后顺序,但是没有计时器来计算时间。

注:题目中不要考虑鸽子体能,是否匀速,是否直线飞行等等情况,可以理想设定速度均匀而且稳速。
==============================================

请问:
A)在确保能挑出25只鸽子中飞的最快的5只的前提下,最少需要多少次比赛(每次只能5只)能保证能挑出最快的5只。

B)怎样比赛?
posted on 2007-06-03 16:34 colys 阅读(1678) 评论(15)  编辑 收藏 引用

Feedback

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-03 18:09 陶波
思想类似于用最小堆 做k路合并吧
最多10次就够了  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-03 18:32 刘东
A):最少8次可保证。
B):首先6次得到第1快和5*5矩阵,由左上角向右下角推进,第7次得到2、3快,第8次得到4、5快,推进过程怎么取舍5只比 恕可推不可表述,所以有人拿这种模型编程“玩”吗?
  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-04 00:22 kimi
想了一晚,只想了个9次的,第4、5快的一次搞不出来,  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-04 09:12 colys
谢谢各位牛人大哥, 这是我们公司出的题,现在已经过了截止日期了,不过我还有有兴趣写出代码的!  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-04 13:54 picasa
如何设计呢?  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-04 15:03 kimi
最近没时间啊,我也很想看一下8次是怎么搞出来的,毕业找不到工作,回家养鸽子去。  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-05 09:37 ff
很感兴趣!

半路出家程序员,最晕的就是这样的题目。有没有推荐的书,补补基础知识啊?  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-05 13:21 ethan
分5拨 5次比赛后决出各组的次序1st,2nd,3rd,4ur,5th 5次
1st,2nd,3rd,4ur,5th 一
1st,2nd,3rd,4ur,5th 二
1st,2nd,3rd,4ur,5th 三
1st,2nd,3rd,4ur,5th 四
1st,2nd,3rd,4ur,5th 五
1st决赛 决出1# 并出列形成例:
2nd,3rd,4ur,5th 一
1st,2nd,3rd,4ur,5th 二
1st,2nd,3rd,4ur,5th 三
1st,2nd,3rd,4ur,5th 四
1st,2nd,3rd,4ur,5th 五
2nd决赛 决出2# 并出列...
依次比赛后决出全部的前5名 共记10次  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-05 15:20 ethan
补充下不是 2nd决赛 而是2ND加入进来后 1ST重新比赛  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-05 16:00 hoho
only want to know 8 times  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-05 23:30 aa
8次可能,主要是要利用第六次开始之后的纵向排名,剔除不需要的,补进有可能更快的。  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-06 10:49 ethan
哦 果然是8次
21113 的话只需7次
下面的和其衍生的要8次:
23111 确定2个
11123 等其余确定3个  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-06 10:51 westwalk
需要八次

第一步:
分为五组 进行第一轮选拔 : 决出名次
1: 1 2 3 4 5
2: 1 2 3 4 5
3: 1 2 3 4 5
4: 1 2 3 4 5
5: 1 2 3 4 5
共五次。
第二步:
对每组的第一名进行比赛
假设:
(组)
6: 1 2 3 4 5
则: 第一组的1名最快
加入前五名队列
淘汰不可能的
则:
1: 2 3 4 5
2: 1 2 3 4
3: 1 2 3
4: 1 2
5: 1
第二步:进行预测:
第二名和第三名的组合很有可能是(第一组的2和3);(第二组的1和2); (第二组的1和第三组的1);(第一组的2和第二组的1);
而二三名的产生刚好锁定在五只鸽子中。
即第一组的2,3 第二组的1,2 第三组的 1
则进行比赛:可以决出二三名。
假设名次为:第一组的 2,3 第二组的 1, 2 第三组的 1
则 2, 3加入前五名
剩余为:
1:4 5
2:1 2
3:1 2 3
4:1 2
5:1
由于仅剩两个名额
则第五组的第一名出局
第四组的第一二名出局
第三组的二三名出局
则:
1:4 5
2:1 2
3:1
决赛:
证毕!
  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2007-06-06 18:45 colys
@westwalk good
  回复  更多评论
  

# re: 2007年度逻辑竞赛 (从25只鸽子中挑出飞的最快的前5只鸽子) 2008-05-07 10:59 marksman
westwalk 的思路差不多正确 但是证明似乎不是完全正确的
后面的证明不能那样假设  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理