hdu 2516 取石子游戏（斐波那契博弈）

快来打我* 2024-02-17 20:50 75阅读 0赞

## 取石子游戏 ##

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

分析：斐波那契博弈 可以参考这篇博文 ：http://blog.csdn.net/dgq8211/article/details/7602807

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=100;
    typedef long long LL;
    LL f[maxn];
    int main(){
    	f[0]=0;f[1]=1;
    	int i=1;
    	do{
    		i++;
    		f[i]=f[i-1]+f[i-2];
    	}while(f[i]<(1<<31)-1);
    	int T=i-1;
    
    	int n;
    	while(scanf("%d",&n)==1 && n){
        
        if(f[T]<n)printf("First win\n");
        else 
    	for(i=2;i<=T;i++){
    	   if(f[i]==n){
    	   	printf("Second win\n");
    	   	break;
    	   }
    	   if(f[i]>n){
    	   	printf("First win\n");	
    	   	break;
    	   }
    	 }	
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，75人围观）

还没有评论，来说两句吧...

相关阅读

相关博弈论 | 斐波那契博弈

斐波那契博弈博弈论是二人或多人在平等的对局中各自利用对方的策略变换自己的对抗策略,达到取胜目标的理论。博弈论是研究互动决策的理论。博弈可以分析自己与对手的利弊关系,从

柔光的暖阳◎/ 2024年03月24日 19:00/ 0 赞/ 62 阅读

相关 hdu 2516 取石子游戏（斐波那契博弈）

取石子游戏 Problem Description 1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上

快来打我*/ 2024年02月17日 20:50/ 0 赞/ 76 阅读

相关 HDOJ 2516-取石子游戏

取石子游戏 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

ゞ浴缸里的玫瑰/ 2022年08月20日 04:19/ 0 赞/ 215 阅读

相关 hdu-2516 斐波那契数sg值

不管怎样，我是先写出了前十个数的情况。发现2，3，5，8是必败态，因此猜想凡是n的值为斐波那契数就是先手的必败态，否则为胜态。猜想完成当然要验证了，接下来先证：n

灰太狼/ 2022年08月12日 01:59/ 0 赞/ 8 阅读

相关斐波那契数列

关于斐波那契数列的解法，本人找到了一种比较简单的方法，结果是正确的，不知道各位有没有另外更好的解法，一起探讨探讨。 import java.util.; pu

╰+攻爆jí腚メ/ 2022年08月01日 12:15/ 0 赞/ 427 阅读

相关 HDU 2516-取石子游戏（斐波那契博弈）

取石子游戏 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

小灰灰/ 2022年07月24日 03:27/ 0 赞/ 224 阅读

相关斐波那契数列

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，

冷不防/ 2022年07月13日 03:19/ 0 赞/ 369 阅读

相关斐波那契数列

class FibIter(object): def __init__(self, lenth): self.lent

一时失言乱红尘/ 2022年05月27日 13:51/ 0 赞/ 368 阅读

相关斐波那契数列

include<iostream> using namespace std; int fibonacci1(int t) { if(t

古城微笑少年丶/ 2022年05月09日 08:58/ 0 赞/ 340 阅读

相关斐波那契博弈

一堆个数为n的物品，双方轮流按如下规则取物品，取完最后物品的人胜利。先手不可以第一次取完所有物品。之后每次可以取得物品个数1<=k<=对手上次取得个数的2倍。

阳光穿透心脏的1/2处/ 2021年12月24日 13:51/ 0 赞/ 218 阅读