设计简单的网站,wordpress网站好做排名吗,深圳房地产最新消息,登录文章目录斐波那契博弈问题#xff1a;结论证明#xff1a;尼姆博奕(Nimm Game)问题#xff1a;结论#xff1a;证明#xff1a;代码#xff1a;公平组合博弈#xff08;Impartial Combinatori Games#xff09;理论知识#xff08;1#xff09;、若面临末状态者为获胜…
文章目录斐波那契博弈问题结论证明尼姆博奕(Nimm Game)问题结论证明代码公平组合博弈Impartial Combinatori Games理论知识1、若面临末状态者为获胜则末状态为胜态否则末状态为必败态。2、一个局面是胜态的充要条件是该局面进行某种决策后会成为必败态。3、一个局面是必败态的充要条件是该局面无论进行何种决策均会成为胜态斐波那契博弈
问题
有一堆数量为n的石子游戏双方轮流取石子满足
1先手不能在第一次把所有的石子取完
2之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间包含1和对手刚取的石子数的2倍。
约定取走最后一个石子的人为赢家。 求必败态
结论
当n为斐波那契数时先手必败。
证明
齐肯多夫(zeckendorf)定理 任何正整数都可以表示成若干个不连续的斐波那契数(不包括第一个斐波那契数)之和 比如n54 n还可以写成n251334 先手A取两个后手B取的范围是1~4也就是5之后取不了那第五个肯定被A拿了因为至少拿一个也就是拿走了5的最后一颗接下来A也能拿走13的最后一颗拿走34的最后一颗这样A就赢了。 反之如果n是斐波那契数A就输了
尼姆博奕(Nimm Game)
问题
有三堆各若干个物品数量分别是a,b,c两个人轮流从某一堆取任意多的物品规定每次至少取一个多者不限最后取光者得胜。
结论
如果每堆物品数全部异或起来得到的值时0则先手必败反之先手则赢
(a,b,c)的必败态等于a ^ b ^ c 0
如果石头有n堆如果每堆数目进行异或后为0则是必败态
证明
略。。
代码 for(int i1;in;i) { cinans; sum^ans; } if(sum0) cout后手必胜endl; else cout先手必胜endl; 公平组合博弈Impartial Combinatori Games
这个第一次见还没搞懂
