hdoj 2516 取石子游戲(斐波那契博弈)

2022-09-23 01:11:57 字數 2061 閱讀 3108

problem description

1堆石子有n個,兩人輪流取.先取者第1次可以取任意多個,但不能全部取完.以後每次取的石子數不能超過上次取子數的2倍。取完者勝.先取者負輸出"second win".先取者勝輸出"first win".

input

輸入有多組.每組第1行是2<=n<2^31.n=0退出.

output

先取者負輸出"second win". 先取者勝輸出"first win".

參看sample

output.

sample input213

10000

0sample output

second win

second win first win

有一堆總數為n的石子,遊戲雙方輪流取石子,滿足:

1)先手不能在第一次就把所有的石子取完

2)之後每次可以取的石子數介於1到對手取得石子數的兩倍之間(包含1和對手剛取的石子數兩倍)。

和巴什博弈的不同點是-->巴什博弈取石子的策略是固定的,斐波那契博弈是依賴於前者取得石子數

而斐波那契數列是解決斐波那契博弈的基礎,所以斐波那契數列是什麼咧?

fibonacci數列:f[n]:1,2,3,5,8,13,21,34,55,89……

推理得出先手勝當且僅當n不是fibonacci數。反面就是必敗就是因為構成了fibonacci數列

哲學告訴我們,事物之間都是有聯絡的,所以要解決fibonacci需要藉助"zeckendorf定理"(齊肯多夫定理)

齊肯多夫定理告訴我們任何正整數都可以表示為若干個不連續的fibonacci數之和

舉個例子

比如肢解83(^_^),83介於55,89之間,於是可以攜程83=55+28,28介於21,34之間,於是28=21+7, 7介於5,8之間,於是7=5+2;此時2,5,21,55都是fibonacci數。

來看看分解的偉大力量:若先手取2個,那麼後手不可以取5個及其以上(2,5都是fibonacc數),這樣先手可以取到5顆石子的最後一顆,根據第二類歸納法,

則先手可以取得21,55,的最後一顆,那麼先手贏。

如果n是fibonacci數,例如89,設先手一開始取得數量為x個,如果x>=34(89前兩項),那麼後手一定贏,這是第一種情況,第二種,如果x<34,那麼現在剩下的石子數y(89-x)介於55~89之間,也因此這個數一定不是fibonacci數,所以要將它拆分,y=55+f[1],[2],f[i]……f[j],如f[j]<=2x;那麼對後手就是面臨y局面的先手,所以根據之前的分析,後手只要先取個f[j],即可,以後再按照之前的分析後手就贏啦

綜上所述:如果n是fibonacci數,那麼先手輸,而巴什博弈就是判斷n%(m+1)求餘

1 #include 2

using

namespace

std;

3int

main()

14if(flag) puts("

first win

"); //處理完flag都沒變,說明n不是fibonacci數15}

16return0;

17 }

ps:摘錄

puts()函式只用來輸出字串,沒有格式控制,裡面的引數可以直接是字串或者是存放字串的字元陣列名。

printf()函式的輸出格式很多,可以根據不同格式加轉義字元,達到格式化輸出。

puts()函式的作用與語句printf("%s\n",s);的作用形同。

例子:①:

#include   

int   main(   void   )  

output  

hello   world   from   puts!  

②:main()

;puts(a);

}則輸出 hi!!燙燙燙燙燙燙燙dhaklhdwuhdaghdagdak... (後面都是亂碼)

原因: a在結尾處缺少一個空字元('\0'), 所以它不是一個串,這樣, puts() 就不知道什麼時候停止輸出, 它將會把 a 後面記憶體單元中的內容都列印出, 直到它在什麼地方碰到了一個空字元為止

HDU 2516 取石子游戲 (斐波那契博弈)

1堆石子有n個 兩人輪流取 先取者第1次可以取任意多個,但不能全部取完 以後每次取的石子數不能超過上次取子數的2倍。取完者勝 先取者負輸出...

取石子游戲 HDU2516(斐波那契博弈)

題目 problem description 1堆石子有n個 兩人輪流取 先取者第1次可以取任意多個,但不能全部取完 以後每次取的石子數不能超過上次取子數的2倍。取完者勝 先取者負輸出 second win 先取者勝輸出 first win input 輸入有多組 每組第1行是2 n 2 31 n ...

斐波那契博弈

處理何種問題 有一堆個數為n的石子,遊戲雙方輪流取石子,滿足 1 先手不能在第一次把所有的石子取完,且最少取1個 2 之後每次可以取得石子數...