python博弈論_博弈論 威佐夫博奕嗚

有兩堆石子，數量任意，可以不同。遊戲開始由兩個人輪流取石子。遊戲規定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數量的石子。最後把石子全部取完者為勝者。現在給出初始的兩堆石子的數目，如果輪到你先取，假設雙方都采取最好的政策，問最後你是勝者還是敗者。

Input

輸入包含若幹行，表示若幹種石子的初始情況，其中每一行包含兩個非負整數a和b，表示兩堆石子的數目，a和b都不大于1,000,000,000。

Output

輸出對應也有若幹行，每行包含一個數字1或0，如果最後你是勝者，則為1，反之，則為0。

Sample Input

2 1

8 4

4 7

Sample Output

1

經典的威佐夫博奕詳細介紹左轉參考大佬的網址

定義奇異局勢 (a[k],b[k])面對奇異局勢就會輸 a[k]

(0 0)，(1 2)，(3 5)···也就是新的奇異局勢 是前面沒出現過的最小整數且b[k]=a[k]+k,而且 每個非零整數在奇異局勢中一定存在且隻有一次出現機會 任何非零整數 都包含在一個有且 僅有一個 奇異局勢 中 是以有以下性質

1 任何操左都會使奇異局勢變為非奇異局勢 我感覺這個其實是巴什博弈的擴充？ 證明 由于每次隻能拿一堆 或 兩堆拿同樣數量的石子 每一個奇異局勢都是由順序産生的 a[k]>a[k-1] b[k]=a[k]+k>a[k-1]+k-1=b[k-1],b[k]-b[k-1]與a[k]-a[k-1]作比較 前者比後者多一以此類推 同時拿同樣個數的石子一定不能得到奇異局勢 由于每個非零整數 都包含在一個有且 僅有一個 奇異局勢 中 不可能從一堆裡拿出任意的石子 變為另一個奇異局勢

2.采用最好的推理判斷 可以将非奇異局勢變為奇異局勢

面對局勢 (a，b))(前提a<=b) a=b 直接全部拿走 當a=a[k] 1. b>b[k] 隻需要b-(b-b[k]) 2.b

a[k] 隻需要a-(a-a[k]) 2.a 3.奇異局勢b[k]-a[k]的值表示第幾個奇異局勢 。 這裡我簡要說一下最難的部分是找n和m是不是奇異局勢 解題關鍵 判斷(n m)是不是奇異局勢 可以假設 abs(m-n)是第(m-n)個奇異局勢那麼min(a，b)=a[abs(m-n)] 判斷一下即可 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long using namespace std; int main() { int n,m; while(scanf("%d %d",&n,&m)!=EOF) { int k=abs(n-m); n=n int ok= floor(k*(1+sqrt(5.0))/2); printf("%d\n",ok!=n); } return 0; } 本文位址：https://blog.csdn.net/qq_45827278/article/details/107881196 如您對本文有疑問或者有任何想說的，請點選進行留言回複，萬千網友為您解惑！