hdu-2516 斐波那契数sg值

灰太狼 2022-08-12 01:59 7阅读 0赞

不管怎样，我是先写出了前十个数的情况。

发现2，3，5，8是必败态，因此猜想凡是n的值为 斐波那契数就是先手的必败态，否则为胜态。

猜想完成当然要验证了，接下来

先证：n为斐波那契额数时，先手必败

当n=2时，先手必败；

当n=3时，先手必败；

假设n=fib\[k-1\]时，先手必败；

假设n=fib\[k-2\]时，先手必败；

那么，

当n=fib\[k\]=fib\[k-1\]+fib\[k-2\];

因为fib\[k-1\]<2\*fib\[k-2\];

所以不可能先手第一次取超过fab\[k-2\]的棋子；

这就回归到了fib\[k-2\]必败的问题。

显然这样操作先手必败，证毕；

再证n=非斐波那契数是必胜态；

由于“任一个正整数都可拆分为不连续的斐波那契额数之和”（[Zeckendorf's theorem][Zeckendorf_s theorem]）

以n=20为例：n=13+5+2；

此时我可以取2，而对手至多可以取4，既让对手面临5的必败态，然后再让对手面临13的必败态；

其它整数证明类似；

即：n=f\[a\]+f\[b\]+...(已按从小到大排列）

先手取f\[a\],因为2\*f\[a\]<f\[b\]（a，b，不连续），故转变成了让后手面临斐波那契数组成的必败态。

证毕；

跳转[http://yjq24.blogbus.com/logs/46150651.html][http_yjq24.blogbus.com_logs_46150651.html]

#include <cstdio>
    
    int fib[50]={0,1,1};
    
    int main (){
    	int n;
    	for(int i=3;i<=46;i++)//2^31之内只有46个fibonacci
    	fib[i]=fab[i-1]+fab[i-2];
    	while(scanf("%d",&n)&&n){
    		int sign=1;
    		for(int i=1;fib[i]<=n;i++)
    			if(fib[i]==n){
    				printf("Second win\n");sign=0;
    			}
    			if(sign)printf("First win\n");
    	}
    	return 0;
    }

[Zeckendorf_s theorem]: http://en.wikipedia.org/wiki/Zeckendorf%27s_theorem
[http_yjq24.blogbus.com_logs_46150651.html]: http://yjq24.blogbus.com/logs/46150651.html

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu 2516 取石子游戏（斐波那契博弈）

取石子游戏 Problem Description 1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上

快来打我*/ 2024年02月17日 20:50/ 0 赞/ 75 阅读

相关 509. 斐波那契数

509. 斐波那契数题干描述动态规划五部曲 1. 确定dp数组以及下标的含义 2. 确定递推公式 3. dp数组如

朴灿烈づ我的快乐病毒、/ 2023年10月16日 15:50/ 0 赞/ 66 阅读

相关斐波那契数

1、用java代码去计算 / @Title:斐波那契数(这个数列从第3项开始，每一项都等于前两项之和) @Author: longzhou

た入场券/ 2023年06月15日 13:29/ 0 赞/ 63 阅读

相关 509. 斐波那契数

参考： [面试题10- I. 斐波那契数列][10- I.] [10- I.]: https://blog.csdn.net/zyx_ly/article/detai

朴灿烈づ我的快乐病毒、/ 2022年12月12日 02:18/ 0 赞/ 218 阅读

相关 509. 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) =

太过爱你忘了你带给我的痛/ 2022年10月07日 07:50/ 0 赞/ 224 阅读

相关 hdu-2516 斐波那契数sg值

不管怎样，我是先写出了前十个数的情况。发现2，3，5，8是必败态，因此猜想凡是n的值为斐波那契数就是先手的必败态，否则为胜态。猜想完成当然要验证了，接下来先证：n

灰太狼/ 2022年08月12日 01:59/ 0 赞/ 8 阅读

相关 HDU 2516-取石子游戏（斐波那契博弈）

取石子游戏 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

小灰灰/ 2022年07月24日 03:27/ 0 赞/ 224 阅读

相关斐波那契数

> 牛客网《剑指offer》时间限制：`1秒` 空间限制：`32768K` 热度指数：`199742` 解题思路一：如果像这样，将会有大量的计算是重复的，时空

╰+哭是因爲堅強的太久メ/ 2022年06月08日 02:46/ 0 赞/ 226 阅读

相关大斐波那契数

斐波那契数计算公式 : f(n)=f(n-1)+f(n-2) (n>=3) f(1)=1 f(2)=1 对于 n 比较小的情况下，下边的程序就可以实现这个功能

妖狐艹你老母/ 2022年05月26日 02:47/ 0 赞/ 262 阅读

相关 golang 斐波那契数

golang 斐波那契数 package main import "fmt" / 斐波那契数，亦称之为斐波

短命女/ 2021年11月02日 02:02/ 0 赞/ 347 阅读