【博弈论】斐波那契博弈斐波那契博弈例题尝试推广

56 阅读 0 评论 37 点赞

我是靠谱客的博主纯情眼睛，最近开发中收集的这篇文章主要介绍【博弈论】斐波那契博弈斐波那契博弈例题尝试推广，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

斐波那契博弈

简介

一堆有 $n$ 个物品，如果有甲乙两个人。甲和乙轮流从这对物品中选取物品，第一次可以取 $1 \sim n - 1$ 个物品，后一个人能取的物品数范围是 $1$ 到前一个人取的物品数 $2$ 倍，最后取光物品的人获胜。

思路

若甲先手，设当前物品数为 $r$ 。

当 $r \leq 3$ 时，甲无法取胜，甲必败。

当 $r = 4$ 时，甲取 $1$ ，乙剩 $3$ 个无法取胜，故甲必胜。

当 $r = 5$ 时，甲若取 $2$ 个及以上乙必胜。甲若取 $1$ 个，乙取 $1$ 个又变成了 $r = 3$ 的情况，乙胜。

根据上述过程，不难发现要想自己赢必须尽可能保证对方拿到斐波那契数。

也就是说，甲先手获胜需要满足 $n$ 不是斐波那契数。

算法模板

首先我们需要能计算斐波那契数

递归法

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

大概概括一下，就是 $n$ 表示物品数，输出第一个人先手时哪个人能获胜，输出获胜的人(First win or Second win)，输入 $0$ 表示结束。

#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 winn";
        else cout<<"Second winn";
    }
    return 0;
}