1.斐波那契博弈是另种类型的博弈,这种博弈要求的条件是(1):博弈者还是两个人,n个物品(2)先手在第一次不能取完所有的物品,但是至少取走一个物品。(3)以后的每一个回合,每次取走的物品至多是上一个人的两倍,至少是一个。(4)先取完的人胜利。
2.同理,我们在这里还是要研究先手的必胜和必败态。在斐波那契博弈中,先手的必败态是:当物品的数量n是一个斐波那契数的时候,先手必败。至于证明,有点复杂,就不再证明。但是我想说明的是一个定理:Zeckendorf定理(齐肯多夫定理):任何正整数可以表示为若干个不连续的Fibonacci数之和。这是一个很重要的定理,分解的过程使用贪心思想,尽量选大的。下面给出一个HDU上的例子:斐波那契博弈。
下面是代码:
#include"stdafx.h"
#include<iostream>
#pragma warning(disable:4996)
#define ll long long
const int maxn = 1e4;
ll tem[maxn];
void init()
{
tem[0] = 1;
tem[1] = 1;
for (int i = 2; i < 100; i++)
{
tem[i] = tem[i - 1] + tem[i - 2];
}
}
using namespace std;
int main()
{
init();
int n;
while (scanf("%d", &n) && n)
{
int flag = 0;
for (int i = 0; i < 200; i++)
{
if (n == tem[i])
{
flag = 1;
}
}
if (flag)
{
printf("Second winn");
}
else
{
printf("First winn");
}
}
return 0;
}
最后
以上就是细腻水杯最近收集整理的关于博弈论-斐波那契博弈的全部内容,更多相关博弈论-斐波那契博弈内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复