论坛首页 Java企业应用论坛

网上没找到答案的逻辑推理题

浏览 17220 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2009-09-05  
今天去一家游戏公司面试,这一题没推出来。在网上也没找到合理的答案。只能劳烦大家了。请大家不要用穷举法,如果知道答案请将推理过程写出来。谢了。

甲、乙、丙三队互相比赛,每两队之间都比赛了同样多的场数,然后根据得分的多少,决定哪一队是最后的胜利者。规则是每场比赛,胜者得3分,负者得0分,平局各得1分。

甲队在全部比赛结束之后,得意洋洋的说:“我们队赢的场数比你们两队中的任何一队都多。”

乙队反唇相击,道:“我们队输的场数比你们两队中的任何一队都少。”

唯有丙队发言人一声不吭。

你认为丙队会排名第一吗?

注意:甲、乙、丙三队,每两队之间的比赛场数可以不止一场。 甲、乙、丙三队互相比赛,每两队之间都比赛了同样多的场数,然后根据得分的多少,决定哪一队是最后的胜利者。规则是每场比赛,胜者得3分,负者得0分,平局各得1分。

甲队在全部比赛结束之后,得意洋洋的说:“我们队赢的场数比你们两队中的任何一队都多。”

乙队反唇相击,道:“我们队输的场数比你们两队中的任何一队都少。”

唯有丙队发言人一声不吭。

你认为丙队会排名第一吗?

注意:甲、乙、丙三队,每两队之间的比赛场数可以不止一场。
   发表时间:2009-09-05  
   假设双循环赛,则每队4场比赛,乙输的最少(假设不输),那么甲和丙至少输一场,甲输一场则另外两队有一队赢一场,甲赢的最多,那么至少赢两场。也就是说甲至少6分。丙输了一场了要想第一只有大于6分,意味着至少和甲赢的一样多,这就与甲赢的最多矛盾了,所以不可能第一。其实只要甲赢的超过一场,丙就不可能第一。在这个双循环的规则下:甲2胜1平1负,乙1胜3平,丙2负2平。
   不是这种赛制的没多想,因为我喜欢踢实况,嘿嘿。
0 请登录后投票
   发表时间:2009-09-05  
丙是可以第一的。用穷举可以算的出来。如
     甲 胜8 平4 负10
   乙 胜6 平11 负5
   丙 胜7 平9 负6
但用穷举解题只是下下之选。重在推理过程。
不知道答案的朋友也请支持下吧。认会解的人看到。
重在过程。
0 请登录后投票
   发表时间:2009-09-06  
3队之间进行了 n轮比赛 共记3n场比赛 每队参加其中2n场
x场 平y场 总分 3x+2y
甲胜 a1 平b1 负 2n-a1-b1
乙胜 a2 平b2 负 2n-a2-b2
丙胜 a3 平b3 负 2n-a3-b3
其中 a1,a2,a3,b1,b2,b3<=2n
其中 a1+a2+a3=x
     b1+b2+b3=y
甲胜最多     a1>a2, a1>a3
乙负最少     a2+b2>a1+b1 a2+b2>a3+b3
如果丙第一   3a3+b3>3a2+b2 3a3+b3>3a1+b1
求n的最小解

0 请登录后投票
   发表时间:2009-09-06  
已知

Score[x] = 3 * Win[x] + Tie[x]
Score[y] = 3 * Win[y] + Tie[y]
Score[z] = 3 * Win[z] + Tie[z]

Win[x] + Win[y] + Win[z] = Los[x] + Los[y] + Los[z] -- (1)

Win[x] + Tie[x] + Los[x] = Win[y] + Tie[y] + Los[y] = Win[z] + Tie[z] + Los[z]  -- (2)

Win[x] > Win[y],Win[x] > Win[z],Loss[y] < Loss[x],Loss[y] < Loss[z]

代入2式消去 Tie[x], Tie[y]
Score[x] = 2 * Win[x] + (Win[z] + Tie[z] + Los[z] - Los[x])
Score[y] = 2 * Win[y] + (Win[z] + Tie[z] + Los[z] - Los[y])
Score[z] = 3 * Win[z] + Tie[z]

丙获胜的条件:
Score[z] > Score[x] 且 Score[z] > Score[y]


3 * Win[z] + Tie[z] > 2 * Win[x] + (Win[z] + Tie[z] + Los[z] - Los[x])
3 * Win[z] + Tie[z] > 2 * Win[y] + (Win[z] + Tie[z] + Los[z] - Los[y])
简化
Los[x] - Los[z] > 2 * (Win[x] - Win[z]) > 0  -- (3)
2 * (Win[z] - Win[y]) > Los[z] - Los[y] > 0  -- (4)

上两式隐含 Los[x] > Los[z] > Los[y] 以及 Win[x] > Win[z] > Win[y]

符合上面3, 4 条件及1式的就是丙的解, 令

Win[x] - Win[z] = a
Los[x] - Los[z] = b
Los[z] - Los[y] = c
Win[z] - Win[y] = d

b > 2 * a
2 * d > c

Win[x] = a + Win[z]
Win[y] = Win[z] - d
Win[z]

Los[x] = Los[z] + b
Los[y] = Los[z] - c
Los[z]

把上面六式加起来,再利用1式

Win[z] - Los[z] = (d - a + b - c) / 3


b = 2 * a + b'
c = 2 * d - c'

Win[z] - Los[z] = (a + b' + c' - d) / 3
这样我们可以直接选取大于零的 a b' c' d
同时保证 2 * d > c',以及 a + b' + c' - d可以被3整除就可以了

比方取
a = 1, b' = 2, c' = 1, d = 1,c = 2 * d - c' = 1,b = 2 * a + b' = 4

有 Win[z] - Los[z] = 1
取 Win[z] = 2 Los[z] = 1 (Win[z] > d, Los[z] > c)

Win[x] = 3,Los[x] = 5
Win[y] = 1,Los[y] = 0
Win[z] = 2,Los[z] = 1


最后选择Tie的值(Win + Los的最大值减去各队的Win + Los),可以有一个自由变量T
Tie[x] = 0 + T
Tie[y] = 7 + T
Tie[z] = 5 + T

Score[z] = 11 + T 分获胜

其实就算丙胜的场数比败的场数还少都可能是第一名

比方取
a = 1 b' = 1 c' = 1 d = 6
c = 2 * d - c' = 11
b = 2 * a + b' = 3

Win[z] - Los[z] = -1 (Win[z] > 6, Los[z] > 11)

取 Win[z] = 11 Los[z] = 12

Win[x] = 12,Los[x] = 15,Tie[x] = 0 + T
Win[y] = 5 ,Los[y] = 1 ,Tie[y] = 21+ T
Win[z] = 11,Los[z] = 12,Tie[z] = 4 + T

Score[z] = 37 + T 分获胜

这么多的可能都可以获胜为什么中国队就胜不了呢!
0 请登录后投票
   发表时间:2009-09-06  
更正上面

(Win[z] > d, Los[z] > c)
(Win[z] > 6, Los[z] > 11)

应为

(Win[z] >= d, Los[z] >= c)
(Win[z] >= 6, Los[z] >= 11)

应为胜负场数可以为0
0 请登录后投票
   发表时间:2009-09-06  
用数学列方程,解方程
这样有了方程写程序就容易多了
0 请登录后投票
   发表时间:2009-09-06  
感谢 lugionline 的回答。总算找到解法了。
您分解问题的方法值得学习。
再次感谢。
0 请登录后投票
   发表时间:2009-09-06  
ftj20003 写道
   假设双循环赛,则每队4场比赛,乙输的最少(假设不输),那么甲和丙至少输一场,甲输一场则另外两队有一队赢一场,甲赢的最多,那么至少赢两场。也就是说甲至少6分。丙输了一场了要想第一只有大于6分,意味着至少和甲赢的一样多,这就与甲赢的最多矛盾了,所以不可能第一。其实只要甲赢的超过一场,丙就不可能第一。在这个双循环的规则下:甲2胜1平1负,乙1胜3平,丙2负2平。
   不是这种赛制的没多想,因为我喜欢踢实况,嘿嘿。


这个才合理!

一般三个队的循环赛都是4场!
0 请登录后投票
   发表时间:2009-09-07  
jwinder 写道
ftj20003 写道
   假设双循环赛,则每队4场比赛,乙输的最少(假设不输),那么甲和丙至少输一场,甲输一场则另外两队有一队赢一场,甲赢的最多,那么至少赢两场。也就是说甲至少6分。丙输了一场了要想第一只有大于6分,意味着至少和甲赢的一样多,这就与甲赢的最多矛盾了,所以不可能第一。其实只要甲赢的超过一场,丙就不可能第一。在这个双循环的规则下:甲2胜1平1负,乙1胜3平,丙2负2平。
   不是这种赛制的没多想,因为我喜欢踢实况,嘿嘿。


这个才合理!

一般三个队的循环赛都是4场!


麻烦告诉一下,题目里哪个地方说到是“双循环”赛了?
我只看到这一句:
引用
每两队之间都比赛了同样多的场数
,这是双循环么?
构建在错误的前提上,你的逻辑再好,得出的结论也是不可靠的。
0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics