【算法】经典博弈论问题——斐波那契博弈 + Zeckendorf 定理 python

斐波那契博弈（Fibonacci Nim）

先说结论：当初始石子数目 n 是斐波那契数时，先手必败；否则，先手有策略获胜。

证明概要:
当n=2时，先手只能取1颗石子，后手直接取剩下的1颗石子获胜，因此先手必败。
假设对于所有小于等于某个斐波那契数 f[k]的情况，结论都成立。
归纳：
对于f[k+1]=f[k]+f[k-1]的情况，可以把这一堆石子看成两堆，分别有f[k]和[k-1]颗石子。
根据归纳假设，无论先手怎么取，后手总能取到最后一个石子。
特别地，如果先手取的石子数大于等于f[k-1],则后手可以直接取完f[k],因为f[k]<2*f[k-1]。

齐肯多夫（Zeckendorf）定理

任何正整数都可以表示成若干个不连续的斐波那契数之和。

~~证明略~~

非斐波那契数的情况：
使用齐肯多夫定理(Zeckendorf’s theorem),任何正整数可以表示为若干个不连续的斐波那契数之和。
将n分解为若干个不连续的斐波那契数之和，然后通过适当的策略让先手每次都能取到最后一颗石子，从而获胜。

示例分析

假设有一个 n=85 的石子堆，我们首先将85分解为斐波那契数之和：
85 = 55 + 30
30 = 21 + 9
9 = 8 + 1
所以，85=55+21+8+1。

根据上述结论，先手可以通过以下策略获胜：
1.先手先取1颗石子，剩下84颗。
2.因为84不是斐波那契数，后手无法直接应用斐波那契博弈的必败态。
3.接下来，先手可以根据后手的动作，逐步减少石子数，并确保每次后手面对的是非斐波那契数，最终达到胜利。

实战演练

[COCI 2010/2011 #4] HRPA https://www.luogu.com.cn/problem/P6487

题目描述

有 $n$ 枚石子。两位玩家定了如下规则进行游戏：

Mirko 先取一次，Slavko 再取一次，然后 Mirko 再取一次，两人轮流取石子，以此类推；
Mirko 在第一次取石子时可以取走任意多个；
接下来，每次至少要取走一个石子，最多取走上一次取的数量的 $2$ 倍。当然，玩家取走的数量必须不大于目前场上剩余的石子数量。
取走最后一块石子的玩家获胜。

双方都以最优策略取石子。Mirko 想知道，自己第一次至少要取走几颗石子最终才能够获胜。

输入格式

输入一行一个整数 $n$ ，表示石子的数量。

输出格式

输出一行一个整数，表示 Mirko 最少取多少石子可以保证获胜。

样例输入 #1

样例输出 #1

样例输入 #2

样例输出 #2

样例输入 #3

样例输出 #3

提示

样例 1 解释

对于这个样例，Mirko 第一次可以取 $1/2/3/4$ 个。虽然他取 $4$ 个会直接赢得比赛，但这并不是最少的。最少的方案是取走 $1$ 个。这样 Slavko 只能取走 $1$ 个或者 $2$ 个。无论选择哪种，Mirko 下一步都能取走所有的石子并获胜。

数据规模与约定

对于 $100\%$ 的数据，保证 $2\le n\le 10^{15}$ 。

说明

题目译自 COCI2010-2011 CONTEST #4 T6 HRPA。

题解code：

python">n = int(input())def solve(n):if n == 1:return 1if n == 2:return 2a, b = 1, 2  # 初始化前两个斐波那契数while True:c = a + b  # 计算下一个斐波那契数if c == n:return n  # 当前n是斐波那契数，先手必败elif c > n:break  # 当前c大于n，退出循环a, b = b, c  # 更新a和b为下一个斐波那契数# 当前n不是斐波那契数，减去b并继续判断return solve(n - b)print(solve(n))