[算法讨论]百度之星复赛第一题：杀人游戏

wqx1

这个．．．．．．．！

不是约瑟夫吗！？

期待啊．．．

代码

Eastsun

汗，怎么是约瑟夫呢，虽然可以用同一种方法解决。

但这个题用我那第二种算法是得不到象解约瑟夫问题一样简洁的代码的。

用模拟算法的话应该是太慢了。

wqx1

如果第m个人恰好是Austin自己，他就杀掉他顺时针方向的下一个人。
还是有点区别啊

lufeng369

def mypos(n,m,t):
      kill_lists=[]
      list=range(n)
      m,t,d=m-1,t-1,m-1
      while len(list)>1:
           if d==t:d+=1
           kill_lists.append(list.pop(d)+1)
           d=(d+m)%len(list)
      return kill_lists[-1]

print mypos(7,4,1)

lufeng369

2. #或者这样。。其实差不多。。
4. def mypos(n,m,t):
5.   
6.       list=range(n)
7.       m,t,d=m-1,t-1,m-1
8.       while len(list)>2:
9.            if d==t:d+=1
10.            del list[d]
11.            d=(d+m)%len(list)
12.       list.remove(t);
13.       return list[0]+1
14. print mypos(7,4,1)

复制代码

Eastsun

呵呵，那楼上测试一下，比如数据都为1000,1000,99,测试10000组数据，能够在5秒之内搞定么？

如果能用这么简单的算法作出来就没必要比赛了。

lufeng369

恳求楼主解释一下约瑟夫环的算法！

Eastsun

其实想法很简单...讲出来就不名一文了，呵呵：

简单讲，就是递归算法：在n个人时，很容易知道第一个踢出人的序号，这样剩下的n－1个人就组成一个新的约瑟夫环。。。对n进行递归就OK 了。

注意的是，从n－1的约瑟夫环到n约瑟夫环，那些人的序号会发生改变，要进行变换。
ps:一般我给出算法就不会给出代码，反之亦然，因为这样可以给大家一个思考的余地，否则就没什么意思了。

Eastsun

没有啊，惭愧～

lufeng369

约瑟夫环游戏的递归定义：
   n个人围成环（编号0~n-1）
传统定义：从0号数起。
            步骤1。
            踢掉数到的第m个人。
            步骤2。
            后形成一个新环，重复步骤一。直到只剩下一个人。
            得最后胜者的序号。

新递归定义：n==1:第一届（一个人参加）冠军为0号;

              n>1  :第n届（n个人参加的n>1）的冠军为
              从上届的冠军号码后面的那个人数起..数到第m个人,那个人就是这届冠军

              总结一下就是下面这段代码..

2. game (n,m) | n==1 =0;
3.             | n>1   =(game(n-1,m)+m)%n;

复制代码

lufeng369

占个位。。

loglave

Eastsun进了决赛没有?

Eastsun

1.另类杀人游戏

周末的晚上，百度的员工们总喜欢聚集在公司的会议室玩杀人游戏。从1警1匪到n警n匪，他们尝试了几乎所有流行的杀人游戏规则。终于有一天，连最热衷杀人游戏的“杀人不眨眼”的Austin也开始对无休止的辩论感到厌烦。于是，他决定改变他的一贯作风，他开始变成了一个“杀人不睁眼”的杀手。

如何做到“杀人不睁眼”呢？Austin早已构思好他的杀人计划：

<OL>

N个人（包括Austin）坐成一圈玩杀人游戏，按顺时针编号 1 2 3 4 ... ...

Austin从1号开始顺时针开始数到第m号就杀掉第一个人，被杀掉的人要退出游戏。

如果第m个人恰好是Austin自己，他就杀掉他顺时针方向的下一个人。

Austin从被杀的人的下一个顺时针数m个人，把第m个杀掉。

重复2-4，直至杀掉所有人。

</OL>
Austin把这个杀人计谋告诉了法官小k，他便可以闭起眼睛杀人啦。作为一个正直善良的法官，小k当然不能让残忍的Austin得逞，于是，她偷偷把Austin的杀人计划告诉了作为警察的你，聪明的百度之星。现在，你的任务是活到最后，与“杀人不睁眼”的Austin对决。


输入要求：
第一个行包含一个整数K，表示有K组测试数据。 对于每组测试数据三个整数：
N，M，T，(3<=N<=10000,1<=M,T<=10000)
分别表示参与游戏的人数，Austin每隔M个人会杀掉一人，Austin初始位置的标号。


输入样例：
2
7 4 1
7 4 1

样例：in.txt

输出要求：
每个测试数据输出一个整数。
你需要选择的初始位置的序号，以确保最后剩下的两个人是你与Austin。


输出样例：
5
5
例子说明：杀人顺序为4 2 7 6 3 5 ， 所以5 是你要选择的位置。


附:解答程序的LAV版,算法的时间复杂度为O(N),在WQX NC3000上4s内可解答出n<=1000的情形。

1. /**
   
2. @ Content:杀人游戏之递归算法LAV版
   
3. @ Author :Eastsun
   
4. @ Version:1.0
   
5. */
   
6. #define MAX_N 1000
   
7. #define MAX_LEN 8
   
8. int solve(int n,int m,int k){
   
9.     int killer[MAX_N+1];
   
10.     int index,temp,result;
    
11.     m--; k--;
    
12.     killer[n] =k;
    
13.     for(index =n-1;index>=3;index--)
    
14.        if((temp=m%(index+1))==killer[index+1])killer[index] =index -1;
    
15.        else                                   killer[index] =(killer[index+1]+index-temp)%(index+1);
    
16.     if(killer[3]==m%3)    result =(killer[3]+2)%3;
    
17.     else                  result =3-killer[3]-m%3;
    
18.     for(index =4;index<=n;index++)
    
19.        if(killer[index]==m%index)     result =(result+m+2)%index;
    
20.        else                           result =(result+m+1)%index;
    
21.     return result+1;
    
22. }
    
23. long getNum(int x,int y,int max){//取得一个不大于max的正数
    
24.      char numKey[11];
    
25.      char buf[MAX_LEN+2],key;
    
26.      long num,n,k;
    
27.      strcpy(numKey,"0bnmghjtyu");
    
28.      buf[MAX_LEN+1] =0;
    
29.      n =num =0;
    
30.      while(1){
    
31.         memset(buf+n,' ',MAX_LEN+1-n);
    
32.         buf[n] ='_';
    
33.         TextOut(x,y,buf,0x41);
    
34.         key =getchar();
    
35.         if(key==0x0d){
    
36.           TextOut(x+n*6,y," ",0x41);
    
37.           return num;
    
38.         }
    
39.         if(key==0x1b){
    
40.             TextOut(x+n*6,y," ",0x41);
    
41.             return -1;
    
42.         }
    
43.         if(key==23&&n>0){
    
44.           n--;
    
45.           num =num/10;
    
46.         }
    
47.         else{
    
48.           for(k=0;k<10&&numKey[k]!=key;k++);
    
49.           if(k>=10||n>=MAX_LEN||num*10+k>max) continue;
    
50.           buf[n++]=k+'0';
    
51.           num =num*10+k;
    
52.         }
    
53.      }
    
54. }
    
55. void main(){
    
56.     int n,m,k;
    
57.     char text[20];
    
58.     while(1){
    
59.         ClearScreen();
    
60.         Refresh();
    
61.         TextOut(2,1,"Input N(2<N<1001):",0x41);
    
62.         if((n=getNum(110,1,1000))<3) break;
    
63.         TextOut(2,15,"Input M(0<M):",0x41);
    
64.         if((m=getNum(80,15,0x7fff))<=0) break;
    
65.         TextOut(2,29,"Input K(0<K<=N):",0x41);
    
66.         if((k=getNum(98,29,n))<=0) break;
    
67.         sprintf(text,"Position :%d",solve(n,m,k));
    
68.         TextOut(8,43,text,0x41);
    
69.         if(getchar()==0x1b) break;
    
70.     }
    
71. }         
    

复制代码

[此贴子已经被作者于2006-6-21 23:24:44编辑过]

dodolovely

上面的各位都是高手！支持一下！

leesoft

很令人头疼的问题