题意：
给定两个非负数，可以用较小那个数的任意正整数倍数去减较大那个数，但要保证结果非负。两个人轮流操作，结果中先出现0的那个人获胜。
第一次做博弈题，不知如何下手。这里认真分析一下。
假设两个数a b，他们的大小关系无非是a>b,a<b,a==b中的一种，对本题二样前两种其实是同一种情况，第三种情况时结果已经出来了（此时轮到谁谁获胜）。
我们再来讨论a>b（a<b）的情况，又可细分为：
b<a<2 * b (1)
a == 2 * b (2)
a >2*b (3)
对情况（1），选手没得选，只能用较小的树去减较大的数，下一个状态一定是b，a%b。也就是说这种状态的出现不会影响最终结果。
情况（2），显然，也可以结束游戏了，当前选手赢了。
情况（3），此时选手可以决定下一个状态是下面状态中的一种：
a-b, b
a-2*b, b
a-3*b, b
.
.
.
a%b+b, b （k-1）
b, a%b （k）
由于两个选手必须轮流操作，因此，两相邻的状态的输赢结果一定相反。而此时，选手恰恰可以决定是到状态（k-1）还是到状态（k）（状态（k-1）的下一个状态一定是状态（k），因为情况（1）），也就是说此时选手能决定自己的输赢。
综上我们可以得到如下结论
出现下述情况之一的就可断定当前选手获胜：
1.a==b
2.a>=2*b
细节：如果一开始输入数据为a，0，本题认为Ollie wins
import java.io.*;
import java.util.*;
class Main {
static boolean firstWin;
public static void main(String[] args) throws IOException{
int a, b;
Scanner sc = new Scanner(System.in);
a = sc.nextInt();
b = sc.nextInt();
while(a != 0 || b != 0){
firstWin = true;//初始认为Stan wins
if(a >= b)
get(a, b);
else
get(b, a);
if(firstWin)
System.out.println("Stan wins");
else
System.out.println("Ollie wins");
a = sc.nextInt();
b = sc.nextInt();
}
}
public static void get(int a, int b){//a >= b
if(a == b)
return;
if(b == 0){//边界情况，如果一开始输入是b为零，我们认为Ollie wins
firstWin = !firstWin;
return;
}
if(a / b >= 2)
return;
firstWin = !firstWin;
get(b, a % b);
}
}
posted on 2013-05-04 16:21
小鼠标 阅读(239)
评论(0) 编辑 收藏 引用 所属分类:
博弈