>       昨天无意中看到的一个面试题(貌似是google的，别人提供的链接),题目意思大概是这样的。现在有5*5匹跑马，外加一个跑马赛场，
> 但赛场只有5条赛道，也就是一次只能给最多5匹马提供比赛机会决出那匹快哪匹慢。设计一个赛跑策略，使得使用赛道的次数最少且可以得出跑的最快的前5匹
> 马。
>    我把这个题推广下，就是n*n个数，有种"天平"，其每次输入是小于等于n个数，输出是输入数的一个大小排列。问，最少应该使用天平多少次使得
> 可以得出n*n个数里面按从大到小排列时，前面n个数是多少。
>    早上上英语课之前，用笔模拟了下，得到的结果是只要使用天平 n+2次就可以精确得出前面n个数。
>    仔细归纳下自己的想法，(上面结论成立的条件是n*n没有相同的数),从我本身感觉上来说，n+2应该是一个使用天平次数的下届，但是不知道怎
> 么证明。或者大家有更好的策略么？

> 真不好意思，这个问题我之前在组里问过，不过不是马，是鸽子。在组里搜"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.
> ---------------------------------------

> 真不好意思，这个问题我之前在组里问过，不过不是马，是鸽子。在组里搜"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.
> ---------------------------------------

> 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.
> > ---------------------------------------

> 你的算法好像不正确
> 最大的是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.
> > > ---------------------------------------- 隐藏被引用文字 -

> - 显示引用的文字 -

> 弱弱问一声：不能计时么？

> 谢谢楼上。
> 刚查了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.
> > ---------------------------------------

> 这个算法是错误的   假定一种数据:
> 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.
> > > ---------------------------------------- 隐藏被引用文字 -

> - 显示引用的文字 -

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

>> 弱弱问一声：不能计时么？

> @Beyond：
> 嗯，我也发现了这个问题，我在最开始的策略说明里面就已经强调了，没有相同的两个数，所有数都是严格不等的。
> 谢谢！

> 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.
> > > > ---------------------------------------- 隐藏被引用文字 -

> > - 显示引用的文字 -

> 是O(n)的想了下  大概是这样
> 将5*5匹马平均分成5组 a,b,c,d,e
> 每一组进行一次排序，得出以下矩阵

> a1 b1 c1 d1 e1
> a2 b2 c2 d2 e2
> a3 b3 c3 d3 e3
> a4 b4 c4 d4 e4
> a5 b5 c5 d5 e5

> 其中a1>a2>a3>a4>a5 ;  b1>b2>b3.... ; e1>e2>e3>e4>e5
> 做了5次排序

> 每组取前三名：
> a1 b1 c1 d1 e1
> a2 b2 c2 d2 e2
> a3 b3 c3 d3 e3

> 对a1 b1 c1 d1 e1 做一次排序，不妨设 b1 > d1 > c1 > a1 > e1
> 可以得到
> b1 b2 b3
> d1 d2 d3
> c1 c2 c3
> a1 a2 a3
> e1 e2 e3

> 这里

> b1 > b2 > b3
> b1 > d1 > c1 > a1 > e1

> 所以
> 前5个最快的是
> b1 b2 b3 d1 c1 a1
> 如果分出前五名名次，则再做一次排序
> 这样最多用7次排序
> 不分出前五名的名次的话则需要6次

> 不知有没有错误...

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

> >> 弱弱问一声：不能计时么？

> 不是等不等的问题

> 2009/9/23 fancyzm <stud...@163.com>

> > @Beyond：
> > 嗯，我也发现了这个问题，我在最开始的策略说明里面就已经强调了，没有相同的两个数，所有数都是严格不等的。
> > 谢谢！

> > 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.
> > > > > ---------------------------------------- 隐藏被引用文字 -

> > > - 显示引用的文字 -- 隐藏被引用文字 -

> - 显示引用的文字 -

> 谢谢楼上。
> 刚查了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.
> > ---------------------------------------

> http://en.wikipedia.org/wiki/Selection_algorithm
> 基本类似Median of Medians algorithm
> 假设每次都是最坏情况，则每次需要比较的次数，M=(7/10)*N*LOGN, (7/10)^2*N*LOG(7/10)N, ..., 最终收
> 敛，用母函数可以解这个方程，这是系统需要比较的次数。然后我们使用条数为5的跑到，每次可以比较的次数为K=5*LOG5（最优比较），所以最终大概
> 使用跑道次数为M/K，我大概画了一下，是11次。

> On 9月22日, 下午10时37分, fancyzm <stud...@163.com> wrote:

> > 谢谢楼上。
> > 刚查了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.
> > > ---------------------------------------- 隐藏被引用文字 -

> - 显示引用的文字 -

> 用信息论的观点,只需要Log5(25)=5次

> On 9月23日, 下午7时51分, OxFAN <odayf...@gmail.com> wrote:
> > 是O(n)的想了下  大概是这样
>  > 将5*5匹马平均分成5组 a,b,c,d,e
> > 每一组进行一次排序，得出以下矩阵

> > a1 b1 c1 d1 e1
> > a2 b2 c2 d2 e2
> > a3 b3 c3 d3 e3
> > a4 b4 c4 d4 e4
> > a5 b5 c5 d5 e5

> > 其中a1>a2>a3>a4>a5 ;  b1>b2>b3.... ; e1>e2>e3>e4>e5
> > 做了5次排序

> > 每组取前三名：
> > a1 b1 c1 d1 e1
> > a2 b2 c2 d2 e2
> > a3 b3 c3 d3 e3

> > 对a1 b1 c1 d1 e1 做一次排序，不妨设 b1 > d1 > c1 > a1 > e1
> > 可以得到
> > b1 b2 b3
> > d1 d2 d3
> > c1 c2 c3
> > a1 a2 a3
> > e1 e2 e3

> > 这里

> > b1 > b2 > b3
> > b1 > d1 > c1 > a1 > e1

> > 所以
> > 前5个最快的是
> > b1 b2 b3 d1 c1 a1
> > 如果分出前五名名次，则再做一次排序
> > 这样最多用7次排序
> > 不分出前五名的名次的话则需要6次

> > 不知有没有错误...

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

> > >> 弱弱问一声：不能计时么？

> 是O(n)的想了下  大概是这样
> 将5*5匹马平均分成5组 a,b,c,d,e
> 每一组进行一次排序，得出以下矩阵

> a1 b1 c1 d1 e1
> a2 b2 c2 d2 e2
> a3 b3 c3 d3 e3
> a4 b4 c4 d4 e4
> a5 b5 c5 d5 e5

> 其中a1>a2>a3>a4>a5 ;  b1>b2>b3.... ; e1>e2>e3>e4>e5
> 做了5次排序

> 每组取前三名：
> a1 b1 c1 d1 e1
> a2 b2 c2 d2 e2
> a3 b3 c3 d3 e3

> 对a1 b1 c1 d1 e1 做一次排序，不妨设 b1 > d1 > c1 > a1 > e1
> 可以得到
> b1 b2 b3
> d1 d2 d3
> c1 c2 c3
> a1 a2 a3
> e1 e2 e3

> 这里

> b1 > b2 > b3
> b1 > d1 > c1 > a1 > e1

> 所以
> 前5个最快的是
> b1 b2 b3 d1 c1 a1
> 如果分出前五名名次，则再做一次排序
> 这样最多用7次排序
> 不分出前五名的名次的话则需要6次

> 不知有没有错误...

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

> >> 弱弱问一声：不能计时么？

> 用信息论的观点,只需要Log5(25)=5次

> On 9月23日, 下午7时51分, OxFAN <odayf...@gmail.com> wrote:
> > 是O(n)的想了下  大概是这样
> > 将5*5匹马平均分成5组 a,b,c,d,e
> > 每一组进行一次排序，得出以下矩阵

> > a1 b1 c1 d1 e1
> > a2 b2 c2 d2 e2
> > a3 b3 c3 d3 e3
> > a4 b4 c4 d4 e4
> > a5 b5 c5 d5 e5

> > 其中a1>a2>a3>a4>a5 ;  b1>b2>b3.... ; e1>e2>e3>e4>e5
> > 做了5次排序

> > 每组取前三名：
> > a1 b1 c1 d1 e1
> > a2 b2 c2 d2 e2
> > a3 b3 c3 d3 e3

> > 对a1 b1 c1 d1 e1 做一次排序，不妨设 b1 > d1 > c1 > a1 > e1
> > 可以得到
> > b1 b2 b3
> > d1 d2 d3
> > c1 c2 c3
> > a1 a2 a3
> > e1 e2 e3

> > 这里

> > b1 > b2 > b3
> > b1 > d1 > c1 > a1 > e1

> > 所以
> > 前5个最快的是
> > b1 b2 b3 d1 c1 a1
> > 如果分出前五名名次，则再做一次排序
> > 这样最多用7次排序
> > 不分出前五名的名次的话则需要6次

> > 不知有没有错误...

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

> > >> 弱弱问一声：不能计时么？

> Log5(25)是怎样得来的？不是很了解信息论，不能给下大概的步骤？

> 2009/9/23 Baiqi <dingxiaofeng...@gmail.com>

>> 用信息论的观点,只需要Log5(25)=5次

>> On 9月23日, 下午7时51分, OxFAN <odayf...@gmail.com> wrote:
>> > 是O(n)的想了下  大概是这样
>> > 将5*5匹马平均分成5组 a,b,c,d,e
>> > 每一组进行一次排序，得出以下矩阵

>> > a1 b1 c1 d1 e1
>> > a2 b2 c2 d2 e2
>> > a3 b3 c3 d3 e3
>> > a4 b4 c4 d4 e4
>> > a5 b5 c5 d5 e5

>> > 其中a1>a2>a3>a4>a5 ;  b1>b2>b3.... ; e1>e2>e3>e4>e5
>> > 做了5次排序

>> > 每组取前三名：
>> > a1 b1 c1 d1 e1
>> > a2 b2 c2 d2 e2
>> > a3 b3 c3 d3 e3

>> > 对a1 b1 c1 d1 e1 做一次排序，不妨设 b1 > d1 > c1 > a1 > e1
>> > 可以得到
>> > b1 b2 b3
>> > d1 d2 d3
>> > c1 c2 c3
>> > a1 a2 a3
>> > e1 e2 e3

>> > 这里

>> > b1 > b2 > b3
>> > b1 > d1 > c1 > a1 > e1

>> > 所以
>> > 前5个最快的是
>> > b1 b2 b3 d1 c1 a1
>> > 如果分出前五名名次，则再做一次排序
>> > 这样最多用7次排序
>> > 不分出前五名的名次的话则需要6次

>> > 不知有没有错误...

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

>> > >> 弱弱问一声：不能计时么？

> log5(25)不是2么？

> 2009/9/24 OxFAN <odayf...@gmail.com>

> > Log5(25)是怎样得来的？不是很了解信息论，不能给下大概的步骤？

> > 2009/9/23 Baiqi <dingxiaofeng...@gmail.com>

> >> 用信息论的观点,只需要Log5(25)=5次

> >> On 9月23日, 下午7时51分, OxFAN <odayf...@gmail.com> wrote:
> >> > 是O(n)的想了下  大概是这样
> >> > 将5*5匹马平均分成5组 a,b,c,d,e
> >> > 每一组进行一次排序，得出以下矩阵

> >> > a1 b1 c1 d1 e1
> >> > a2 b2 c2 d2 e2
> >> > a3 b3 c3 d3 e3
> >> > a4 b4 c4 d4 e4
> >> > a5 b5 c5 d5 e5

> >> > 其中a1>a2>a3>a4>a5 ;  b1>b2>b3.... ; e1>e2>e3>e4>e5
> >> > 做了5次排序

> >> > 每组取前三名：
> >> > a1 b1 c1 d1 e1
> >> > a2 b2 c2 d2 e2
> >> > a3 b3 c3 d3 e3

> >> > 对a1 b1 c1 d1 e1 做一次排序，不妨设 b1 > d1 > c1 > a1 > e1
> >> > 可以得到
> >> > b1 b2 b3
> >> > d1 d2 d3
> >> > c1 c2 c3
> >> > a1 a2 a3
> >> > e1 e2 e3

> >> > 这里

> >> > b1 > b2 > b3
> >> > b1 > d1 > c1 > a1 > e1

> >> > 所以
> >> > 前5个最快的是
> >> > b1 b2 b3 d1 c1 a1
> >> > 如果分出前五名名次，则再做一次排序
> >> > 这样最多用7次排序
> >> > 不分出前五名的名次的话则需要6次

> >> > 不知有没有错误...

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

> >> > >> 弱弱问一声：不能计时么？