斐波那契博弈(fibonacci Game)

简述

一堆石子有n个,两人轮流取,先取者第一次可以取任意多个,但不能全部取完,以后每次取石子的数目不能超过上次取子数的2倍,先取完者胜

分析

这个游戏叫做Fibonacci Game,肯定和Fibonacci数列f[n]:1,1,2,3,5,8,13,21,34,55,89,…有密切关系,结论:先手胜,当且仅当n不是fibonacci数列

证明过程有点复杂,建议看这篇文章

那么当n不是斐波那契数列的时候,先手应该如何拿,才能胜呢?这里涉及到一个定理:任何正整数可以表示为若干个不连续的Fibonacci数之和,比方说分解50,注意到50夹在34和55之间,于是50可以写成50=34+16,然后再分解16,16被夹在13和21之间,于是16可以写成16=13+3,所以50可以分解成50=34+13+3

如果n不是fibonacci数,我们首先将n表示为$n = f[a_1] + f[a_2] + f[a_3]+…+f[a_{p-1}]+f[a_p]$,对于50就是50=34+13+3。那么。我们令先手先取$f[a_p]$个石子,即最少的3,此时后手只能取13这一堆,且不能一次性取完,因为题目限定不能超过上次的两倍,即在这里不能超过6,此时对手相当于面对这个游戏的子游戏(只有$f[a_{p-1}]$,且后手先取)的必败态,即先手一定可以取到这一堆的最后一颗石子。同理可知,对于以后的每一堆,先手都可以取到这一堆的最后一颗,从而获得游戏胜利

例题

1.HDU2516取石子游戏

思路:先用递推求出一系列fibonacci数,然后用输入跟这些fibonacci数一个一个比对,如果是fibonacci数,则后手胜,否则前者胜

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    int f[50] = {1,2};
    for(int i = 2;i < 50;i++)
        f[i] = f[i-1] + f[i-2];
    while(cin>>n&&n)
    {
        int cnt;
        for(cnt = 0;cnt < 50;cnt++)
            if(f[cnt] == n)
                break;
        if(cnt == 50)
            cout<<"First win"<<endl;
        else
            cout<<"Second win"<<endl;
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏章鱼的慢慢技术路

2014年第五届蓝桥杯C/C++B组省赛题目解析

1604
来自专栏ACM算法日常

5行位运算,map靠边站——位操作进阶

Given an array of integers, every element appears three times except for one. F...

551
来自专栏数据结构与算法

NOIP复习内容

https://www.luogu.org/problemnew/lists?name=GSS&orderitem=pid&tag=&content=0&typ...

962
来自专栏海天一树

NOIP 2011初赛普及组C/C++答案详解

3 C 8G = 8 * 1024 M 8 * 1024 / 2 = 4096张 注意,题目说的是“大约”,不要求精确。

932
来自专栏算法与数据结构

PTA 数据结构 银行业务队列简单模拟

仅供参考,请勿粘贴 设某银行有A、B两个业务窗口,且处理业务的速度不一样,其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时,B窗口处理完1个...

1838
来自专栏专知

【关关的刷题日记59】Leetcode 257 Binary Tree Paths

关关的刷题日记59 – Leetcode 257 Binary Tree Paths 题目 ? 题目要求我们给出所有根节点到叶子节点的路径。 思路 思路:求一棵...

3327
来自专栏申龙斌的程序人生

参加steemit数学x程式大赛(第八回)

前一段时间参加了Steemit社区的两个活动,比如“接龙”创作大赛,五个人根据几张图片素材编出一篇小说,事先没有任何沟通,人员报名之后,顺序是随机指定的,我第一...

2946
来自专栏数据结构与算法

P1603 斯诺登的密码

题目背景 根据斯诺登事件出的一道水题 题目描述 题目描述 2013年X月X日,俄罗斯办理了斯诺登的护照,于是他混迹于一架开往委内瑞拉的飞机。但是,这件事情太不周...

3518
来自专栏take time, save time

Think in 递归

     网上写递归的文章可以用汗牛充栋来形容了,大多数都非常清晰而又细致的角度上讲解了递归的概念,原理等等。以前学生的时候,递归可以说一直是我的某种死穴,原理...

39912
来自专栏章鱼的慢慢技术路

今日头条2018校园春季招聘研发岗位笔试(第一场)经验

993

扫码关注云+社区