首页 > 代码库 > POJ 1067: Wythoff Game【博弈】

POJ 1067: Wythoff Game【博弈】

经典的威佐夫博奕把黄金分割常数乘以kk=m-n)即为奇异点,此时奇异点是用小数据观察出来的,具体的数学证明,观察到黄金分割常数是无理数,再加上高斯函数[kφ]的形势将自然数分割成两个等价类很容易想到beatty定理,很容易解出α和β

 

#include<iostream>

#include<cstdio>

#include<string.h>

#include <stdlib.h>

#include <math.h>

using namespace std;

int min(int a,int b)

{

    if(a<b)return a;else return b;

}

int main()

{

   int m,n,k;

   double fai=((sqrt(5.0)+1)/2);

   while(scanf("%d%d",&n,&m)!=EOF)

    {

       k=abs(m-n);

       if (min(m,n)==(int)(k*fai))printf("0\n");elseprintf("1\n");

    }

   return 0;

}

POJ 1067: Wythoff Game【博弈】