本文主要是介绍博弈---斐波那契博弈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
参考的这里
题目：http://acm.hdu.edu.cn/showproblem.php?pid=2516
题意：
一堆石子有n个，两人轮流取，先取者第1次可以取任意多个，但不能全部取完，以后每次取的石子数不能超过上次取子数的
2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win"。
分析：这个跟威佐夫博弈和取石子游戏有一个很大的不同点，就是游戏规则的动态化。后两者的规则中，每次可以取的石子
的策略集合是基本固定的，但是这次有规则2：一方每次可以取的石子数依赖于对手刚才取的石子数。
这个游戏叫做Fibonacci Nim，肯定和Fibonacci数列f[n]：1,2,3,5,8,13,21,34,55,89,… 有密切的关系。如果试
验一番之后，可以猜测：先手胜当且仅当n不是Fibonacci数，换句话说，必败态构成Fibonacci数列。
下面简单谈谈“先手败当且仅当n为Fibonacci数列”这一结论是怎么得来的。
这里要用到一个很有用的定理：任何正整数可以表示为若干个不连续的 Fibonacci 数之和。
这里定理涉及到数论，这里不做证明。下面只谈如何把一个正整数表示为若干个不连续的 Fibonacci 数之和。
比如，我们要分解83，注意到83被夹在55和89之间，于是把83可以写成83=55+28；然后再想办法分解28，28被夹在21和
34之间，于是28=21+7；依此类推 7=5+2，故83=55+21+5+2。
如果 n 是 Fibonacci 数，比如 n = 89。89前面的两个Fibonacci 数是34和55。如果先手第一次取的石子不小于34
颗，那么一定后手赢，因为 89 - 34 = 55 = 34 + 21 < 2*34，注意55是Fibonacci数。此时后手只要将剩下的全部
取光即可，此时先手必败。故只需要考虑先手第一次取得石子数 < 34 即可，于是剩下的石子数 x 介于 55 到 89 之
间，它一定不是一个 Fibonacci 数。于是我们把 x 分解成 Fibonacci 数：x = 55 + f[i] + … + f[j]，其中
55 > f[i] > … > f[j]，如果 f[j] ≤ 先手一开始所取石子数 y 的两倍，那么对后手就是面临 x 局面的先手，所以
根据之前的分析，后手只要先取 f[j] 个即可，以后再按之前的分析就可保证必胜。
下证：f[j] ≤ 2y
反证法：假设f[j]>2y，则 y < f[j]/2 = (f[j-1] + f[j-2])/2 < f[j-1]。而最初的石子数是个斐波那契数，即
n = f[k] = x + y < f[k-1] + f[i] + … + f[j] + f[j-1] ≤ f[k-1]+f[i]+f[i-1] ≤ f[k-1]+f[k-2] ≤
f[k] （注意第一个不等号是严格的），矛盾！f[j] ≤ 2y得证。
如果 n 不是 Fibonacci 数，比如n=83，我们看看这个分解有什么指导意义：假如先手取2颗，那么后手无法取5颗或更
多，而5是一个Fibonacci数，如果猜测正确的话，（面临这5颗的先手实际上是整个游戏的后手）那么一定是整个游戏的
先手取走这5颗石子中的最后一颗，而这个我们可以通过第二类归纳法来绕过，同样的道理，根据“先手败当且仅当n为
Fibonacci数列”，接下去先手取走接下来的后21颗中的最后一颗，再取走后55颗中的最后一颗，那么先手赢。
#include <iostream>
#include <string.h>
#include <stdio.h>using namespace std;
const int N = 55;int f[N];void Init()
{f[0] = f[1] = 1;for(int i=2;i<N;i++)f[i] = f[i-1] + f[i-2];
}int main()
{Init();int n;while(cin>>n){if(n == 0) break;bool flag = 0;for(int i=0;i<N;i++){if(f[i] == n){flag = 1;break;}}if(flag) puts("Second win");else puts("First win");}return 0;
}
这篇关于博弈---斐波那契博弈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
