大佬教程收集整理的这篇文章主要介绍了博弈论:Nim游戏,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
给定 n 堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
先手可以直接将整堆直接拿走,让第二个人没有办法拿到任何东西
后手可以通过在先手所拿的堆相对的另外一堆中拿和先手相同的数量(跟随策略),从而能保证自己最后能拿光。
先手可通过在两堆中数量较多的那一堆中拿出一定的数量使得两堆的数量相等,从而将当前的局面转化成局面二,局面三的先手转化成局面二的后手。
相当于局面一和局面三的叠加
每堆的数量异或,如果最终为0,则先手必输。
#include<bits/stdc++.h>
using namespace std;
const int n = 1E5+10;
int stone[n];
int main()
{
int n;
cin>>n;
int ans;
cin>>ans;
for(int i=2;i<=n;i++)
{
int x;
cin>>x;
ans=ans^x;
}
if(ans==0) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
return 0;
}
给定 n 堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
此时为必胜态,直接拿完,对手就没有办法再拿了。
此时为必败态,先手者替别人打工,刚从第二级台阶拿到第一级台阶,后手者就可以把刚拿下来的石子一下子拿到地面。
此时为必败态,先手从第一级台阶拿出多少放到地上,后手就从第三级台阶拿出多少放到第二级台阶,先不考虑接触第二级台阶上的石子。按以上操作反复进行,会发现只有第二级台阶剩下石子,也就变成了局面二(必败态)。
此时先手可在第一级台阶和第二级台阶中的拥有更多的石子的那个台阶拿出一定数量的石子使得两个台阶的石子数量相等(局面三),而此时局面四的先手将转化为局面三的后手(局面三是后手胜利)。
根据跟随策略,可将局面五转化成局面三或者局面四。
可转换为局面二,可以忽略掉偶数级台阶的石子。
台阶-Nim游戏可当作是只考虑奇数级台阶的普通版本的Nim游戏
奇数堆的数量异或,如果最终为0,则先手必输。
#include<bits/stdc++.h>
using namespace std;
const int n = 1E5+10;
int stone[n];
int main()
{
int n;
cin>>n;
int ans;
cin>>ans;
for(int i=2;i<=n;i++)
{
int x;
cin>>x;
if(i&1)ans=ans^x;
}
if(ans==0) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
return 0;
}
以上是大佬教程为你收集整理的博弈论:Nim游戏全部内容,希望文章能够帮你解决博弈论:Nim游戏所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。