斐波那契博弈(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 条评论
登录 后参与评论

相关文章

来自专栏java工会

你连java成长史都不了解,谈什么java学习技巧!

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

零基础学编程026:学什么编程语言最有前途?

(封面图来自于网络) 想学习编程的朋友可能一直纠结于到底学哪一种编程语言最有前途,我google了一下,在维基百科的下面这个页面里大概有500多种编程语言,这些...

3138
来自专栏Create Sun

设计模式------设计原则

前言: 推荐几本相关的书: (1)Head First Design Patterns 曾经买Head First系列的时候买的一本书,是java语言的案例,但...

3328
来自专栏Java3y

购物车案例【简单版】

前言 为了巩固MVC的开发模式,下面就写一个购物车的小案例.. ①构建开发环境 导入需要用到的开发包 ? 建立程序开发包 ? ---- ②设计实体 书籍实体 ...

4586
来自专栏Java学习123

什么才是Java的基础知识?

2133
来自专栏二进制文集

《代码整洁之道》

写整洁代码,需要遵循大量的小技巧,贯彻刻苦习得的“整洁感”。这种“代码感”就是关键所在。有些人生而有之。有些人费点劲才能得到。它不仅让我们看到代码的优劣,还予我...

1542
来自专栏程序工场

什么才是java的基础知识?

1356
来自专栏程序员的知识天地

用python炒股?python除了生孩子还有什么不能的!

不用深厚的数学功底也不用深厚的金融知识, 本文中也不会引用各种高深的投资模型或数学模型。这不用,那不用的,到底怎么用python炒股?往下看

1603
来自专栏架构师之路

URI设计原则,你设计的API做到了么?

咱们设计的REST API真的nice么? 优雅型:http://api.exapmle.com/louvre/da-vinci/mona-lisa 卢浮宫...

3545
来自专栏编程微刊

2018年国内就业薪资高的7大编程语言排行1. Java2.Python3.C语言4.SQL5. JavaScript6.PHP7:C++

1863

扫码关注云+社区