首页 > ACM题库 > HDU-杭电 > hdu 2516 取石子游戏-博弈论-[解题报告]C++
2014
02-09

hdu 2516 取石子游戏-博弈论-[解题报告]C++

取石子游戏

问题描述 :

1堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".

输入:

输入有多组.每组第1行是2<=n<2^31. n=0退出.

输出:

输入有多组.每组第1行是2<=n<2^31. n=0退出.

样例输入:

2
13
10000
0

样例输出:

Second win
Second win
First win

hdu2516

2

3

4(-1)                解释4 – 1 = 3 , n==3为必败点,所以4为必胜点

5

6(-1)

7(-2)

8

9(-1)

10(-2)

11(-3)

12(-1)  

13

然后就是斐波纳契……

#include<iostream>
using namespace std;

int num[50];
void init()
{
    int i;
    num[1]=1;num[2]=2;
    for(i=3;i<=45;i++)    num[i]=num[i-1]+num[i-2];
    
}

int main()
{
    init();
    int i,j;
    while(scanf("%d",&i),i)
    {
        for(j=1;j<=45;j++)
            if(i==num[j])
                break;
        if(j!=46)    printf("Second win\n");
        else        printf("First win\n");
    }
    
    return 0;
}

解题转自:http://blog.csdn.net/dellaserss/article/details/7935598


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.