博弈论]斐波那契博弈
最编程
2024-05-03 21:32:43
...
「这是我参与11月更文挑战的第20天,活动详情查看:2021最后一次更文挑战」。
斐波那契博弈
简介
一堆有个物品,如果有甲乙两个人。甲和乙轮流从这对物品中选取物品,第一次可以取个物品,后一个人能取的物品数范围是到前一个人取的物品数倍,最后取光物品的人获胜。
思路
若甲先手,设当前物品数为。
当时,甲无法取胜,甲必败。
当时,甲取,乙剩个无法取胜,故甲必胜。
当时,甲若取个及以上乙必胜。甲若取个,乙取个又变成了的情况,乙胜。
根据上述过程,不难发现要想自己赢必须尽可能保证对方拿到斐波那契数。
也就是说,甲先手获胜需要满足不是斐波那契数。
算法模板
首先我们需要能计算斐波那契数
- 递归法
long long fib(int k){
if(k<=1) return 1;
else return fib(k-1)+fib(k-2);
}
- 递推法
long long fib(int k){
fib[0]=fib[1]=1;
for(int i=2;i<=k;i++){
fib[i]=fib[i-1]+fib[i-2];
}
return fib[k];
}
模板
由于递推法的线性复杂度,所以采取递推来实现斐波那契博弈。
bool fibG(int n){//这里返回的是先手玩家是否可以获胜
fib[0]=fib[1]=1;
for(int i=2;fib[i-2]<=n;i++){
if(fib[i-2]==n) return false;
fib[i]=fib[i-1]+fib[i-2];
}
return true;
}
例题
hdu2516
大概概括一下,就是表示物品数,输出第一个人先手时哪个人能获胜,输出获胜的人(First win or Second win),输入表示结束。
#include <iostream>
using namespace std;
int fib[1001];
bool fibG(int n){//这里返回的是先手玩家是否可以获胜
fib[0]=fib[1]=1;
for(int i=2;fib[i-2]<=n;i++){
if(fib[i-2]==n) return false;
fib[i]=fib[i-1]+fib[i-2];
}
return true;
}
int main(){
int n;
while(cin>>n,n!=0){
if(fibG(n)) cout<<"First win\n";
else cout<<"Second win\n";
}
return 0;
}
尝试推广
如果规定先取完的人输,再看一下策略。
因为甲可以取个,那么甲直接取个,留下个给乙,则乙必输。
上一篇: 单个链接表是否有环,有两种方法可以实现!
下一篇: 第 7 课 盈亏问题中的乘数关系