首页 > 代码库 > GameTheory(二):Fibonacci Game(斐波那契博弈)
GameTheory(二):Fibonacci Game(斐波那契博弈)
本质描述:
有n个物品,游戏双方轮流取物品,规则为:
1.先手不能在第一次把所有的物品取完
2.之后每次可以取的物品个数为[ 1 , 2 * 对手取的数量]
轮到某人取,这个人没东西取就是输了。
结论:
当n为斐波那契数的时候,先手处于必败态
分析一下:
我们可以看到,这个博弈跟Bash Game不同,这个规则是动态的。证明这个Game要用到Zeckendorf(齐肯多夫定理):任何正整数都可以表示成若干个不连续的斐波那契数(1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55...)(不包括第一个斐波那契数)之和。我们看一下如果一个数是53的话,53位于34和55之间,显然不可能拿55去加,所以53 = 34 + 19 , 19位于13与21之间, 19 = 13 + 6 , 6位于5和8之间, 6 = 5 + 1 , 这样53 = 1 + 5 + 13 + 34.
那么,再来看一下用数学归纳法对Fibonacci Game的证明:
当n = 2,先手一定是P点
当n = 3,先手一定是P点
当n = 4,要是不想一次输,第一次只能取1,剩下3,这时候后手最多取2,所以先手一定是N点
当n = 5,如果先手取1,那么剩下4,后手就变成4情况下的先手,那么后手一定位于N点,如果取2,剩下3,那么后手能一次性取光,所以先手一定位于P点
当n = 6,如果先手取1,剩下5,后手就变成n = 5情况下的先手,所以,此时后手处于P点,如果取2,那么后手直接能赢了,所以这种情况下先手可以处于N点
所以,综上再推几个我们就可以看出当n为斐波那契数的时候,先手一定输。
我们再来用Zeckendorf(定理来看一下,如果n = 13 , 13 = 5 + 8 , 5本来就是必败态,所以13就是必败态,看n = 12, 12 = 8 + 4,那么只要我们这次取物品不超过3,必定能凑到一个N态
题目:
取石子游戏(hd2516)
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 Input
2
13
10000
0
Sample Output
Second win
Second win
First win
Solve:
典型的FIB博弈,先预处理FIB表循环找就行了
Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 int fib[52]; 4 int main() 5 { 6 int n; 7 fib[0] = 1 , fib[1] = 2; 8 for(int i = 2 ; i < 52 ; ++i) 9 fib[i] = fib[i - 1] + fib[i - 2];10 while(~scanf("%d" , &n) && n)11 {12 bool flag = 1;13 for(int i = 0 ; i < 52 ; ++i)14 {15 if(n < fib[i]) break;16 if(fib[i] == n) {flag = 0;break;}17 }18 if(flag) printf("First win\n");19 else printf("Second win\n");20 }21 }
GameTheory(二):Fibonacci Game(斐波那契博弈)