
博弈问题(巴什博弈 威佐夫博弈 尼姆博弈 斐波拉契博弈)结论
发布日期:2021-06-21 03:12:36
浏览次数:15
分类:技术文章
本文共 1273 字,大约阅读时间需要 4 分钟。
巴什博弈
有一堆n个石子从里面取,一次从里面取1~m个,最后取完者获胜。
结论:如果n%(m+1)==0 先手必败 n%(m+1)!=0为先手必胜。
HDU 4764
#include<iostream>
#include<algorithm>using namespace std;int main(){ int n,m; while(cin>>n>>m) { if(n==0&&m==0) break; if((n-1)%(m+1)!=0) cout<<"Tang"<<endl; else cout<<"Jiang"<<endl; } }威佐夫博弈
有两堆石子,每次要么从一堆中取任意个,最少为1;要么从两堆中取出相同个,最后取完者获胜。
结论:用最大的一堆减去最小的一堆的值*(1+sqrt(5)/2) 如果等于较小的那堆个数,先手必败 否则先手必胜。
尼姆博弈
任意堆石子,每次从中取任意个石子,最少为一个,最后取完者获胜。
结论:将所有堆的石子异或起来,如果等于0先手必败,否则先手必胜。
HDU2176
#include<cstdio>
#include<iostream>#include<algorithm>using namespace std;int main(){ int n,a[10005]; while(cin>>n) { int k,tmp=0; for(int i=0;i<n;i++) { cin>>a[i]; tmp^=a[i];} if(tmp==0) cout<<"No"<<endl; else { cout<<"Yes"<<endl; for(int i=0;i<n;i++) { int t=tmp^a[i]; if(t<a[i]) { cout<<a[i]<<" "<<t<<endl; } } } }return 0;}
斐波拉契博弈
一堆物品轮流取,每次最少一个最多无上限,后一次最多为前一次的两倍,最少一个,最后取完者胜利。
结论:当n不是斐波拉契数,先取者胜利,反之后者。
HDU2516
#include <iostream>
#include <string.h> #include <stdio.h> using namespace std; const int N = 55; int f[N]; void Init() { f[0] = f[1] = 1; for(int i=2;i<N;i++) f[i] = f[i-1] + f[i-2]; } int main() { Init(); int n; while(cin>>n) { if(n == 0) break; bool flag = 0; for(int i=0;i<N;i++) { if(f[i] == n) { flag = 1; break; } } if(flag) puts("Second win"); else puts("First win"); } return 0; }转载地址:https://blog.csdn.net/k_koris/article/details/80214487 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2025年02月15日 00时46分41秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
类豌豆荚: Linux Mint实测QtADB安卓管理客户端
2019-06-30
SpringBoot之Starter相关说明
2019-06-30
LVS 负载均衡集群学习笔记
2019-06-30
一个根据内存使用情况重启tomcat的小脚本
2019-06-30
kickstart命令及安装引导光盘的制作
2019-06-30
docker 安装配置
2019-06-30
rsync:include和exclude参数
2019-06-30
指针和链条
2019-06-30
jQuery选择器和事件
2019-06-30
angular2 返回一个数组里面的内容禁用 新增一天是可编辑的状态
2019-06-30
喜迎2015年新年:坦克大战(Robocode)游戏编程比赛图文总结
2019-06-30
ETCD集群部署
2019-06-30
oracle 10046
2019-06-30
javascript中的焦点管理
2019-06-30
记一次网项目(一)
2019-06-30
拆分一个大文件(linux)
2019-06-30
javascript-事件默认行为/右键菜单、拖拽
2019-06-30
用Xmanager远程登录AIX图形界面
2019-06-30
我的友情链接
2019-06-30