【博弈论 && 斐波那契博弈】 HRPA

HRPA

---

这道题就是一个斐波那契博弈的经典模型：
有一堆个数为n的石子，第一个人第一次不能全部取完，每次一个人取石子的个数都应当大于0，且小于等于上一个人取的石子个数的两倍。
问是否有先手必胜策略。
如果有，第一个人取的石子个数最少是多少？

---

分析：

这边我们先引入一个齐肯多夫（Zeckendorf）定理：

• 任何正整数都可以表示成若干个不连续的斐波那契数之和。

这个定理使我们分析这道题目的理论基础。

我们先抛出一个结论：
如果n恰好是斐波那契数，那么先手必败。
为什么呢？
由于n是斐波那契数，那么$n=f_x+f_{x+1}$
先手的人不能直接取>=$f_x$个数的石子，因为这样后手就可以直接取完剩下的石子。
那么问题就变成了，先手有没有策略分别取完$f_x$和$f_{x+1}$个数的石子。
由于$f_x$和$f_{x+1}$都是斐波那契数列，因此问题产生了迭代。
边界情况是$x=2$，即$n=2$的情况。
这个时候，先手只能取1，因此后手胜利。

综上，如果n恰好是斐波那契数，那么后手必胜。

那么，如果n不是斐波那契数列呢？
根据齐肯多夫定理，n可以分解为若干个不连续的斐波那契数列之和:
$n=f_{x1}+f_{x2}+f_{x3}+\dots \dots$
这里，f数组依次递增。
那么，这个时候，先手取完$f_{x1}$之后，就可以必胜。
为什么呢？
首先，我们要知道，$2\ast f_{x1}<f_{x2}(1)$，这也就是说，如果我们取了$f_{x1}$，对方也没有办法直接取完$f_{x2}$，这个时候对方也就落入了第一种情况的被动局面。
但是，$(1)$怎么证明呢？
我们利用反证法，假设$2\ast f_{x1}>=f_{x2}$，那么这个时候$x_2$必然等于$x_1+1$，那么$f_{x1}+f_{x2}=$$f_{x1}+f_{x1+1}=f_{x1+2}$，也就是说，这两个斐波那契数，可以用$f_{x1+2}$代替，那么也就不会存在$f_{x1}+f_{x2}$这种情况了。
因此，如果想要这种斐波那契分解存在，就必须满足$条件(1)$

那么这题的分析到这里就结束了。

---

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e5+100;
int n;
int f[N];
int nn;

signed main(){
int x; cin>>x;
f[0] = 1;
f[++n] = 1; f[++n] = 1;
for (int i = 3; i <= 1000; i++){
if (f[n] > x) break;
f[++n] = f[i-1]+f[i-2];
}
int now = n-1;
while (x){
while (f[now] > x) now--;
x-=f[now];
if (x == 0) cout<<f[now]<<endl;
}
return 0;
}

原文地址：https://blog.csdn.net/huang_ke_hai/article/details/142363079

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！