NYOJ题目358 取石子(五)hdu题目2516 取石子游戏 Fibonacci’s Game(斐波那契博弈)

取石子(五)

时间限制:1000 ms  |  内存限制:65535 KB
难度:4
描述
himdd最近很想玩游戏,于是他找到acmj和他一起玩,游戏是这样的:有一堆石子,两个人轮流从其中取走一定的石子,取走最后所有石子的人为赢家,不过得遵循如下规则:
1.第一次取不能取完,至少取1颗.

2.从第二次开始,每个人取的石子数至少为1,至多为对手刚取的石子数的两倍。

himdd事先想知道自己会不会赢,你能帮帮他吗?(每次himdd先手)

输入
有多组测试数据,每组有一个整数n(2<=n<2^64);
输出
himdd会赢输出Yes,否则输出No;
样例输入
2
5
6
样例输出
No
No
Yes


先取者 :斐波纳契数列为必败点

 
/***************************
# 2013-8-25 11:33:04 
# Time: 8MS   Memory: 232KB
# Author: zyh
# Status: Accepted
***************************/ 

#include<stdio.h>

long long n,f[100];
int main()
{

	f[0] = 2; f[1] = 3;
	for(int i=2;i<100;i++){
		f[i] = f[i-1] + f[i-2];
	}
	
	while(scanf("%lld",&n)!=EOF)
	{
		int flag = 1;
		for(int i=0;i<100;i++){
			if(f[i]==n) {
				flag =0;
				break;
			}
		}
		printf("%s\n",!flag?"No":"Yes");
	}
	return 0;
}         





取石子游戏

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


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
 
/***************************
# 2013-8-25 11:33:04 
# Time: 0MS   Memory: 228KB
# Author: zyh
# Status: Accepted
***************************/ 

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>

using namespace std;

long long n,f[50];
int main()
{

    f[0] = 2; f[1] = 3;
    for(int i=2;i<45;i++){
        f[i] = f[i-1] + f[i-2];
    }
    
    while(scanf("%lld",&n),n)
    {
        int flag = 1;
        for(int i=0;i<45;i++){
            if(f[i]==n) {
                flag =0;
                break;
            }
        }
        printf("%s\n",!flag?"Second win":"First win");
    }
    return 0;
}