学习笔记目录

巴什博弈——不用 for 循环的算法

有任何问题，欢迎私信/评论。
码字不易，求点赞啦~

巴什博弈：有一堆石子，共 $n$ 个。两个人轮流从中取石子，规定每次每人最少取 $1$ 个，最多取 $m$ 个。最后，无法再取石子的人失败。若两人 $IQ$ 奇高无比，问：先手有没有必胜策略？

为了让读者更好的理解游戏规则，蒟蒻自编了一个 $cpp$ 游戏（或许这次是我第一次在学习笔记中引入游戏元素），复制到 dev-cpp 中食用更佳~。

#include<bits/stdc++.h>
#include<unistd.h>
#include<ctime>
using namespace std;
int main(){
    srand((int)time(NULL));
    int n=rand()%91+10,m=rand()%16+5;
    printf("现在有 %d 个石头，您与计算机轮流取石头，您先取，电脑后取。\n",n);
    printf("规定每人最少取 1 个石子，最多取 %d 个石子\n",m);
    int rd=1;
    while(n!=0){
        printf("========== Round %d ==========\n",rd);
        if(rd%2==1){
            printf("请您输入您想取走的石子个数： ");
            int take;
            scanf("%d",&take);
            while(take<=0 || take>m || take>n){
                if(take<=0)printf("警告：至少取走 1 个石子，请重新输入：");
                else if(take>m)printf("警告：至少取走 %d 个石子，请重新输入：",m);
                else if(take<n)printf("警告：总共只有 %d 个石子，而您取了 %d 个石子，请重新输入：",n,take);
                scanf("%d",&take);
            }
            n-=take;
            printf("现在还剩 %d 个石子。\n",n);
            if(n==0)printf("恭喜您，您获胜了！！！");
        }
        else{
            printf("请电脑输入电脑想取走的石子个数： ");
            int take;
            sleep(3);
            if(n<=m)take=n;
            else take=rand()%m+1;
            printf("%d\n",take);
            n-=take;
            sleep(1);
            printf("现在还剩 %d 个石子。\n",n);
            if(n==0)printf("恭喜电脑，电脑获胜了！！！");
        }
        rd++;
        cout<<endl; 
    }
    return 0;
}

初次看到这题，是否有些熟悉？回想一下小学奥数题：

甲乙轮流报数，最多报 $7$ 个数，最少报 $1$ 个数，从 $1$ 开始，谁先报到 $50$ 谁就胜利。甲先报，有无必胜策略？

甲有必胜策略。他先报 $2$ 个数，这样还有 $48$ 个数要报。之后每次乙报 $x$ 个数，甲都报 $8-x$ 个数，所以每一轮都会去掉 $8$ 个数字，$6$ 轮以后，甲胜利。

同理，在巴什博弈中，当 $n≡s\ (\mod m+1)\ \ (1\leq s \leq m)$ 时，即 $n$ 无法被 $m+1$ 整除，那么先手取走 $s$ 个石子。之后后手每取走 $k$ 个石子，先手都取 $m+1-k$ 个石子，若干轮之后，先手取光石子，先手获胜。

有上面的推到，我们可以知道，当 $n$ 不能被 $m+1$ 整除时，先手有必胜策略；即 $n$ 能被 $m+1$ 整除时，后手有必胜策略。

【代码】

#include <iostream>
using namespace std;
int main() {
    int n,m;
    cin>>n>>m;
    if(n%(m+1)==0){
        cout<<"后手必胜"<<endl;
    } else {
        cout<<"先手必胜"<<endl;
    }
    return 0;
}