{讨论}{非技术}{数学}
fancyzm
但赛场只有5条赛道，也就是一次只能给最多5匹马提供比赛机会决出那匹快哪匹慢。设计一个赛跑策略，使得使用赛道的次数最少且可以得出跑的最快的前5匹
马。
我把这个题推广下，就是n*n个数，有种"天平"，其每次输入是小于等于n个数，输出是输入数的一个大小排列。问，最少应该使用天平多少次使得
可以得出n*n个数里面按从大到小排列时，前面n个数是多少。
早上上英语课之前，用笔模拟了下，得到的结果是只要使用天平 n+2次就可以精确得出前面n个数。
仔细归纳下自己的想法，(上面结论成立的条件是n*n没有相同的数),从我本身感觉上来说，n+2应该是一个使用天平次数的下届，但是不知道怎
么证明。或者大家有更好的策略么？
Waterlife Zhang
--
---------------------------------------
Waterlife Zhang
Whu,CS,06'.
Linux,C,Python.
Do one thing and do it well.
---------------------------------------
fancyzm
刚查了javaeye。。讨论的确是很热烈。
但都忽视了一点就是，假如，两匹马的速度是一样的呢？怎么比？
我的思路是先分成5个小组，分别赛，组内比出排名，然后让这5组的第一名再赛，最后我们可以得到下面一个矩阵
a11 a12 a13 a14 a15
a21 a22 a23 a24 a25
a31 a32 a33 a34 a35
a41 a42 a43 a44 a45
a51 a52 a53 a54 a55
矩阵列是有序的(每一列代表最开始的5组)，并且矩阵的第一行是有序的。
考虑第七次赛 a15,a24 ,a33,a42,a51
如果是a15赢的话，那么 前5是a11 a12 a13 a14 a15
如果是a24赢的话，那么 前5是a11 a12 a13 a14 a24
如果是a33赢的话，那么 前5是a11 a12 a13 a23 a33
如果是a42赢的话，那么 前5是a11 a12 a22 a32 a42
如果是a51赢的话，那么 前5是a11 a21 a31 a41 a51
证明很简单的，由于有序，选5个组的时候只能从左上开始，先往右走，然后往下走。直至矩阵的右上连左下的对角线。
有位前辈做了下推广，不过是n*n 和m条赛道的，但是没有具体分析，下面没人跟着讨论。
我的想法是m=n的话，那么这种方法应该就是n+2；但貌似没有前辈给出下届的证明。
On 9月22日, 下午10时06分, Waterlife Zhang <shuiflo...@gmail.com> wrote:
> 真不好意思，这个问题我之前在组里问过，不过不是马，是鸽子。在组里搜"25只鸽子，每次5只放飞，找出其中最快的5只"可找到相关主题，另外，这个25匹马赛-跑的问题在网上有很多讨论，我记得javaeye上就讨论得就很激烈。
>
> 2009/9/22 fancyzm <stud...@163.com>
fancyzm
On 9月22日, 下午10时06分, Waterlife Zhang <shuiflo...@gmail.com> wrote:
> 真不好意思，这个问题我之前在组里问过，不过不是马，是鸽子。在组里搜"25只鸽子，每次5只放飞，找出其中最快的5只"可找到相关主题，另外，这个25匹马赛-跑的问题在网上有很多讨论，我记得javaeye上就讨论得就很激烈。
>
> 2009/9/22 fancyzm <stud...@163.com>
>
wang xin
fancyzm
你说的可能性是不可能成立的啊，如果a31能选的话，那么a21是必然能选的。也就是说选择前5的时候只能从矩阵的左上角开始，往右走，然后再往下走，
结束。注意矩阵的列有序性和第一行的有序性。这也就保证了在选取的时候次大和第三大。。的可能性是唯一的。
谢谢ls提供的链接。最小k元素，对就是这个意思，但，我们要充分利用一次可以比较n个元素的这个条件。也就是根本没必要o(n*n)的。
On 9月23日, 上午11时41分, wang xin <xera...@gmail.com> wrote:
> 你的算法好像不正确
> 最大的是a11
>
> 次大的可能是a12和a21
>
> 第三大的可能是a13,a22,a31
>
> 也就是说有可能是这样的组合a11, a12, a31 ... 而这个用你的算法是求不出来的。
>
> 其实这个就是kth smallest element的算法，MIT 的 Introduction to Algorithms 里有详细的分析。
>
> 参见：http://videolectures.net/mit6046jf05_demaine_lec06/
>
> 2009/9/22 fancyzm <stud...@163.com>
>
>
>
> > ok，谢谢ls。javaeye好多前辈啊。
>
> > On 9月22日, 下午10时06分, Waterlife Zhang <shuiflo...@gmail.com> wrote:
>
> > 真不好意思，这个问题我之前在组里问过，不过不是马，是鸽子。在组里搜"25只鸽子，每次5只放飞，找出其中最快的5只"可找到相关主题，另外，这个25匹马赛--跑的问题在网上有很多讨论，我记得javaeye上就讨论得就很激烈。
>
> > > 2009/9/22 fancyzm <stud...@163.com>
>
> > > > 昨天无意中看到的一个面试题(貌似是google的，别人提供的链接),题目意思大概是这样的。现在有5*5匹跑马，外加一个跑马赛场，
> > > > 但赛场只有5条赛道，也就是一次只能给最多5匹马提供比赛机会决出那匹快哪匹慢。设计一个赛跑策略，使得使用赛道的次数最少且可以得出跑的最快的前5匹
> > > > 马。
> > > > 我把这个题推广下，就是n*n个数，有种"天平"，其每次输入是小于等于n个数，输出是输入数的一个大小排列。问，最少应该使用天平多少次使得
> > > > 可以得出n*n个数里面按从大到小排列时，前面n个数是多少。
> > > > 早上上英语课之前，用笔模拟了下，得到的结果是只要使用天平 n+2次就可以精确得出前面n个数。
> > > > 仔细归纳下自己的想法，(上面结论成立的条件是n*n没有相同的数),从我本身感觉上来说，n+2应该是一个使用天平次数的下届，但是不知道怎
> > > > 么证明。或者大家有更好的策略么？
>
> > > --
> > > ---------------------------------------
> > > Waterlife Zhang
> > > Whu,CS,06'.
> > > Linux,C,Python.
> > > Do one thing and do it well.
> > > ---------------------------------------- 隐藏被引用文字 -
>
> - 显示引用的文字 -
谢铸聪
弱弱问一声：不能计时么？
wang xin
Beyond
fancyzm
嗯，我也发现了这个问题，我在最开始的策略说明里面就已经强调了，没有相同的两个数，所有数都是严格不等的。
谢谢！
On 9月23日, 下午6时55分, Beyond <beyond...@gmail.com> wrote:
> 这个算法是错误的 假定一种数据:
> 80 75 70 65 60
> 74 60 68 63 50
> 70 55 67 60 40
> 60 50 60 50 30
> 10 10 10 10 10
> 按照你的算法,得到的是80 75 70 68 67
> 而实际是:80 75 74 70 70
> 这个问题应该是磁盘排序的问题的变种吧 在不能计时的情况下 我觉得n * n 匹马 m 条跑道起码需要
> ( int )( ( n * n - 1 + m ) / m ) * 2 次
>
> 2009/9/22 fancyzm <stud...@163.com>
>
>
>
> > 谢谢楼上。
> > 刚查了javaeye。。讨论的确是很热烈。
>
> > 但都忽视了一点就是，假如，两匹马的速度是一样的呢？怎么比？
>
> > 我的思路是先分成5个小组，分别赛，组内比出排名，然后让这5组的第一名再赛，最后我们可以得到下面一个矩阵
>
> > a11 a12 a13 a14 a15
> > a21 a22 a23 a24 a25
> > a31 a32 a33 a34 a35
> > a41 a42 a43 a44 a45
> > a51 a52 a53 a54 a55
>
> > 矩阵列是有序的(每一列代表最开始的5组)，并且矩阵的第一行是有序的。
>
> > 考虑第七次赛 a15,a24 ,a33,a42,a51
>
> > 如果是a15赢的话，那么 前5是a11 a12 a13 a14 a15
>
> > 如果是a24赢的话，那么 前5是a11 a12 a13 a14 a24
>
> > 如果是a33赢的话，那么 前5是a11 a12 a13 a23 a33
>
> > 如果是a42赢的话，那么 前5是a11 a12 a22 a32 a42
>
> > 如果是a51赢的话，那么 前5是a11 a21 a31 a41 a51
>
> > 证明很简单的，由于有序，选5个组的时候只能从左上开始，先往右走，然后往下走。直至矩阵的右上连左下的对角线。
>
> > 有位前辈做了下推广，不过是n*n 和m条赛道的，但是没有具体分析，下面没人跟着讨论。
>
> > 我的想法是m=n的话，那么这种方法应该就是n+2；但貌似没有前辈给出下届的证明。
>
> > On 9月22日, 下午10时06分, Waterlife Zhang <shuiflo...@gmail.com> wrote:
>
> > 真不好意思，这个问题我之前在组里问过，不过不是马，是鸽子。在组里搜"25只鸽子，每次5只放飞，找出其中最快的5只"可找到相关主题，另外，这个25匹马赛--跑的问题在网上有很多讨论，我记得javaeye上就讨论得就很激烈。
>
> > > 2009/9/22 fancyzm <stud...@163.com>
>
> > > > 昨天无意中看到的一个面试题(貌似是google的，别人提供的链接),题目意思大概是这样的。现在有5*5匹跑马，外加一个跑马赛场，
> > > > 但赛场只有5条赛道，也就是一次只能给最多5匹马提供比赛机会决出那匹快哪匹慢。设计一个赛跑策略，使得使用赛道的次数最少且可以得出跑的最快的前5匹
> > > > 马。
> > > > 我把这个题推广下，就是n*n个数，有种"天平"，其每次输入是小于等于n个数，输出是输入数的一个大小排列。问，最少应该使用天平多少次使得
> > > > 可以得出n*n个数里面按从大到小排列时，前面n个数是多少。
> > > > 早上上英语课之前，用笔模拟了下，得到的结果是只要使用天平 n+2次就可以精确得出前面n个数。
> > > > 仔细归纳下自己的想法，(上面结论成立的条件是n*n没有相同的数),从我本身感觉上来说，n+2应该是一个使用天平次数的下届，但是不知道怎
> > > > 么证明。或者大家有更好的策略么？
>
> > > --
> > > ---------------------------------------
> > > Waterlife Zhang
> > > Whu,CS,06'.
> > > Linux,C,Python.
> > > Do one thing and do it well.
OxFAN
Beyond
Baiqi
On 9月23日, 下午7时51分, OxFAN <odayf...@gmail.com> wrote:
> 是O(n)的想了下 大概是这样
> 2009/9/23 wang xin <xera...@gmail.com>
>
>
>
> > 25, 24, 21, 20, 19
> > 23, 18, 17, 16, 15
>
> > 22, 14, 13, 12, 11
>
> > 10, 9, 8, 7, 6
>
> > 5, 4, 3, 2, 1
>
> > PS 算法的复杂度是O(n)
>
> > 2009/9/23 谢铸聪 <zhucong...@gmail.com>
>
> >> 弱弱问一声：不能计时么？
fancyzm
呃。。失误。重新翻前辈们的帖子去，详细的看看。
On 9月23日, 下午9时14分, Beyond <beyond...@gmail.com> wrote:
> 不是等不等的问题
>
> 2009/9/23 fancyzm <stud...@163.com>
> > 真不好意思，这个问题我之前在组里问过，不过不是马，是鸽子。在组里搜"25只鸽子，每次5只放飞，找出其中最快的5只"可找到相关主题，另外，这个25匹马赛---跑的问题在网上有很多讨论，我记得javaeye上就讨论得就很激烈。
>
> > > > > 2009/9/22 fancyzm <stud...@163.com>
>
> > 昨天无意中看到的一个面试题(貌似是google的，别人提供的链接),题目意思大概是这样的。现在有5*5匹跑马，外加一个跑马赛场，
>
> > 但赛场只有5条赛道，也就是一次只能给最多5匹马提供比赛机会决出那匹快哪匹慢。设计一个赛跑策略，使得使用赛道的次数最少且可以得出跑的最快的前5匹
> > > > > > 马。
>
> > 我把这个题推广下，就是n*n个数，有种"天平"，其每次输入是小于等于n个数，输出是输入数的一个大小排列。问，最少应该使用天平多少次使得
> > > > > > 可以得出n*n个数里面按从大到小排列时，前面n个数是多少。
> > > > > > 早上上英语课之前，用笔模拟了下，得到的结果是只要使用天平 n+2次就可以精确得出前面n个数。
>
> > 仔细归纳下自己的想法，(上面结论成立的条件是n*n没有相同的数),从我本身感觉上来说，n+2应该是一个使用天平次数的下届，但是不知道怎
> > > > > > 么证明。或者大家有更好的策略么？
>
> > > > > --
> > > > > ---------------------------------------
> > > > > Waterlife Zhang
> > > > > Whu,CS,06'.
> > > > > Linux,C,Python.
> > > > > Do one thing and do it well.
> > > > > ---------------------------------------- 隐藏被引用文字 -
>
> > > - 显示引用的文字 -- 隐藏被引用文字 -
>
> - 显示引用的文字 -
raymond
基本类似Median of Medians algorithm
假设每次都是最坏情况，则每次需要比较的次数，M=(7/10)*N*LOGN, (7/10)^2*N*LOG(7/10)N, ..., 最终收
敛，用母函数可以解这个方程，这是系统需要比较的次数。然后我们使用条数为5的跑到，每次可以比较的次数为K=5*LOG5（最优比较），所以最终大概
使用跑道次数为M/K，我大概画了一下，是11次。
鋆邓
husir
husir
cui nk
On 9月23日, 下午7时51分, OxFAN <odayf...@gmail.com> wrote:
> 是O(n)的想了下 大概是这样
> 2009/9/23 wang xin <xera...@gmail.com>
>
>
>
> > 25, 24, 21, 20, 19
> > 23, 18, 17, 16, 15
>
> > 22, 14, 13, 12, 11
>
> > 10, 9, 8, 7, 6
>
> > 5, 4, 3, 2, 1
>
> > PS 算法的复杂度是O(n)
>
> > 2009/9/23 谢铸聪 <zhucong...@gmail.com>
>
> >> 弱弱问一声：不能计时么？
OxFAN
hongtao wang
Baiqi
log5(5!)=3
On 9月25日, 上午10时13分, hongtao wang <wanghongta...@gmail.com> wrote:
> log5(25)不是2么？
>
> 2009/9/24 OxFAN <odayf...@gmail.com>
>
>
>
> > Log5(25)是怎样得来的？不是很了解信息论，不能给下大概的步骤？
>
> > 2009/9/23 Baiqi <dingxiaofeng...@gmail.com>
Aaron Zheng
我认为最好的情况是7次，而最坏的情况是10次。
其实很简单,原因如下：
前6次就不用说了，得出矩阵：
a1 a2 a3 a4 a5
b1 b2 b3 b4 b5
c1 c2 c3 c4 c5
d1 d2 d3 d4 d5
e1 e2 e3 e4 e5
a2 a3 a4 a5
b1 b2 b3 b4
c1 c2 c3
d1 d2
e1
第7次应该比较候选马中每组的第一名比较：a2,b1,c1,d1,e1.
这样可以得出第二名。比如是c1胜利，候选马为：
a2 a3 a4 a5
b1 b2 b3 b4
c2 c3
d1 d2
e1
当然这里有理想的情况，选取a5,b1,c1,d1,e1 若a5胜利，则前5名是 a1 a2 a3 a4 a5，这为最理想的最小次数。
第8，9，10次同理，依次可以选出所有的前5名。
当然最差的情况是比较10次，最好的情况是比较7次。当然其它次数也是有可能的，但都需要想7次那样的运气才行。
欢迎请大家评论。
husir
楼上的算法还算比较靠谱的，要2n次肯定能赛出来结果的
husir
b1 b2 b3 b4
d1 d2
e1
Wenbo Yang
http://blog.solrex.cn/articles/25-horses-problem.html
有兴趣的朋友可以过去围观一下，看看写的对不对。
文博
昨天无意中看到的一个面试题(貌似是google的，别人提供的链接),题目意思大概是这样的。现在有5*5匹跑马，外加一个跑马赛场，
但赛场只有5条赛道，也就是一次只能给最多5匹马提供比赛机会决出那匹快哪匹慢。设计一个赛跑策略，使得使用赛道的次数最少且可以得出跑的最快的前5匹
马。
我把这个题推广下，就是n*n个数，有种"天平"，其每次输入是小于等于n个数，输出是输入数的一个大小排列。问，最少应该使用天平多少次使得
可以得出n*n个数里面按从大到小排列时，前面n个数是多少。
早上上英语课之前，用笔模拟了下，得到的结果是只要使用天平 n+2次就可以精确得出前面n个数。
仔细归纳下自己的想法，(上面结论成立的条件是n*n没有相同的数),从我本身感觉上来说，n+2应该是一个使用天平次数的下届，但是不知道怎
么证明。或者大家有更好的策略么？
--
Wenbo YANG
Homepage ---> http://solrex.cn
Blog | Solrex Shuffling ---> http://blog.solrex.cn