533
zoj 2290 GAME 博弈
轉的 一篇非常好的分析 https://www.stubc.com/thread-3747-1-1.html
A必輸的情形形成菲波那契數列。
顯然，2和3是A必輸的情形。現在，設a和a[i+1]是連續兩個A必輸的狀態，則a[i+2]=a
+a[i+1]也是A必輸的狀態。因為，根據菲波那契數列的特點，A不能一次取a個以上
（含a個），否則，因為a[i+1]<2*a，B可以一次把剩下的全取完(不超過a[i+1]塊）。
剩下的問題就是，B能否在留下a[i+1]塊stones的同時，保證A不能一次性拿完剩下的所有
stones。如果成立的話，這就回到了a[i+1]的狀態。我們假設，對於a塊stones，B可以
保證最後一把不會超過a[i-1]（2和3時都成立），而a[i+1]（=a+a[i-1]）>2*a[i-1]。
這就保證了剩下的a[i+1]塊石頭不會被A一次取完。注意到這時，B最後一把不會超過a[i+
1],其實也就歸納的證明了剛才的假設。
上述的證明其實也提示了A贏的情況下的策略。這也是一個遞歸的結果。設有n（n不是菲波
那契數）塊stones，離它最近而比它小的菲波那契數是a。A拿掉n-a塊後，留下a塊給B先拿
，A就贏了。令n=n-a。若n是菲波那契數，則A必須一次性取n塊。否則，重複上麵過程，直
到n為菲波那契數（包括1）為止。
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int fib[45];
int is_that(int re)
{
int i=0;
while(fib[i]<re)i++;
if(fib[i]==re)return re;
else return is_that(re-fib[i-1]);
}
int main()
{
int i;
fib[0]=1;fib[1]=1;
for(i=2;i<45;i++)
fib[i]=fib[i-1]+fib[i-2];
int n;
while(~scanf("%d",&n))
{
i=0;
while(fib[i]<n)i++;
if(fib[i]==n)puts("lose");
else printf("%d\n",is_that(n-fib[i-1]));
}
}
最後更新：2017-04-03 14:53:53