精华内容
下载资源
问答
  • 斐波那契博弈

    2020-09-23 16:00:44
    斐波那契博弈 1.有一堆个数为n的石子,游戏双方轮流取石子 2.先手不能在第一次把所有的石子取完; 3.之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍) 以上是典型斐波那契...

    斐波那契博弈

    1.有一堆个数为n的石子,游戏双方轮流取石子

    2.先手不能在第一次把所有的石子取完;

    3.之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)

    以上是典型斐波那契博弈的基本要求。这里以hdu2516为题贴个模板。

    
    #include "stdio.h"
    #include "iostream"
    #include "vector"
    using namespace std;
    #define N 400005
    typedef long long ll;
    int main()
    {
        ll a =2 , b =3;
        ll s;
        while (scanf("%lld",&s) && s)
        {
            int f = 0;
            while(1 )
            {
                if(a == s  || b == s )
                {
                    cout <<  "Second win" << endl;
                    f = 1;
                    break;
                }
                int m  = b;
                b = b+a;
                a = m;
                if(a > s || f == 1)
                    break;
            }
            if(f == 0 )
                cout << "First win" << endl;
        }
    }
    

    假设有F[k] 和F[k-1] ,先手在F[k-1] 中取y >= 1/3F[k-1],则后手取的为x<= 2/3F[k-1],这时我们只需要判断x2与F[k]的大小关系,若x2小于F[k],则先手一次无法取完,则会根据F[k]的规则再次失败。

    感谢大佬的博客:https://blog.csdn.net/dgq8211/article/details/7602807

    展开全文
  • Fibonacci博弈

    2017-04-04 17:29:00
    当遇见只能去f[x]里的物品时,可以看成Fibonacci博弈,用SG函数就可以求出答案来。 HDU1848 任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会陌生,它是这样定义的:F(1)=1;F(2)=2;F(n)=F(n-1)+F(n-2)...

    当遇见只能去f[x]里的物品时,可以看成Fibonacci博弈,用SG函数就可以求出答案来。

    HDU1848

    任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会陌生,它是这样定义的:
    F(1)=1;
    F(2)=2;
    F(n)=F(n-1)+F(n-2)(n>=3);
    所以,1,2,3,5,8,13……就是菲波那契数列。
    在HDOJ上有不少相关的题目,比如1005 Fibonacci again就是曾经的浙江省赛题。
    今天,又一个关于Fibonacci的题目出现了,它是一个小游戏,定义如下:
    1、  这是一个二人游戏;
    2、  一共有3堆石子,数量分别是m, n, p个;
    3、  两人轮流走;
    4、  每走一步可以选择任意一堆石子,然后取走f个;
    5、  f只能是菲波那契数列中的元素(即每次只能取1,2,3,5,8…等数量);
    6、  最先取光所有石子的人为胜者;

    假设双方都使用最优策略,请判断先手的人会赢还是后手的人会赢。
     

     

    Input
    输入数据包含多个测试用例,每个测试用例占一行,包含3个整数m,n,p(1<=m,n,p<=1000)。
    m=n=p=0则表示输入结束。
     
    Output
    如果先手的人能赢,请输出“Fibo”,否则请输出“Nacci”,每个实例的输出占一行。
     
    Sample Input
    1 1 1
    1 4 1
    0 0 0
     
    Sample Output
    Fibo
    Nacci
     1 #include <iostream>
     2 #include <cstring>
     3 #include <cstdio>
     4 using namespace std;
     5 int f[20], sg[1010], Hash[1010];
     6 
     7 void getSG(int n){
     8     memset(sg, 0, sizeof(sg));
     9     for(int i = 1; i <= n; i++){
    10         //cout << i << endl;
    11         memset(Hash, 0, sizeof(Hash));
    12         for(int j = 1; f[j] <= i; j++)
    13             Hash[sg[i-f[j]]] = 1;
    14         for(int j = 0; j <= n; j++){
    15             if(!Hash[j]){
    16                 sg[i] = j;
    17                 break;
    18             }
    19         }
    20     }
    21 }
    22 int main(){
    23     f[0] = f[1] = 1;
    24     for(int i = 2; i < 17; i++)
    25         f[i] = f[i-1] + f[i-2];
    26     getSG(1000);
    27     int n, m, p;
    28     while(cin>>n>>m>>p){
    29         if(n==0&&m==0&&p==0)break;
    30         if(sg[n]^sg[m]^sg[p])puts("Fibo");
    31         else puts("Nacci");
    32     }
    33 }

     

    转载于:https://www.cnblogs.com/xingkongyihao/p/6665563.html

    展开全文
  • fibonacci博弈

    2018-04-18 17:13:36
    有一堆个数为n的石子,游戏双方轮流取石子,满足: 1) 先手不能在第一次把所有的石子取完;...先说结论如果n是的fibonacci数,那么就是后手赢,否则是先手赢 当n=2,先手只能拿一个,后手赢。 假设f[i]为第i个fi...

    有一堆个数为n的石子,游戏双方轮流取石子,满足:

    1) 先手不能在第一次把所有的石子取完;

    2) 之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)。

    第一次取任意多个,但不能全部取完,也不能不取,问先手赢还是后手赢

    先说结论如果n是的fibonacci数,那么就是后手赢,否则是先手赢

    当n=2,先手只能拿一个,后手赢。

    假设f[i]为第i个fibonacci数

    i<=k时结论成立,即f[k-1],f[k]都是后手赢

    那么我们要证明f[k+1]=f[k-1]+f[k]的时候也是后手赢

    首先我们把f[k+1]分成两堆,f[k-1]个和f[k]个

    先考虑f[k-1]个,由于是后手赢,且x<=2*y

    那么先手一开始拿最大值y>=1/3*f[k-1]

    则后手最后一次拿最大值的x<=2/3*f[k-1]

    有fibonacci数列的性质我们知道x<=2/3*f[k-1]<1/2*f[k]

    所以后手在拿完f[k-1]个那堆时,先手并无法一次拿完f[k]个那堆

    所以后手在n=f[k+1]个时的最优策略即为先拿f[k-1]的最后一个,再拿到f[k]的最后一个

    我们再考虑先手如何在不是fibonacci数时必赢的策略

    如果不是fibonacci数,n必定有唯一分解,n=f[a1]+f[a2]+....f[at],a1<a2<at

    因为二进制是可以唯一分解的而f[k]=f[k-1]+f[k-1]<2*f[k-1],所以fibonacci数列比起2的幂次更为密集,必定可以唯一分解

    而fibonacci数列的分解也有一定的特性,它必定不是连续fibonacci数

    比如现在要分解9,优先取8,而不是3和5,那么这样5就不能被取到了。

    我们令先手先取完f[a1]即最小的一堆,根据以上性质2*f[a1]<f[a2],所以后手无法将f[a2]取完

    此时就先手就变成了n-f[a1]=f[a2]+f[a3]+...f[at]这个子游戏的后手

    那么我们由之前的后手最优策略,先手是必赢的

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,086
精华内容 1,234
关键字:

斐波那契博弈