博弈論入門之斐波那契博弈

斐波那契博弈

斐波那契博弈是一種經典的博弈問題

有一堆石子，兩個頂尖聰明的人玩遊戲，先取者可以取走任意多個，但不能全取完，以後每人取的石子數不能超過上個人的兩倍

結論

斐波那契博弈有一個非常重要的性質：

先手必敗，當且僅當石子數為

斐波那契數

是不是很神奇？？

證明：

懶得看了，這裡有

代碼

HDU 2516

#include<cstdio>
#include<map>
int fib[233],x;
std::map<int,bool>mp;
int main()
{
	fib[1]=1;fib[2]=1;
	for(int i=3;i<=50;i++) fib[i]=fib[i-1]+fib[i-2],mp[fib[i]]=1;
	while(scanf("%d",&x)&&x!=0)
		puts(mp[x]==1?"Second win":"First win");
    return 0;
}

           

作者：自為風月馬前卒

個人部落格http://attack204.com//

出處：http://zwfymqz.cnblogs.com/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。