e******s
发帖数: 38 | 1 题A: 一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起
比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问
，最少得比多少场才能知道跑得最快的5匹马？
题B： 49 匹赛马. Assume for each one, it travels the track in the same
amount of time every time. Also assume no two finish the track in the same
amount of time. Suppose you have 7 tracks, but no timer. Design races to
find the 25-th fastest with minimal number of races
记得好像板上讨论过，找不到了原帖。 不知道有什么好的系统的解法。 |
r**o
发帖数: 4614 | 2 题A
等车的时候想了下，可能有错，就当抛砖引玉了
一共ABCDE5个组
假设排名是A1B2C3D4E5
然后选组内排名的A(2)A(3)B(1)B(2)C(1)跑
最坏情况排名是B(1)C(1)。。。。就是每次最少选出2名
下一次最差就选A（2）A（3）B（2）D（1）E（1）跑， 也是选出2名
最多3次
题B
其实是一样的，每次跑最快的组出（7-1）/2 = 3， 前3名
那就是A(2)A(3)A(4)B(1)B(2)B(3)C(1）跑， 每次最少选出2名
下一次最差就是A（2）A(3)A(4）B（2）B(3)D(1)E(1)， 每次最少选出2名
。。。。
最多4次。 |
p*****y
发帖数: 1386 | 3 这个“假设排名是A1B2C3D4E5”是什么意思啊？每个组里5匹马，这个排名是组里第几
名的排名呢？
而且每个组各自赛一次就是5次了，我估摸着再怎么也得跑个8次吧，暂时还没有什么系
统一点的想法。。。
【在 r**o 的大作中提到】
: 题A
: 等车的时候想了下，可能有错，就当抛砖引玉了
: 一共ABCDE5个组
: 假设排名是A1B2C3D4E5
: 然后选组内排名的A(2)A(3)B(1)B(2)C(1)跑
: 最坏情况排名是B(1)C(1)。。。。就是每次最少选出2名
: 下一次最差就选A（2）A（3）B（2）D（1）E（1）跑， 也是选出2名
: 最多3次
: 题B
: 其实是一样的，每次跑最快的组出（7-1）/2 = 3， 前3名
|
c*********a
发帖数: 2265 | |
r**o
发帖数: 4614 | 5 写得太快了
详细点哈
先是每个组赛1场， 1共赛5场
然后赛1场每个组的第一名， 假设跑的最快的依次是ABCDE， 就这就是A1B2C3D4E5的意
思啊
前面写的就是从这里开是
我们先选前3名， 第一名已经知道了，是A（1）， 那么有可能第2，3名的话就是A（2
）A（3）和B(1)B(2)C(1),然后他们赛一下， 就知道了前3名。
下面就是排列组合了
1. A（2）A(3）B（1）B（2）C（1）， 这种情况我们下面就用A（4）A（5）B（2）B（
3）C（1）来赛。 B（2）是排除A组跑的最快的。
2. A（2）A（3）B（1）C（1）B(2)， 下一次就是A（4）A（5）B（1）C（2）B（2）
3. A（2）B(1)A(3)B(2)C(1), 下一次就是A(3)A(4)B(2)B（3）C（1）
。。。
B(1)A(2)A(3)B(2)C(1), 这种情况下一次就是A（4）B（3)C(1)D(1)E(1)
...
可以都排出一下得出下一轮的排序
overall 6+1+1是8次。 3次是那开始5轮算好的次数， sorry
【在 p*****y 的大作中提到】
: 这个“假设排名是A1B2C3D4E5”是什么意思啊？每个组里5匹马，这个排名是组里第几
: 名的排名呢？
: 而且每个组各自赛一次就是5次了，我估摸着再怎么也得跑个8次吧，暂时还没有什么系
: 统一点的想法。。。
|
c********t
发帖数: 5706 | 6 A懂了。
题B,如何解？ 是不是 7+1+ ((25-1)/2) = 20次？有没有优化的？
2
【在 r**o 的大作中提到】
: 写得太快了
: 详细点哈
: 先是每个组赛1场， 1共赛5场
: 然后赛1场每个组的第一名， 假设跑的最快的依次是ABCDE， 就这就是A1B2C3D4E5的意
: 思啊
: 前面写的就是从这里开是
: 我们先选前3名， 第一名已经知道了，是A（1）， 那么有可能第2，3名的话就是A（2
: ）A（3）和B(1)B(2)C(1),然后他们赛一下， 就知道了前3名。
: 下面就是排列组合了
: 1. A（2）A(3）B（1）B（2）C（1）， 这种情况我们下面就用A（4）A（5）B（2）B（
|
w*****3
发帖数: 101 | 7 A题是7次，
先5次，然后
每组头名比赛
A1， B1， C1， D1， E1
假设是 A1 〉 B1 〉 C1〉 D1 〉 E1
可以移除D1，E1， C2 < C1
剩下
A2，A3，B1，B2，C1 跑一次就可以知道了 2， 3 名 |
r**o
发帖数: 4614 | 8 没有那么复杂， B题就是一个ABCDE后面FG位推进的问题， 回家写个程序就搞出来了。
【在 c********t 的大作中提到】
: A懂了。
: 题B,如何解？ 是不是 7+1+ ((25-1)/2) = 20次？有没有优化的？
:
: 2
|
c********t
发帖数: 5706 | 9 我同意你分析的每次能赛出两名，所以要得到第25名，不是需要 25-1 /2 次吗？再加
上前面 7+1（比第一名），总共是20次啊。
我只是在想，有没有算法不需要从第一名赛起啊？
。
【在 r**o 的大作中提到】
: 没有那么复杂， B题就是一个ABCDE后面FG位推进的问题， 回家写个程序就搞出来了。
|
r**o
发帖数: 4614 | 10 我回去做车的时候再想想， 2个是10分钟内乱想的。 7组派次序应该有更多的关系可以
用到。
【在 c********t 的大作中提到】
: 我同意你分析的每次能赛出两名，所以要得到第25名，不是需要 25-1 /2 次吗？再加
: 上前面 7+1（比第一名），总共是20次啊。
: 我只是在想，有没有算法不需要从第一名赛起啊？
:
: 。
|
