【POJ 2348】Euclid's Game 【简单博弈】
可以用搜索的姿势写过。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
long long a,b;
bool Judge(int a,int b)
{
if(a < b) swap(a,b);
if(!b) return false;
int end = a / b;
for(int i = end; i >= 1; --i)
if(!Judge(a - i * b,b))
return true;
return false;
}
int main()
{
long long x,y;
while(scanf("%lld%lld",&x,&y),x + y)
printf("%s\n",Judge(x,y) ? "Stan wins":"Ollie wins");
}下面有个题解：
分析：每次令a大于b，
1 如果a-b<b，则只能有一种减的方法，即a=a-b
2. a-b>b，则有多种减的方法，a减去b的倍数后，可能结果小于b，如果小于b，下一步将是固定的走法；如果减去后达到第一种情况，后面也还是固定减法，即此时你可以决定后面的两种减法（必胜和必败），也就是你可以选择到达下面式子的x还是y，既然可以选择输赢，当然是赢。
x（4,7）-y（4,3）-z（