???????????????????????????? 取(2堆)石子游戲

????????????????????? Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
?????????????????????????????????????????????? Total Submission(s): 3854????Accepted Submission(s): 2381
Problem Description

有兩堆石子，數(shù)量任意，可以不同。游戲開始由兩個(gè)人輪流取石子。游戲規(guī)定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時(shí)取走相同數(shù)量的石子。最后把石子全部取完者為勝者。現(xiàn)在給出初始的兩堆石子的數(shù)目，如果輪到你先取，假設(shè)雙方都采取最好的策略，問最后你是勝者還是敗者。如果你勝，你第1次怎樣取子? Input 輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個(gè)非負(fù)整數(shù)a和b，表示兩堆石子的數(shù)目，a和b都不大于1,000,000，且a<=b。a=b=0退出。 Output 輸出也有若干行，如果最后你是敗者，則為0，反之，輸出1，并輸出使你勝的你第1次取石子后剩下的兩堆石子的數(shù)量x,y,x<=y。如果在任意的一堆中取走石子能勝同時(shí)在兩堆中同時(shí)取走相同數(shù)量的石子也能勝，先輸出取走相同數(shù)量的石子的情況. Sample Input 1 2 5 8 4 7 2 2 0 0 Sample Output 0 1 4 7 3 5 0 1 0 0 1 2 這到題明顯的是威佐夫博弈題。我們用（a[k],b[k])(a[k]<=b[k],k=0,1……n)表示兩堆物品的數(shù)量，并稱其為奇異局勢。k表示局勢的序號，第一個(gè)局勢k=0；列舉一下前幾個(gè)奇異局勢：(0,0) (1,2) (3,5) (4,7)……? 可以看出，a[0]=a[0]=0,a[k]是未在前面出現(xiàn)過的最小自然數(shù)，而b[k]=a[k]+k。奇異局勢具有以下性質(zhì)： 1、任何自然數(shù)都包含在一個(gè)且僅有一個(gè)奇異局勢中。 2、任意操作都可將奇異局勢變?yōu)榉瞧娈惥謩荨?3、采用適當(dāng)?shù)姆椒梢詫⒎瞧娈惥謩葑兂善娈惥謩荨?如果兩個(gè)人都采用正確的操作，那么面對非奇異局勢，先拿者必勝；反之，后拿者必勝。 所以真正難得是判斷一個(gè)局面他是不是一個(gè)奇異局勢。有如下公式可以證明：a[k]=[k(1+√5)/2],b[k]=a[k]+k(k=0,1,2……,n)方括號內(nèi)取整。 AC代碼： #include <iostream> #include <math.h> #include <cstdio> #include <cstdlib> using namespace std; int main() {int a,b,temp,temp2,k,i, tmp;while(scanf("%d%d",&a,&b)&&(a+b)){if(a>b)swap(a,b);k=b-a; //求出差值temp=k*(1.0+sqrt(5.0))/2.0; //求出差值對應(yīng)的開頭數(shù)if(a==temp) //奇異局勢printf("0\n");else{printf("1\n");if(abs(temp-a)==abs(temp+k-b) && temp < a){//b=a+k時(shí)可形成奇異局面，也就是說，如果一堆中取走相同數(shù)量的物品就可以形成奇異局勢的優(yōu)先輸出 printf("%d %d\n",temp,temp+k);tmp = temp;}//一堆中取if(a==0) //0 0情況，第一種奇異局勢printf("0 0\n");for(i=1;i<=b;i++) //從第二種奇異局勢開始遍歷，看取走多少石子可以滿足 {temp=i*(1.0+sqrt(5.0))/2.0; //開頭if(temp == tmp)continue;//如果是取走相同石頭，已經(jīng)輸出過了，跳過 temp2=temp+i;if(temp==a) printf("%d %d\n",a,temp2);else if(temp2==a)printf("%d %d\n",temp,a);else if(temp2==b)printf("%d %d\n",temp,b);}}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/fromzore/p/9846396.html

總結(jié)

以上是生活随笔為你收集整理的杭电acm 2177 取（2堆）石子游戏（威佐夫博弈）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。