首页 > 其他 > 详细

HDU-2516 取石子游戏

时间:2014-01-15 23:54:04      阅读:632      评论:0      收藏:0      [点我收藏+]

http://acm.hdu.edu.cn/showproblem.php?pid=2516

博弈中的斐波那契数

n =2时输出second

n =3时也是输出second

n =4时,第一个人想获胜就必须先拿1个,这时剩余的石子数为3,此时无论第二个人如何取,第一个人都能赢,输出first

n =5时,first不可能获胜,因为他取2时,second直接取掉剩下的3个就会获胜,当他取1时,这样就变成了n4的情形,所以输出的是second

n =6时,first只要去掉1个,就可以让局势变成n5的情形,所以输出的是first

n =7时,first取掉2个,局势变成n5的情形,故first赢,所以输出的是first

n =8时,当first1的时候,局势变为7的情形,第二个人可赢,first2的时候,局势变成n6得到情形,也是第二个人赢,取3的时候,second直接取掉剩下的5个,所以n =8时,输出的是second

…………

从上面的分析可以看出,n2358时,这些都是输出second,即必败点,仔细的人会发现这些满足斐波那契数的规律,可以推断13也是一个必败点。

 

n =12时,只要谁能使石子剩下8且此次取子没超过3就能获胜。因此可以把12看成8+4,把8看成一个站,等价与对4进行”气喘操作“。

又如1313=8+55本来就是必败态,得出13也是必败态。


 

也就是说,只要是斐波那契数,都是必败点。

所以我们可以利用斐波那契数的公式:fib[i]= fib[i-1]+ fib[i-2],只要n是斐波那契数就输出second

                            取石子游戏

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2336    Accepted Submission(s): 1336

Problem Description
1堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".
 
Input
输入有多组.每组第1行是2<=n<2^31. n=0退出.
 
Output
先取者负输出"Second win". 先取者胜输出"First win".  参看Sample Output.
 
Sample Input
2
13
10000
0
 
Sample Output
Second win
Second win
First win
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
int main()
{
    int n,fib[45]={2,3},i;
    while(~scanf("%d",&n)&&n!=0)
    {
        for(i=2;i<45;i++)
          fib[i]=fib[i-1]+fib[i-2];
        for(i=0;i<45;i++)
        {
            if(fib[i]==n)
            {
                printf("Second win\n");
                break;
            }
        }
        if(i==45)
            printf("First win\n");
    }
    return 0;
}

 

 

HDU-2516 取石子游戏

原文:http://www.cnblogs.com/cancangood/p/3515855.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!