关于巴什博弈的解析以及在C编程中的写法

巴什博弈,是我们代码初学者可能会遇到的一类题型

接下来我将从几个方面为大家讲解

1、巴什博弈的浅解析

2、它的底层逻辑的算法

巴什博弈的浅解析

它的描述是这样的:

假设你和你的朋友都绝对理性,有一堆石头,规定你先手,每一次从这堆石头中取1~m个,规定最后取完的那个人获胜。这个就是巴什博弈。

我们来举一个例子,我们假定m=3,也就是每人每次只能取1~3个石头,而绝对理性的限制告诉我们,两个人都会按自己的最优取法去取出石头,以此达到胜利的目标。

假设石头有n个,当n取4的时候,你会发现无论你怎么取石头,你都必须输。

同理,取5,7,9等等等10一系列数字,输的还是你!

我们来看看问题所在,设当n=m+1的时候,由于是你先手,你至少取一个,假设你取了i个,你取完之后,无论如何,你的朋友都会取走剩下的m+1-1<m个,也就是你输。

这样的情况推广一下,当n=k(m+1)的时候,你先手,你取出i个,你的朋友取出m+1-i个,你的朋友必然胜利(不要问为什么你的朋友会这么取,因为他绝对理性)

当n=k(m+1)+s的时候,你先手,取出s个,(s<=m) 这样就将你的朋友置于上面你的境地当中,这个时候无论怎么取,你都会赢!

底层逻辑算法

大家观察上面的式子,也就是说,当n可以被m+1整除的时候,你先手的情况下,无论怎么取都是你输,而当n不可以被m+1整除的时候,你先手取完,让式子可以被m+1整除,那么你就胜利

这个算法说起来很简单

我们的思考方式是这样

if(n%(m+1)=0);

printf("flase");

if else(n%(m+1!)=0);

printf("true");

如果n取余为0,你失败,如果不为0,你成功。

但这种算法是不是显得太繁杂了,在这里给大家一个我看到的一个很精妙的解法。

bool game(int n)

return n%(m+1)!=0

此时无声胜有声

发表评论

相关文章