{讨论}{非技术}{数学}

55 views
Skip to first unread message

fancyzm

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

Waterlife Zhang

unread,
Sep 22, 2009, 10:06:27 AM9/22/09
to pon...@googlegroups.com
真不好意思,这个问题我之前在组里问过,不过不是马,是鸽子。在组里搜“25只鸽子,每次5只放飞,找出其中最快的5只”可找到相关主题,另外,这个25匹马赛跑的问题在网上有很多讨论,我记得javaeye上就讨论得就很激烈。

2009/9/22 fancyzm <stu...@163.com>



--
---------------------------------------
Waterlife Zhang
Whu,CS,06'.
Linux,C,Python.
Do one thing and do it well.
---------------------------------------

fancyzm

unread,
Sep 22, 2009, 10:37:18 AM9/22/09
to TopLanguage
谢谢楼上。
刚查了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

unread,
Sep 22, 2009, 11:13:00 AM9/22/09
to TopLanguage
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>
>

wang xin

unread,
Sep 22, 2009, 11:41:21 PM9/22/09
to pon...@googlegroups.com
你的算法好像不正确

最大的是a11

次大的可能是a12和a21

第三大的可能是a13,a22,a31

也就是说有可能是这样的组合a11, a12, a31 ... 而这个用你的算法是求不出来的。

其实这个就是kth smallest element的算法,MIT 的 Introduction to Algorithms 里有详细的分析。


2009/9/22 fancyzm <stu...@163.com>

fancyzm

unread,
Sep 23, 2009, 12:27:10 AM9/23/09
to TopLanguage
@wang xin :

你说的可能性是不可能成立的啊,如果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.

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

谢铸聪

unread,
Sep 23, 2009, 1:39:28 AM9/23/09
to pon...@googlegroups.com

弱弱问一声:不能计时么?

wang xin

unread,
Sep 23, 2009, 5:55:37 AM9/23/09
to pon...@googlegroups.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 谢铸聪 <zhuco...@gmail.com>

弱弱问一声:不能计时么?


Beyond

unread,
Sep 23, 2009, 6:55:13 AM9/23/09
to pon...@googlegroups.com
这个算法是错误的   假定一种数据:
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 <stu...@163.com>

fancyzm

unread,
Sep 23, 2009, 7:31:32 AM9/23/09
to TopLanguage
@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.

OxFAN

unread,
Sep 23, 2009, 7:51:54 AM9/23/09
to pon...@googlegroups.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 <xer...@gmail.com>

Beyond

unread,
Sep 23, 2009, 9:14:23 AM9/23/09
to pon...@googlegroups.com
不是等不等的问题

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

Baiqi

unread,
Sep 23, 2009, 10:16:57 AM9/23/09
to TopLanguage
用信息论的观点,只需要Log5(25)=5次

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>
>
> >> 弱弱问一声:不能计时么?

Message has been deleted

fancyzm

unread,
Sep 23, 2009, 10:06:05 AM9/23/09
to TopLanguage
@Beyond:
呃。。失误。重新翻前辈们的帖子去,详细的看看。

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

unread,
Sep 23, 2009, 12:06:55 PM9/23/09
to TopLanguage
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次。
Message has been deleted
Message has been deleted

鋆邓

unread,
Sep 23, 2009, 9:36:36 PM9/23/09
to pon...@googlegroups.com
=。= 你这个式子来的毫无理由啊
首先一次比赛的信息量是lg(5!);,也就是说是5个数的排列
其次总需要的信息量也不是25,也不是25!,而是C(25, 5)
再其次,信息论的这部分观点从来只能证明下界,也就是至少需要,何时可以证明只需要了……

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

husir

unread,
Sep 23, 2009, 9:12:48 PM9/23/09
to pon...@googlegroups.com
问题简单化,3*3矩阵
10 8 7
9  6  5
4  3  2
 第n+1之后赛完之后,如楼主所说得出上述矩阵,那么第n+2赛,则结果为10,8,7

结论错误。
所以,楼主所说算法不可能成立,不可能有这么低的计算复杂度的。

husir

unread,
Sep 23, 2009, 9:50:28 PM9/23/09
to pon...@googlegroups.com
对于算法分析来说,任何满足条件的n*n的都是可以成立的。
举一个3*3的例子只是为了看着方便。5*5也是可以举出来的的。

我觉得对于算法题目来说 最终目的是希望找出一个复杂度低的算法

cui nk

unread,
Sep 24, 2009, 1:26:22 AM9/24/09
to TopLanguage
为啥取每组前三名 难道所有的第四第五都不考虑了?

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

unread,
Sep 24, 2009, 10:15:20 AM9/24/09
to pon...@googlegroups.com
Log5(25)是怎样得来的?
不是很了解信息论,不能给下大概的步骤?

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

hongtao wang

unread,
Sep 24, 2009, 10:13:13 PM9/24/09
to pon...@googlegroups.com
log5(25)不是2么?

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

Baiqi

unread,
Sep 24, 2009, 11:00:56 PM9/24/09
to TopLanguage
不好意思,没看仔细,是这样:
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

unread,
Sep 25, 2009, 1:26:52 AM9/25/09
to pon...@googlegroups.com
没看明白结论为7的答案。

我认为最好的情况是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
其中第一名是a1,候选马为:
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

unread,
Sep 26, 2009, 9:00:14 AM9/26/09
to pon...@googlegroups.com
楼上的算法还算比较靠谱的,要2n次肯定能赛出来结果的
 

我当时考虑的是在前6次之后,在每一组的最后一名之间比赛,只取第一名,其他的几名就直接淘汰,之后进行循环,直到淘汰的剩下n个。

husir

unread,
Sep 26, 2009, 9:06:18 AM9/26/09
to pon...@googlegroups.com


在前6次之后, 前5名的候选马就是上述矩阵了。
a1   a2   a3   a4   a5
b1   b2   b3   b4 
c1   c2   c3 
d1   d2
e1
而后,采用淘汰法就行了。如在 a5,b4,c3,d2,e1之间比赛,进行淘汰,直到剩下5个。

Wenbo Yang

unread,
Oct 17, 2009, 6:43:25 AM10/17/09
to pon...@googlegroups.com
嘿嘿,我今天翻出来这道题目,尝试分析了一下,写了篇博客。地址在:

http://blog.solrex.cn/articles/25-horses-problem.html

有兴趣的朋友可以过去围观一下,看看写的对不对。

文博

2009/9/22 fancyzm <stu...@163.com>

      昨天无意中看到的一个面试题(貌似是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
Reply all
Reply to author
Forward
0 new messages