两种常见的取物品游戏:
1.一堆物品
两人轮流取一堆物品,物品数量为n,规定每次至少取一个物品,最多为m个,最后取完者获胜。
思路:如果n=m+1,由于一次最多只能取m个物品,那么无论先取者如何去取,后取的都能获胜。
那么先取者想要获胜的关键就是保证每次取完之后剩余物品的数量都是m+1的倍数,即如果n=r(m+1)+s,先取者要先取走s个,依次保持下去。
2.两堆物品
经典的例子就是POJ ACM 1067题,两个人轮流取石子,每人可以从一堆中取任意数量的石子,或者从两堆中取走相同数量的石子,给定两堆石子的食量,问先取者是否可以获胜。
威佐夫博弈:用(a
k,b
k)表示两堆物品数量,称之为局势,如果甲面对(0,0)局势,那么说明甲已经输了,类似的局势还有
(1,2) (3,5) (4,7) (6,10) (8,13) (9,15) (11,18) (12,20)...
这种局势叫做奇异局势,ak是前面没有出现的最小自然数,bk=ak+k
奇异局势的特点:
1.任何一个自然数都包含在一个且仅有一个奇异局势中。
2.任何操作都可以将奇异局势变为非奇异局势。
3.可以通过适当的方法将非奇异局势变为奇异局势。
所以面对奇异局势的人是不能获胜的。
判断一个局势是不是奇异局势的方法:
ak=[k(1+√5)/2],bk=ak+k ([]是取整运算)
(1+√5)/2=1.6180339887...黄金分割数
于是,取石子游戏的实现如下:
#include<stdio.h>
int main()
{
int n,m,k;
double R=1.6180339887,r=1/R;
scanf("%d%d",&n,&m);//input
//swap if n>m
if(n>m)
{
k=n;
n=m;
m=k;
}
k=n*r;
if(n!=(int)k*R)
++k;
if(m!=(int)k*R+k)
printf("1\n");
else
printf("0\n");
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 3752 字母旋转游戏.md
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告