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

快来打我* 2024-02-17 20:50 34阅读 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 条评论，34人围观）

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

相关阅读

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

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

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

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

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

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

相关 HDOJ 2516-取石子游戏

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

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

相关斐波那契数列

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

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

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

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

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

相关斐波那契数列

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

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

相关斐波那契数列

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

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

相关斐波那契数列

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

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

相关斐波那契查找

1. 问题描述我们知道，对于有序数据序列进行查找，二分查找法性能是相当好的，时间效率达到O(log2n)，但该算法其实还有些可以进行改进的地方。普通的折半查找直接通过折

Bertha 。/ 2022年03月28日 10:46/ 0 赞/ 304 阅读

相关斐波那契博弈

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

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