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

    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

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 534
精华内容 213
关键字:

斐波那契博弈