題意：
給定兩個(gè)非負(fù)數(shù)，可以用較小那個(gè)數(shù)的任意正整數(shù)倍數(shù)去減較大那個(gè)數(shù)，但要保證結(jié)果非負(fù)。兩個(gè)人輪流操作，結(jié)果中先出現(xiàn)0的那個(gè)人獲勝。
第一次做博弈題，不知如何下手。這里認(rèn)真分析一下。
假設(shè)兩個(gè)數(shù)a b，他們的大小關(guān)系無(wú)非是a>b,a<b,a==b中的一種，對(duì)本題二樣前兩種其實(shí)是同一種情況，第三種情況時(shí)結(jié)果已經(jīng)出來(lái)了（此時(shí)輪到誰(shuí)誰(shuí)獲勝）。
我們?cè)賮?lái)討論a>b（a<b）的情況，又可細(xì)分為：
b<a<2 * b (1)
a == 2 * b (2)
a >2*b (3)
對(duì)情況（1），選手沒(méi)得選，只能用較小的樹(shù)去減較大的數(shù)，下一個(gè)狀態(tài)一定是b，a%b。也就是說(shuō)這種狀態(tài)的出現(xiàn)不會(huì)影響最終結(jié)果。
情況（2），顯然，也可以結(jié)束游戲了，當(dāng)前選手贏了。
情況（3），此時(shí)選手可以決定下一個(gè)狀態(tài)是下面狀態(tài)中的一種：
a-b, b
a-2*b, b
a-3*b, b
.
.
.
a%b+b, b （k-1）
b, a%b （k）
由于兩個(gè)選手必須輪流操作，因此，兩相鄰的狀態(tài)的輸贏結(jié)果一定相反。而此時(shí)，選手恰恰可以決定是到狀態(tài)（k-1）還是到狀態(tài)（k）（狀態(tài)（k-1）的下一個(gè)狀態(tài)一定是狀態(tài)（k），因?yàn)榍闆r（1）），也就是說(shuō)此時(shí)選手能決定自己的輸贏。
綜上我們可以得到如下結(jié)論
出現(xiàn)下述情況之一的就可斷定當(dāng)前選手獲勝：
1.a==b
2.a>=2*b
細(xì)節(jié)：如果一開(kāi)始輸入數(shù)據(jù)為a，0，本題認(rèn)為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;//初始認(rèn)為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){//邊界情況，如果一開(kāi)始輸入是b為零，我們認(rèn)為Ollie wins
firstWin = !firstWin;
return;
}
if(a / b >= 2)
return;
firstWin = !firstWin;
get(b, a % b);
}
}
posted on 2013-05-04 16:21
小鼠標(biāo) 閱讀(262)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
博弈