題意：
給定兩個非負數，可以用較小那個數的任意正整數倍數去減較大那個數，但要保證結果非負。兩個人輪流操作，結果中先出現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
小鼠標 閱讀(265)
評論(0) 編輯 收藏 引用 所屬分類:
博弈