首页 > 代码库 > HDU 2516 取石子游戏 斐波纳契博弈
HDU 2516 取石子游戏 斐波纳契博弈
斐波纳契博弈:
有一堆个数为n的石子,游戏双方轮流取石子,满足:
1)先手不能在第一次把所有的石子取完;
2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)。
约定取走最后一个石子的人为赢家,求必败态。
证明 FBI数为必败局:
1.对于任意一个FBI数 FBI[K]=FBI[K-1]+FBI[K-2],我们可以将FBI[K]看成石子数目分别是FBI[K-1],FBI[K-2]的两堆(一定可以这样分,因为FBI[K-1] > FBI[K-2]*2,若先手取的数目大于等于FBI[K-2],则后手可以一次拿完)
2.将FBI[K-2],FBI[K-1],再次拆分,无论先手如何取,后手总能取走最后一个石子
证明 非FBI数为必胜局:
1.由齐肯多夫定理知道,任意一个整数,可以被拆分成几个不连续的FBI数相加的形式:n=FBI(ak)+FBI(ak-1)+FBI(ak-2)+……+FBI(a1)
2.因为式子中的FBI数不连续,所以FBI(a) > 2FBI(a-1)
3.先手取走FBI(a1)个石子,那么后手只能在FBI(a1+1)堆中取,且不能一次性取完。依旧是说对于任意一堆,总是先手取走最后一个石子!
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<iostream> #include<algorithm> #define INF 0x3f3f3f3f #define MAXSIZE 100005 using namespace std; int fib[MAXSIZE]; int Game(int n) { for(int i=1;i<=46;i++) { if(fib[i]==n) return 0; } return 1; } int main() { int n; fib[1]=1; for(int i=2;i<=46;i++) fib[i]=fib[i-1]+fib[i-2]; while(scanf("%d",&n),n) { int op=Game(n); if(op==0) printf("Second win\n"); else printf("First win\n"); } return 0; }
HDU 2516 取石子游戏 斐波纳契博弈
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。