在非洲草原里,生活着三类动物--大象、蛇、老鼠(每类动物的数量未知),以及一位妖精,他们各自具有非凡的本领:
象(踩)胜蛇;
蛇(噬)胜鼠;
鼠(钻鼻孔)胜象;
妖精可以变化,可以将自己变为大象、猫、老鼠3类动物中的某一种,从而具有所变动物的能力,但具体会变成哪类动物是随机的,在比赛之前妖精本人也不知道。
注:同类的动物之间则会战成平手。为了增进各类动物和妖精之间的交流,深林里举行了一界比武大会,比武大会的规则如下:
动物们自愿报名,妖精必须参赛。
赛前对每位参赛选手进行编号(编号为从1到n的整数,n为总选手个数)。
比赛会进行多场,每场比赛随机抽取两位选手到擂台上进行比武,上擂台之前两位选手都不知道对方的身份(动物的类型)。
每场比赛中,如果妖精被选中,他可以在上擂台前施展变化变为三类动物之一,但不允许在擂台上变化。
整个赛事会通过广播进行直播,而播音员为了省事,每场比赛结束的时候,他只会报导说:i号选手战胜(平)了j号选手(i,j<=n),但不会说出i号和j号选手的身份(动物的类型)。假如此时你坐在收音机旁收听比赛直播,你能否根据比赛结果判断出谁是魔法师?

解决方案 »

  1.   

    主要考虑:
    1、1胜2,1平(或者负)2——可以确定1、2种必有一个妖精;
    2、1胜2,2=4,4=7... n-1=n ...1负n——此中任意一个(个数不定)都可能是妖精;对于第二种方式出来的,该怎么获取并最终参与过滤
      

  2.   

    应该说,如果i和j比赛了2次,而这2次的结果不同,那么必然有一个是妖精
    再来一个,如果i和k比赛了2次,而这2次的结果也不同,那么可知i是妖精,
      

  3.   

    i VS j 两次结果不同
    i VS k 两次结果不同
      

  4.   

    如果比赛场数为1,则无法判断;
    如果场数为2,也无法判断;
    如果场数为3,也无法判断;
    如果场数为4,其中只有当比赛人数为3(i,j,k)并且ij比两场,结果不同;ik比两场,结果不同时才可以判断;
    如果比赛场数为n,则按以下方法思考:
    1,寻找i,当i跟其他任何两人或以上分别比赛2场或以上结果不同,则i为妖精;(找不到则转第二步)
    2,寻找四人ijpq,其中ij两次或以上比赛结果不同;则以下五组可判断i为妖精;(找不到则转第三步)
    (i赢p,i赢q),
    (i输p,i输q),
    (i平p,p平q,i不平q),
    (i平p,p输q,i不输q),
    (i平p,p赢q,i不赢q);
    3,无法判断,转第四步
    4,我刚才写了什么,头好晕啊。。好晕。。