斐波那契博弈
两个顶尖聪明的人在玩游戏，有一堆石子，先手第一次可以拿任意多个但不能全拿走也不能不拿，之后每个人最少拿一个，最多拿前一个人两倍那么多个，谁取到最后一个谁就能获胜，请问先手后手谁必胜？
齐肯多夫定理 任何正整数都可以表示成若干个不连续的斐波那契数之和。
构造这种和式可以通过每次贪心选出最大的不超过它的斐波那契数。
斐波那契博弈先手必胜取的最小石子数为齐肯多夫表示下的最小斐波那契数
结论：当石子数为斐波那契数时先手必败，反之先手必胜。
Skip to content