不看会后悔的Windows XP之经验谈	简单快捷DIY实用家庭影院

据说做对第二题拿薪水1W不成问题

楼主sunbird69（太阳鸟）2006-10-27 16:26:57 在 C/C++ / C语言提问

围棋考级的赛制是：
一共比赛5轮，和不同的对手比。
累计获胜2轮者通过，且不参加剩余的比赛。
连续4轮告负者不参加第5轮比赛。

在对手配对上，有个特别的规则：
就是每次都让胜率相同者配对比赛。
2个对手不能相遇2次或以上。

如：
第一轮，大家都是0胜0负
第二轮，就有1胜和1负2种胜率
第三轮，就有1胜1负和2负2种胜率
第四轮，就有1胜2负和3负2种胜率
第五轮，只有1胜3负1种胜率

第一题：请问这样的围棋考级的通过率是多少？

第二题：假设把所有选手根据原来的实力排个名次，假定名次高的必胜名次低的。
而比赛的配对是根据赛制再抽签，和原来的实力排名无关。
那么可能通不过的最高名次是第几名？
==============================================================================
分别用程序实现。
要求写出实现思路... 问题点数：80、回复次数：65Top

1 楼hziee_（）回复于 2006-10-27 17:01:10 得分 1

没有和其的啊Top

2 楼sunbird69（太阳鸟）回复于 2006-10-27 17:11:51 得分 0

没有就是这么定制的
第一题比较简单重点是第二题
===============================
是1W/M 哦如果综合能力好的话，会更多Top

3 楼lilachue（静水思雅）回复于 2006-10-27 17:20:24 得分 1

你给钱所？Top

4 楼laiwusheng（风清扬）回复于 2006-10-27 17:21:32 得分 1

markTop

5 楼ugvihc（maybe good good study, hope day day up!）回复于 2006-10-27 17:23:03 得分 1

markTop

6 楼morphymorphy（叔，人家还小啦~~ =_=）回复于 2006-10-27 17:41:28 得分 1

Mark;;

第一题: 13/16
第一题: 那么可能通不过的最高名次是第8名Top

7 楼danjiewu（阿丹）回复于 2006-10-27 17:52:11 得分 1

2个对手不能相遇2次或以上这个条件在人数足够多的情况下可以忽略吧？
实际上选手可以分为3类：赢过2盘的，赢过1盘的，没赢过的。
相当于每次比赛胜者组有一半人通过，败者组分出一半到胜者组。
所以5轮后的通过率很容易计算，应该是7/8。
Top

8 楼danjiewu（阿丹）回复于 2006-10-27 17:54:53 得分 5

计算有误，应该是13/16Top

9 楼danjiewu（阿丹）回复于 2006-10-27 17:59:21 得分 1

第2题是第8名？
1w/m的题啊，不会这么简单的吧？再想想Top

10 楼left_zxp（专逃课的左手）回复于 2006-10-27 18:02:23 得分 1

mark
Top

11 楼zhenhaojia（真好记）回复于 2006-10-27 18:23:11 得分 4

定义一个数据结构，
typedef struct person{
int no; // 编号
int win; // 赢的盘数
int loss ; // 输的盘数
int selected; // 本轮该选手是否以参加过比赛。
int quit; // 是否已经退出比赛。0，未退出；1；成功退出；2，失败退出
｝person_t;

有多少个人参加比赛，就申请多大的person_t数组。其实no完全可以不需要，下标与之相同。

然后就按照比赛规则迭代数组，停止条件为所有人都已经退出比赛。关于迭代的细节就不在赘述。

只要人数取的足够多。通过率就可以得出。第二个问题遍历数组就可以迎刃而解。
Top

12 楼sunbird69（太阳鸟）回复于 2006-10-27 23:14:04 得分 0

to morphymorphy(Morphy):

答案和我的一样，说说思路如何
不敢保证就一定正确Top

13 楼iclife（孔子）回复于 2006-10-28 01:11:06 得分 1

markTop

14 楼djj0628（没有多少分了：（）回复于 2006-10-28 03:24:12 得分 1

mark
Top

15 楼y71355480（JAVA初学者）回复于 2006-10-28 09:15:12 得分 5

第二题答案第五名？
不会程序语言Top

16 楼sunbird69（太阳鸟）回复于 2006-10-28 09:30:49 得分 0

楼上
怎么得出的第五名，能否把对阵情况简单列举一下？Top

17 楼wang430903（味觉全无）回复于 2006-10-28 10:23:34 得分 1

最大第6名?Top

18 楼y71355480（JAVA初学者）回复于 2006-10-28 10:46:19 得分 5

纯数学解题
通过第一题得到
1/4，1/4，3/16，1/8通过
1/8，1/16 不过
通过的第一个1/4两两对阵，余一对和后面的对阵，怎么着都赢
得出我的第五名~
感觉还是有点问题？Top

19 楼lyy1089（月落无痕）回复于 2006-10-28 11:09:53 得分 1

mark
Top

20 楼lyy1089（月落无痕）回复于 2006-10-28 11:19:05 得分 1

第一题我用数学得出13/16，第2题完全没有思路Top

21 楼yanidealsay521（大牛）回复于 2006-10-28 11:40:10 得分 1

我的第一题答案1/4,1/8,1/16,1/8,1/16,1/16,总计11/16通过
1/16,1/16,1/8,1/16,总计5/16不通过

第二题答案第５名
Top

22 楼yanidealsay521（大牛）回复于 2006-10-28 12:02:37 得分 1

第二题简单思路：总共比赛实际是４轮，max_min最少输３轮，那至少是前面有３名排名高于他（这个其实可以不考虑，只是３名后是注定的）．如果连输４轮，max_min更小，不考虑．第一次输的时候是排名比他高的，第二次输也是排名高于他的，考虑胜率配对，max_min输给的第二个对手也输过一次，又考虑只能和一个对手交锋一次，max_min第二次输后有３名高于他，思维层层推段，max_min第三次输给的对手可以在前一轮输给max_min第一次输给的对手．所以可以断定max_min前面至少有４名选手大于他的排名，因此是第五名．

写的思维稍微不好理解，不知道有没有其他的理解思路．Top

23 楼yanidealsay521（大牛）回复于 2006-10-28 12:22:28 得分 5

2轮　1－－∞(1胜)　5－－∞（5胜） 2--∞(2胜) 3--∞(3胜) 4--∞(4胜)

3轮　１－－5(5负)　2－－4(4负) 3－－∞(3胜)

4轮 5－－4(5负)　２－－3(3负)
　
5轮　5－－3(5负)

Top

24 楼skyairmj（方外）回复于 2006-10-28 14:03:27 得分 2

第一题 11/16,只要算通不过的机率就可以了:前四轮皆负和只胜一轮
(1/2)^4+4*(1/2)^4 = 5/16
所以通过的概率是1-5/16 = 11/16

第二题不计算也能知道是第五名啊
能输掉4场的说明肯定有至少4个人比他级别高
那不就是第五名么?

Top

25 楼yanidealsay521（大牛）回复于 2006-10-28 14:24:39 得分 2

前面思维乱了，错了！！！max_min是第5名．
1轮　null

2轮　1--5(1胜)　 2--∞(2胜) 3--∞(3胜) 4--∞(4胜)

3轮　5--∞(5胜)　3--4(4负)　1--2(2负)

4轮　2--5(5负) 2－－4(4负)

4轮　4--5(5负)

补充：max_min第二次输的对手，前面输过１次，可以是max_min第一次输给的对手;max_min第三次输的对手，也输过２次，其中一次输给前一次max_min已经输过的对手,另外一次输给比自己高的对手（比赛规则要求下，只能是这样）．
Top

26 楼sunbird69（太阳鸟）回复于 2006-10-28 16:11:37 得分 0

to yanidealsay521(大牛)
前面思维乱了，错了！！！max_min是第5名．
1轮　null

2轮　1--5(1胜)　 2--∞(2胜) 3--∞(3胜) 4--∞(4胜)

3轮　5--∞(5胜)　3--4(4负)　1--2(2负)

4轮　2--5(5负) 2－－4(4负) ====>>这也有问题，2在一轮中不会和两名选手比赛

4轮　4--5(5负) ====>>这5好象只有3负吧，下一轮比赛5一定会出线

===========================================================================

贴一下我的思路
====================================================================
第一题：
设有n名选手

第一轮后:
1胜 1负
n/2 n/2
第二轮后：
1胜1负 2负通过
n/4+n/4 n/4 n/4
第三轮后：
1胜2负 3负通过
n/4+n/8 n/8 n/4+n/4
第四轮后：
1胜3负通过淘汰
n/8+n/16+n/16 n/2+n/8+n/16 n/16
第五轮后：
通过淘汰
n/2+n/8+n/16+n/16+n/16 n/16+n/16+n/16
13n/16 3n/16
--------------------------------------------------------------------
从以上分析得出，通过率为13/16=81.25%
====================================================================
第二题：
下面分析根据以上情况：

<<1,2,3,4,5,6,7,8,...>>
1v5,2v6,3v7,4v8,...
第一轮后：
1胜 1负
<<1,2,3,4,...>> <<5,6,7,8,...>>
1v3,2v4,... 5v8,6v7,...
第二轮后：
1胜1负 2负通过
<<3,4,5,6,...>> <<7,8,...>> <<1,2>>
3v5,4v6,... 7v8,...
第三轮后：
1胜2负 3负通过
<<5,6,7,...>> <<8,...>> <<1,2,3,4>>
5v6,7vX,... 8vY,...
第四轮后：
1胜3负通过
<<6,8,...>> <<1,2,3,4,5,7,...>>
6v8,...
第五轮后：
可以看出8是出局的最高名次。
==================================================================

大家一定要注意题中说的两胜就不用参加以后的比赛，还个更重要的条件是2个对手不能相遇2次或以上这两个条件。

试了很多排列的可能，没试出比8更高的名次。大家看看有没有更好的名次能出来...Top

27 楼xiaohulaoshi（）回复于 2006-10-28 16:12:11 得分 1

出这样的问题傻呀?Top

28 楼sunbird69（太阳鸟）回复于 2006-10-28 16:40:32 得分 0

现在关键的问题是想用程序的检验一下
但程序的实现还同有好的解决办法Top

29 楼morphymorphy（叔，人家还小啦~~ =_=）回复于 2006-10-28 16:45:18 得分 1

写了个小程序。。大家给看看怎么样。。忙啊。。
:)

typedef struct{
int ID; /* 棋手编号 */
int power; /* 棋力(在比赛时，棋力大者胜) */
int win; /* 赢的轮数 */
int lose; /* 输的轮数 */
int rival[5]; /* 对弈过的对手ID编号 */
int state; /* 是否已经退出比赛(0,未退出；1,考级成功；2,失败退出) */
}PLAYER;

#define MAX 16
#define EXCITED 0
#define PASS 1
#define FAIL 2
#define BOOL unsigned char
#define TRUE 1
#define FALSE 0

#include "stdio.h"
main()
{
int i,j,k,m;
int sum=0; /* 通过的棋手总和 */
BOOL jump=TRUE; /* 指示指针是否跳跃 */
BOOL isFirstMeet=TRUE; /* 指示是否是第一次对弈 */
PLAYER player[MAX];
for(i=0; i<MAX; i++) /* 初始化各棋手状态 */
{
player[i].ID=i+1;
printf("Please input the power of player%2d: ",player[i].ID);
scanf("%d", &player[i].power);
player[i].win=0;
player[i].lose=0;
player[i].state=EXCITED;
for(j=0; j<5; j++)
player[i].rival[j]=-1;
}
/* 开始比赛 */
for(k=0; k<5; k++) /* 轮数 */
for(i=0; i<MAX; i++)
{
if(player[i].win+player[i].lose > k)
continue;
if(player[i].state == EXCITED) /* 就近配对比赛 */
{
for(j=i+1; j<MAX; j++)
{
if(player[i].win+player[i].lose > k )
continue;
if(player[j].state == EXCITED && player[i].win != player[j].win)
jump=FALSE; /* 前面有赢的轮数不同的棋手, 指针不跳跃 */
for(m=0; m<5; m++)
{
if(player[i].rival[m]==player[j].ID)
isFirstMeet = FALSE;
}
if(isFirstMeet == FALSE)
{
isFirstMeet = TRUE;
}
if(player[j].state == EXCITED && player[i].win == player[j].win)
{
if(player[i].power >= player[j].power) /* 比赛 */
{
player[i].win++;
if(player[i].win == 2)
player[i].state = PASS;
m=0;
while(player[i].rival[m] !=-1 && m<5){m++;}
if(m<5)
player[i].rival[m]=player[j].ID;

player[j].lose++;
if(player[j].lose == 4)
player[j].state = FAIL;
m=0;
while(player[j].rival[m] !=-1 && m<5){m++;}
if(m<5)
player[j].rival[m]=player[i].ID;
}
else
{
player[j].win++;
if(player[j].win == 2)
player[j].state = PASS;
m=0;
while(player[j].rival[m] !=-1 && m<5) {m++;}
if(m<5)
player[j].rival[m]=player[i].ID;

player[i].lose++;
if(player[i].lose == 4)
player[i].state = FAIL;
m=0;
while(player[i].rival[m] !=-1 && m<5) {m++;}
if(m<5)
player[i].rival[m]=player[j].ID;
}
if(jump==FALSE)
{
jump=TRUE;
printf(" =%d= ",i);
break;
}
else
{
i=j;
printf("%d ",i);
break;
}
}
}
}
}
/* 计算围棋考级的通过人数 */
for(i=0; i<MAX; i++)
if(player[i].state == 1)
sum++;
printf("\n===The number of players passed the match is %d(total %d)===\n\n",sum,MAX);
}Top

30 楼morphymorphy（叔，人家还小啦~~ =_=）回复于 2006-10-28 16:47:44 得分 1

上面程序大致算法
1 定义棋手起数组并初始化状态；
2 进入比赛循环体；
2.1 轮数循环
2.2 然后进入二重循环体（指示2个数组下标，一个指向棋手甲，一个指向棋手乙），根据条件判断，不满条件就增

加相应的数组下标值，使其指向下一个棋手，如果满足条件，两人就开始比赛；
2.3 根据比赛结果（比较棋力大小）设定结构体数组变量值（赢的轮数，输的轮数，对弈过的对手ID编号，是否已

经退出比赛等）；
3 根据比赛结果可以计算出问题1的答案。(以16的倍数算了几次，结果等与13/16)

至于问题2，可采用穷举法实现（穷举棋手的棋力序列，呵呵傻了点，当然，采用数学方式解决更好）

===
个人觉得，16人参赛是大规模人员参赛的一个模型（16n+）, 二叉树的特性。。(证明不会 ^0^)Top

31 楼yanidealsay521（大牛）回复于 2006-10-28 17:36:43 得分 1

32 楼yanidealsay521（大牛）回复于 2006-10-28 17:41:33 得分 1

第一题：
设有n名选手

第一轮后:
1胜 1负
n/2 n/2
第二轮后：
1胜1负 2负通过
n/4+n/4 n/4 n/4

第三轮后：
1胜2负 3负通过
n/4+n/8 n/8 n/4+n/4
第四轮后：
1胜3负通过淘汰
n/8+n/16+n/16 n/2+n/8+n/16 n/16
第五轮后：
通过淘汰
n/2+n/8+n/16+n/16+n/16 n/16+n/16+n/16
13n/16 3n/16
--------------------------------------------------------------------
从以上分析得出，通过率为13/16=81.25%

//你犯了我说的上面的误解，有六轮了，第一轮是null
Top

33 楼yanidealsay521（大牛）回复于 2006-10-28 18:15:18 得分 1

我理解错了，不说了，搬个凳子看大人见解．．．Top

34 楼bilei_yzu（咖啡里的奶油）回复于 2006-10-28 19:28:17 得分 1

首先有一点歧异，“第一轮，大家都是0胜0负”

是比赛前的情况还是比赛后的？？

如果是比赛后的就说明全是和棋，如果这样的话第一问应该11/16；我想应该不是这样，若是后者则是13/16，大概是有这两种答案的原因。

至于第二问如果是前种情况就是第8名，若是后者则是第16名。
理由（只说明后种的）：

用归纳推理，由于必须是相同胜率的才可以比，可以认为是输的次数相同的才能比。
我们设是第x号，那么，
第x号在第四轮肯定是和它一样输过三次而且在它之前唯一的一个输过三次的人比赛。

每次都输就说明每次都和在自己相对位置之前的人比，导致一个选手输三次直接人数是3，实际需要的人数大于3，我们先求连续输三次的最靠前的人设为y，要记得y选手是在第X我们所求的人的相对的前面，因此他前面的人自然是第x选手前面的人，x选手前面的人数是y的两倍拉，这样就有眉目了吧。

用这个循环则推到输一次是2号，两次是4号，三次是8号，四次则是16号。

不是说第16号最后一定是和第8号比的，而是和第8~15的随便什么人比都有可能的.

如果有异议,可以先试试输三次的情况,这样推翻我的推理比较容易些,呵呵!希望大家努力帮我找反例,加油.
例如输两次时
不要告诉我3号可以，因为那需要胜率不同的人比赛了！！Top

35 楼bilei_yzu（咖啡里的奶油）回复于 2006-10-28 19:36:16 得分 1

补充一点，输的情况分类时一定要对称的，否则就会不平衡，类似于平衡二叉树，就算有决定情况交叉的情况，也是要对称的因此可以等价于无交叉情况，呵呵。Top

36 楼bilei_yzu（咖啡里的奶油）回复于 2006-10-28 19:50:02 得分 1

其中太阳鸟的第三轮的 “8vy”，8 一定是胜出的，因为8前面的已经符合条件全排列了，8和后面的一定会胜，所以推理8是合理的！：-）Top

37 楼gjb999（老鼠老鼠还是一只老鼠！）回复于 2006-10-28 20:14:41 得分 1

markTop

38 楼SK_HeatoN（）回复于 2006-10-28 20:46:23 得分 1

hui qu zuo zuo
Top

39 楼bilei_yzu（咖啡里的奶油）回复于 2006-10-28 20:57:42 得分 1

我刚才是说8不合理，打错了，呵呵。Top

40 楼sorex（）回复于 2006-10-29 11:17:42 得分 1

只有相同胜率的人才能对弈的
最少12人就可以打到第5轮比赛了
比赛结果如下：
---------------第1轮比赛开始--------------
12 负 11 到目前共败 1 连败 1
11 胜 12 到目前共胜 1
10 负 9 到目前共败 1 连败 1
9 胜 10 到目前共胜 1
8 负 7 到目前共败 1 连败 1
7 胜 8 到目前共胜 1
6 负 5 到目前共败 1 连败 1
5 胜 6 到目前共胜 1
4 负 3 到目前共败 1 连败 1
3 胜 4 到目前共胜 1
2 负 1 到目前共败 1 连败 1
1 胜 2 到目前共胜 1

---------------第1轮比赛结果--------------
***********该轮比赛统计到此结束***********

---------------第2轮比赛开始--------------
12 负 10 到目前共败 2 连败 2
10 胜 12 到目前共胜 1
11 负 9 到目前共败 1 连败 1
9 胜 11 到目前共胜 2
8 负 6 到目前共败 2 连败 2
6 胜 8 到目前共胜 1
7 负 5 到目前共败 1 连败 1
5 胜 7 到目前共胜 2
4 负 2 到目前共败 2 连败 2
2 胜 4 到目前共胜 1
3 负 1 到目前共败 1 连败 1
1 胜 3 到目前共胜 2

---------------第2轮比赛结果--------------
1 入选！
5 入选！
9 入选！
***********该轮比赛统计到此结束***********

---------------第3轮比赛开始--------------
12 负 8 到目前共败 3 连败 3
8 胜 12 到目前共胜 1
11 负 10 到目前共败 2 连败 2
10 胜 11 到目前共胜 2
7 负 6 到目前共败 2 连败 2
6 胜 7 到目前共胜 2
3 负 2 到目前共败 2 连败 2
2 胜 3 到目前共胜 2

---------------第3轮比赛结果--------------
2 入选！
6 入选！
10 入选！
***********该轮比赛统计到此结束***********

---------------第4轮比赛开始--------------
11 负 8 到目前共败 3 连败 3
8 胜 11 到目前共胜 2
7 负 3 到目前共败 3 连败 3
3 胜 7 到目前共胜 2

---------------第4轮比赛结果--------------
3 入选！
8 入选！
***********该轮比赛统计到此结束***********

---------------第5轮比赛开始--------------
11 负 7 到目前共败 4 连败 4
7 胜 11 到目前共胜 2

---------------第5轮比赛结果--------------
7 入选！
11 被淘汰！
***********该轮比赛统计到此结束***********

合格人数：9
淘汰人数：1
胜利未够：2
合格率为：75%
未合格最高名次：4Top

41 楼sorex（）回复于 2006-10-29 11:19:14 得分 1

大家都喜欢16那给个16人的比赛结果看看
---------------第1轮比赛开始--------------
16 负 15 到目前共败 1 连败 1
15 胜 16 到目前共胜 1
14 负 13 到目前共败 1 连败 1
13 胜 14 到目前共胜 1
12 负 11 到目前共败 1 连败 1
11 胜 12 到目前共胜 1
10 负 9 到目前共败 1 连败 1
9 胜 10 到目前共胜 1
8 负 7 到目前共败 1 连败 1
7 胜 8 到目前共胜 1
6 负 5 到目前共败 1 连败 1
5 胜 6 到目前共胜 1
4 负 3 到目前共败 1 连败 1
3 胜 4 到目前共胜 1
2 负 1 到目前共败 1 连败 1
1 胜 2 到目前共胜 1

---------------第1轮比赛结果--------------
***********该轮比赛统计到此结束***********

---------------第2轮比赛开始--------------
16 负 14 到目前共败 2 连败 2
14 胜 16 到目前共胜 1
15 负 13 到目前共败 1 连败 1
13 胜 15 到目前共胜 2
12 负 10 到目前共败 2 连败 2
10 胜 12 到目前共胜 1
11 负 9 到目前共败 1 连败 1
9 胜 11 到目前共胜 2
8 负 6 到目前共败 2 连败 2
6 胜 8 到目前共胜 1
7 负 5 到目前共败 1 连败 1
5 胜 7 到目前共胜 2
4 负 2 到目前共败 2 连败 2
2 胜 4 到目前共胜 1
3 负 1 到目前共败 1 连败 1
1 胜 3 到目前共胜 2

---------------第2轮比赛结果--------------
1 入选！
5 入选！
9 入选！
13 入选！
***********该轮比赛统计到此结束***********

---------------第3轮比赛开始--------------
16 负 12 到目前共败 3 连败 3
12 胜 16 到目前共胜 1
15 负 14 到目前共败 2 连败 2
14 胜 15 到目前共胜 2
11 负 10 到目前共败 2 连败 2
10 胜 11 到目前共胜 2
8 负 4 到目前共败 3 连败 3
4 胜 8 到目前共胜 1
7 负 6 到目前共败 2 连败 2
6 胜 7 到目前共胜 2
3 负 2 到目前共败 2 连败 2
2 胜 3 到目前共胜 2

---------------第3轮比赛结果--------------
2 入选！
6 入选！
10 入选！
14 入选！
***********该轮比赛统计到此结束***********

---------------第4轮比赛开始--------------
16 负 8 到目前共败 4 连败 4
8 胜 16 到目前共胜 1
15 负 12 到目前共败 3 连败 3
12 胜 15 到目前共胜 2
11 负 7 到目前共败 3 连败 3
7 胜 11 到目前共胜 2

---------------第4轮比赛结果--------------
7 入选！
12 入选！
16 被淘汰！
***********该轮比赛统计到此结束***********

---------------第5轮比赛开始--------------
15 负 11 到目前共败 4 连败 4
11 胜 15 到目前共胜 2

---------------第5轮比赛结果--------------
11 入选！
15 被淘汰！
***********该轮比赛统计到此结束***********

合格人数：11
淘汰人数：2
胜利未够：3
合格率为：68.75%
未合格最高名次：3
Top

42 楼ylhyh（----------> www.cnpp.info <----------）回复于 2006-10-29 11:54:35 得分 1

markTop

43 楼zhihualee（卡＠罗）回复于 2006-10-29 12:40:35 得分 1

如果有和棋就不用做了
你做的出来啊
Top

44 楼bilei_yzu（咖啡里的奶油）回复于 2006-10-29 13:06:06 得分 1

呵呵，之前只考虑最先输四次了，没有考虑五伦结束的确是不全面，首先肯定“sorex”思路真的很有道理，支持你，我的大答案估计的确可能存在问题的。
但是“sorex”的比赛中有些选手在某些轮中不能参加比赛，这样似乎也不公平，这样是否就符合要求呢，在他模拟的16人比赛中，3号从第四轮开始就没有参加比赛，3号是算胜出还是淘汰呢，不知“sorex”，做何解释，而且在第四轮有和自己胜率相同的选手啊，而且3号只要比赛就肯定能出现，但是没机会啊，难道就因为sorex想要造就15号的失利就委屈而被淘汰了呢。那么淘汰最前的不会就是3号了吧，如果这种方法说得过的可以想办法让2号成为最倒霉的！所以sorex的人数本身不合理，至少和比赛说明是存在矛盾的！同样的道理，12个人也不见得合理。
不过我觉得15号最早被淘汰有道理，再想办法证明一下看看。：-）
Top

45 楼sorex（）回复于 2006-10-29 13:19:42 得分 1

我的算法是倒序的优先考虑低名次者出线，所以在第四轮的时候3号就没有匹配的对手了（胜率相同且未对弈过）。题目要求也是计算最高的名次不合格。
算法中间没有实现完全配对，那样做的计算效率太低了，所以没有加入到程序中。Top

46 楼sorex（）回复于 2006-10-29 13:34:42 得分 1

相反算法中实现的是排名越靠前者给与的难度也越大，当30人比赛的时候第一名都会被淘汰，同样是没有匹配对手。Top

47 楼yudingding6197（）回复于 2006-10-29 14:21:25 得分 1

0
/ \
1 1a
\ / \
2 2a
\ / \
3 3a
\ / \
4 4a
\ / \
5 淘汰a
\
淘汰
大家可以看看这个比赛抽象图，这是被淘汰选手可能经历的比赛情况，
向左分开表示赢一局棋，向右表示输一局棋。
被淘汰最终情况分为0胜4负和 1胜4负，可以看作选手从0走到淘汰的过程，
如果是0胜4负这种情况，可以推测被淘汰的选手最高名次远远低于1胜4负这种情况。
就是说：如果第九名被淘汰，
在4a轮最少有一个比第九名强的选手（假设第8名）
在3a轮最少有两个比第8，九名强的选手（假设第6，7名）
在2a轮最少有4个比第6，7，8，9名强的选手（假设第2，3，4，5名）

根据题目规则，这是不可能的（第2名最多输一局，因为只有第1名比他强，第2名最多
走到1a位置后，下一局肯定赢，不可能走到2a的位置）。
但是如果是1胜4负这种情况，第9名可能不幸输掉。
所以我们应该考虑1胜4负这种走法。

这相当于是一个图，从0到达淘汰的位置，仅供大家参考，我还需要再考虑一下算法。

Top

48 楼xylophone21（天堂的隔壁）回复于 2006-10-29 17:16:20 得分 0

如果人数不合适有人找不到对手了怎么处理？Top

49 楼superxiaomm（小美）回复于 2006-10-29 19:06:26 得分 1

强算法的问题，不过出这种题目的公司，基本都是世界500强。1w太少了Top

50 楼linzhongren（）回复于 2006-10-29 20:19:48 得分 1

8
/ \
4 5
\ / \
9 8
\ / \

Top

51 楼sally165165_（）回复于 2006-10-29 21:25:23 得分 1

哇！都是高人！搬来板凳看！Top

52 楼eroscheng（成功）回复于 2006-10-29 22:01:14 得分 1

mark
Top

53 楼johndiyang（木木）回复于 2006-10-30 00:58:20 得分 1

markTop

54 楼zhenhaojia（真好记）回复于 2006-10-30 12:05:30 得分 1

这种题目很一般，google, ms, yahoo, 甚至国内的baidu, qq, 网易，搜狐，都会出这样的问题。
我说的还只是互联网公司。Top

55 楼y71355480（JAVA初学者）回复于 2006-10-30 14:16:29 得分 1

第二题答案：第二名.
我侄女（6岁）说的：）
不说数学，不谈程序，想想也是拉
可以参考下~Top

56 楼lsd1025（）回复于 2006-10-30 15:56:13 得分 1

有难度呀，Top

57 楼hehaorome（石沉大海）回复于 2006-10-31 14:43:28 得分 1

第二题答案是第16名
首先规则说“每次都让胜率相同者配对比赛。”这个是解题的关键。
出局最快的方式是连负四场。
结合上面两条：就是说一旦你设计的对手赢了比赛，你就别想跟人家玩了。

可以用逆推法：

第四轮：必须是两个三负的人比赛
3负（胜）----3负（负）

第三轮：想要有第四轮的结果必须有两场这样的比赛
2负（胜）----2负（负） 2负（胜）----2负（负）

第二轮：同理
1负----1负 1负----1负 1负----1负 1负----1负

第一轮：同理
需要8场“0负----0负”的比赛。
就是需要16个人，这是个二叉树，每通过的那个人是这棵树中最小的叶子，也就是第16

不知道对不对，楼主给答案看看吧：）Top

58 楼li01bin（啊！斌）回复于 2006-10-31 15:17:50 得分 1

一看就头疼，给100w，也懒得象Top

59 楼hehaorome（石沉大海）回复于 2006-11-01 11:26:02 得分 1

不好意思，上边想错了。赛程图应该是这样的：

16
/ \
8 8
/ \ / \
4 8 4
/ \ / \
4 6 2
/ \ / \
3 4 1
/ \
2 2
左边的4、4、3、2晋级，右边的1和2淘汰。第一题的通过率应该是13/16，和楼上的诸位一致。

第二题不会，等答案。Top

60 楼danjiewu（阿丹）回复于 2006-11-02 16:32:13 得分 1

前面没考虑好，不过答案是对的，最高为第8名。

其实证明也简单，每次比赛胜者组有一半人通过，败者组分出一半到胜者组。计算一下就知道5轮之后前8名至少出线了7个，因此未出线的最高只可能是第8名。Top

61 楼danjiewu（阿丹）回复于 2006-11-02 16:39:14 得分 1

有遗漏了，先要证明5轮之后前7名至少出线了7个，然后再证明前8名也至少出线了7个，就可以说明最高只可能是第8名。Top

62 楼wenstory（）回复于 2006-11-02 17:18:21 得分 1

正确的答案是第8个吗?
小弟用程序得到的是第8个

本人认为
要得到未出线的最大号,一定要让强强对碰,这样才够残忍

以下是程序,望大家指点

#include <iostream.h>

int opposer[20][4];//用于保存对手编号,为了2个对手不能相遇2次或以上

bool HaveMeet(int i,int j)
{
for(int a=0;a<4;a++)
{
if(opposer[i][a]==j)
return true;
}
return false;
}

void main()
{
int wins[20]; //保存选手的胜率
int matched[20]; //保存每轮是否已经参加比赛

int i=0,j=0;
for(;i<20;i++)
{
for(;j<4;j++)
{opposer[i][j]=-1;}
}

for(i=0;i<20;i++)
{wins[i]=0;matched[i]=0;}

for(int k=0;k<4;k++)//4轮比赛
{
for(int m=0;m<20;m++)//每轮开始时将所有的选手设为未参加比赛
{matched[m]=0;}

for(i=0;i<20;i++)
{
if(wins[i]<2&&matched[i]==0)//如果这个选手需要参加且还没参加这轮比赛
{
for(j=i+1;j<20;j++)//循环查找它的对手
{
if((wins[i]==wins[j])&&(!HaveMeet(i,j))&&(matched[j]==0))//胜率相同且未对战过
{
//赢了
wins[i]+=1;

//保存对手状态
opposer[i][k]=j;
opposer[j][k]=i;

//这2个选手已经比赛了
matched[i]=1;
matched[j]=1;
break;
}
}
}
}
}

//上4轮结束后只要找到第二个只赢了一场的棋手就是最大号淘汰选手
i=0;
while(wins[i]!=1)i++;
i++;
while(wins[i]!=1)i++;

cout<<"可能通不过的最高名次是第"<<i+1<<"号"<<endl;

}Top

63 楼xdspower（杂食菜熊）回复于 2006-11-02 17:32:25 得分 1

第二题肯定答第5名的是错误的
其实这道题可以有很多答案（当然是极致条件），比如如果只有一名选手参数？如果只有两名选手参数等等情况。
如果要严谨一些，保证有足够多的选手参数，也就是大于32名选手参数则问题可以转换为可能连输4场的名称最高选手。

先标记在这里，以后接着想Top

64 楼silwol（知识分子会武术，流氓也挡不住。）回复于 2006-11-03 08:57:35 得分 1

大家的思维被限定了，这应该是算法题目。应该把图扩展完全。
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
我的算法是：
以上节点初始值为0，每次进行一个访问，起始点为1；
访问点a时，a.value++，若a.value为奇数则继续访问其左下方节点，否则访问其右下方节点，直到访问至最后一层时结束本次访问；
当20或15两节点中有一个的值不为0时即结束，否则继续从1节点开始下一次访问；
最终的结果即为访问的次数。
具体的证明我再想想。。。
这样的遍历应该使每个名次的选手最多药比赛多少场才可以胜出的情况，因此当第一个路过20或15的选手即为可能被淘汰的最高排名者。
用此算法得到的结果为8。
Top

65 楼DraculaW（成爲牛人，然後離開）回复于 2006-11-03 16:15:02 得分 1

基本上就是求图的生成树的哈。。。Top

据说做对第二题拿薪水1W不成问题

1 楼hziee_（）回复于 2006-10-27 17:01:10 得分 1

2 楼sunbird69（太阳鸟）回复于 2006-10-27 17:11:51 得分 0

3 楼lilachue（静水思雅）回复于 2006-10-27 17:20:24 得分 1

4 楼laiwusheng（风清扬）回复于 2006-10-27 17:21:32 得分 1

5 楼ugvihc（maybe good good study, hope day day up!）回复于 2006-10-27 17:23:03 得分 1

6 楼morphymorphy（叔，人家还小啦~~ =_=）回复于 2006-10-27 17:41:28 得分 1

7 楼danjiewu（阿丹）回复于 2006-10-27 17:52:11 得分 1

8 楼danjiewu（阿丹）回复于 2006-10-27 17:54:53 得分 5

9 楼danjiewu（阿丹）回复于 2006-10-27 17:59:21 得分 1

10 楼left_zxp（专逃课的左手）回复于 2006-10-27 18:02:23 得分 1

11 楼zhenhaojia（真好记）回复于 2006-10-27 18:23:11 得分 4

12 楼sunbird69（太阳鸟）回复于 2006-10-27 23:14:04 得分 0

13 楼iclife（孔子）回复于 2006-10-28 01:11:06 得分 1

14 楼djj0628（没有多少分了：（）回复于 2006-10-28 03:24:12 得分 1

15 楼y71355480（JAVA初学者）回复于 2006-10-28 09:15:12 得分 5

16 楼sunbird69（太阳鸟）回复于 2006-10-28 09:30:49 得分 0

17 楼wang430903（味觉全无）回复于 2006-10-28 10:23:34 得分 1

18 楼y71355480（JAVA初学者）回复于 2006-10-28 10:46:19 得分 5

19 楼lyy1089（月落无痕）回复于 2006-10-28 11:09:53 得分 1

20 楼lyy1089（月落无痕）回复于 2006-10-28 11:19:05 得分 1

21 楼yanidealsay521（大牛）回复于 2006-10-28 11:40:10 得分 1

22 楼yanidealsay521（大牛）回复于 2006-10-28 12:02:37 得分 1

23 楼yanidealsay521（大牛）回复于 2006-10-28 12:22:28 得分 5

24 楼skyairmj（方外）回复于 2006-10-28 14:03:27 得分 2

25 楼yanidealsay521（大牛）回复于 2006-10-28 14:24:39 得分 2

26 楼sunbird69（太阳鸟）回复于 2006-10-28 16:11:37 得分 0

27 楼xiaohulaoshi（）回复于 2006-10-28 16:12:11 得分 1

28 楼sunbird69（太阳鸟）回复于 2006-10-28 16:40:32 得分 0

29 楼morphymorphy（叔，人家还小啦~~ =_=）回复于 2006-10-28 16:45:18 得分 1

30 楼morphymorphy（叔，人家还小啦~~ =_=）回复于 2006-10-28 16:47:44 得分 1

31 楼yanidealsay521（大牛）回复于 2006-10-28 17:36:43 得分 1

32 楼yanidealsay521（大牛）回复于 2006-10-28 17:41:33 得分 1

33 楼yanidealsay521（大牛）回复于 2006-10-28 18:15:18 得分 1

34 楼bilei_yzu（咖啡里的奶油）回复于 2006-10-28 19:28:17 得分 1

35 楼bilei_yzu（咖啡里的奶油）回复于 2006-10-28 19:36:16 得分 1

36 楼bilei_yzu（咖啡里的奶油）回复于 2006-10-28 19:50:02 得分 1

37 楼gjb999（老鼠老鼠还是一只老鼠！）回复于 2006-10-28 20:14:41 得分 1

38 楼SK_HeatoN（）回复于 2006-10-28 20:46:23 得分 1

39 楼bilei_yzu（咖啡里的奶油）回复于 2006-10-28 20:57:42 得分 1

40 楼sorex（）回复于 2006-10-29 11:17:42 得分 1

41 楼sorex（）回复于 2006-10-29 11:19:14 得分 1

42 楼ylhyh（----------> www.cnpp.info <----------）回复于 2006-10-29 11:54:35 得分 1

43 楼zhihualee（卡＠罗）回复于 2006-10-29 12:40:35 得分 1

44 楼bilei_yzu（咖啡里的奶油）回复于 2006-10-29 13:06:06 得分 1

45 楼sorex（）回复于 2006-10-29 13:19:42 得分 1

46 楼sorex（）回复于 2006-10-29 13:34:42 得分 1

47 楼yudingding6197（）回复于 2006-10-29 14:21:25 得分 1

48 楼xylophone21（天堂的隔壁）回复于 2006-10-29 17:16:20 得分 0

49 楼superxiaomm（小美）回复于 2006-10-29 19:06:26 得分 1

50 楼linzhongren（）回复于 2006-10-29 20:19:48 得分 1

51 楼sally165165_（）回复于 2006-10-29 21:25:23 得分 1

52 楼eroscheng（成功）回复于 2006-10-29 22:01:14 得分 1

53 楼johndiyang（木木）回复于 2006-10-30 00:58:20 得分 1

54 楼zhenhaojia（真好记）回复于 2006-10-30 12:05:30 得分 1

55 楼y71355480（JAVA初学者）回复于 2006-10-30 14:16:29 得分 1

56 楼lsd1025（）回复于 2006-10-30 15:56:13 得分 1

57 楼hehaorome（石沉大海）回复于 2006-10-31 14:43:28 得分 1

58 楼li01bin（啊！斌）回复于 2006-10-31 15:17:50 得分 1

59 楼hehaorome（石沉大海）回复于 2006-11-01 11:26:02 得分 1

60 楼danjiewu（阿丹）回复于 2006-11-02 16:32:13 得分 1

61 楼danjiewu（阿丹）回复于 2006-11-02 16:39:14 得分 1

62 楼wenstory（）回复于 2006-11-02 17:18:21 得分 1

63 楼xdspower（杂食菜熊）回复于 2006-11-02 17:32:25 得分 1

64 楼silwol（知识分子会武术，流氓也挡不住。）回复于 2006-11-03 08:57:35 得分 1

65 楼DraculaW（成爲牛人，然後離開）回复于 2006-11-03 16:15:02 得分 1

相关问题

关键词

得分解答快速导航

相关链接

广告也精彩

反馈