每日算法 — 使用java实现斐波那契博弈：Zeckendorf分解与贪心最优取子策略

一、游戏规则与数学背景

斐波那契博弈（Fibonacci Nim）是组合博弈论中的经典模型，规则如下：
– 初始有 N 枚石子
– 先手玩家第一次可以取 1 到 N-1 枚石子（不能全取）
– 之后每位玩家取的石子数不能超过上一位玩家取的石子数的 2 倍
– 取走最后一颗石子的人获胜

核心定理（Zeckendorf 定理）：任何正整数都可以唯一地表示为若干个不连续的斐波那契数之和。基于这一定理，可以严格证明：当且仅当 N 是斐波那契数时，先手处于必败态（P-position）。

二、Zeckendorf 分解算法

import java.util.*;

/**
 * 斐波那契博弈求解器
 * 基于 Zeckendorf 分解与贪心策略实现必胜决策
 */
public class FibonacciNim {

    // 预计算斐波那契数列（足够覆盖 int 范围）
    private static final List<Integer> FIB = new ArrayList<>();
    static {
        FIB.add(1); // F(1)
        FIB.add(2); // F(2) = 2（博弈论中常用 1,2,3,5... 而非 1,1,2,3...）
        while (true) {
            int next = FIB.get(FIB.size() - 1) + FIB.get(FIB.size() - 2);
            if (next < 0) break; // 溢出停止
            FIB.add(next);
        }
    }

    /**
     * 获取斐波那契数列列表
     */
    public static List<Integer> getFibonacciList() {
        return new ArrayList<>(FIB);
    }

    /**
     * Zeckendorf 分解：将 n 分解为不连续斐波那契数之和
     * 贪心策略：每次取不超过 n 的最大斐波那契数
     * @return 分解后的斐波那契数列表（从大到小）
     */
    public static List<Integer> zeckendorfDecomposition(int n) {
        if (n <= 0) return Collections.emptyList();
        List<Integer> result = new ArrayList<>();
        int remaining = n;
        // 从大到小遍历斐波那契数
        for (int i = FIB.size() - 1; i >= 0; i--) {
            int fib = FIB.get(i);
            if (fib <= remaining) {
                result.add(fib);
                remaining -= fib;
                // 跳过相邻的斐波那契数（Zeckendorf 定理保证不连续）
                i--; // 跳过下一个较小的（因为不能连续）
            }
        }
        return result;
    }

    /**
     * 判断 n 是否为斐波那契数
     */
    public static boolean isFibonacci(int n) {
        return Collections.binarySearch(FIB, n) >= 0;
    }

三、必败态判定与最优策略

    /**
     * 判断当前状态是否为必败态（P-position）
     * 当剩余石子数是斐波那契数时，当前行动方必败（在双方最优策略下）
     */
    public static boolean isLosingPosition(int remaining) {
        return isFibonacci(remaining);
    }

    /**
     * 计算当前最优取子数
     * 策略：
     * 1. 对剩余石子做 Zeckendorf 分解
     * 2. 取走分解中最小的斐波那契数
     * 3. 确保取子数不超过上家取子数的 2 倍
     *
     * @param remaining 剩余石子数
     * @param lastTaken 上家取的石子数（第一次为 0，表示无限制）
     * @return 最优取子数，如果无法行动返回 -1
     */
    public static int optimalMove(int remaining, int lastTaken) {
        if (remaining <= 0) return -1;

        // 第一次行动的特殊规则：不能全取
        if (lastTaken == 0) {
            if (remaining == 1) return -1; // 只剩1个且第一次，无法行动
            // 对剩余-1做 Zeckendorf 分解，取最小项
            List<Integer> decomp = zeckendorfDecomposition(remaining);
            int take = decomp.get(decomp.size() - 1); // 最小项
            // 第一次不能全取，且至少取1
            if (take >= remaining) take = remaining - 1;
            return Math.max(1, take);
        }

        // 常规回合：取子数 <= 2 * lastTaken
        int maxTake = Math.min(2 * lastTaken, remaining);

        // Zeckendorf 分解
        List<Integer> decomp = zeckendorfDecomposition(remaining);
        int smallestFib = decomp.get(decomp.size() - 1);

        if (smallestFib <= maxTake) {
            return smallestFib;
        }

        // 如果最小斐波那契数超过限制，则取 maxTake（被迫）
        // 这种情况通常意味着我们已经处于不利局面
        return maxTake;
    }

四、完整游戏模拟引擎

    /**
     * 游戏状态类
     */
    public static class GameState {
        int remaining;   // 剩余石子
        int lastTaken;   // 上一步取的石子数（0表示第一步）
        int currentPlayer; // 1 or 2

        public GameState(int n) {
            this.remaining = n;
            this.lastTaken = 0;
            this.currentPlayer = 1;
        }

        public GameState copy() {
            GameState gs = new GameState(this.remaining);
            gs.lastTaken = this.lastTaken;
            gs.currentPlayer = this.currentPlayer;
            return gs;
        }
    }

    /**
     * 执行一步移动
     * @return 是否成功
     */
    public static boolean makeMove(GameState state, int take) {
        if (take <= 0) return false;
        if (take > state.remaining) return false;
        if (state.lastTaken > 0 && take > 2 * state.lastTaken) return false;
        if (state.lastTaken == 0 && take >= state.remaining && state.remaining > 1) return false;

        state.remaining -= take;
        state.lastTaken = take;
        state.currentPlayer = (state.currentPlayer == 1) ? 2 : 1;
        return true;
    }

    /**
     * AI 决策：使用贪心最优策略
     */
    public static int aiMove(GameState state) {
        return optimalMove(state.remaining, state.lastTaken);
    }

    /**
     * 运行一场完整的斐波那契博弈
     * @param n 初始石子数
     * @param aiPlayer 哪个玩家由 AI 控制（1或2），0表示双方都是 AI
     */
    public static void playGame(int n, int aiPlayer) {
        GameState state = new GameState(n);
        Scanner scanner = new Scanner(System.in);

        System.out.println("=== 斐波那契博弈开始 ===");
        System.out.println("初始石子: " + n);
        System.out.println("规则：首次不能全取，之后每次最多取上家2倍");

        while (state.remaining > 0) {
            System.out.println("
剩余石子: " + state.remaining);
            System.out.println("上家取了: " + state.lastTaken);
            System.out.println("当前玩家: " + state.currentPlayer);

            int take;
            if (aiPlayer == 0 || state.currentPlayer == aiPlayer) {
                take = aiMove(state);
                System.out.println("AI 决策: 取 " + take + " 枚");
            } else {
                System.out.print("请输入取子数: ");
                take = scanner.nextInt();
            }

            if (!makeMove(state, take)) {
                System.out.println("非法移动！");
                continue;
            }
        }

        int winner = (state.currentPlayer == 1) ? 2 : 1;
        System.out.println("
游戏结束！玩家 " + winner + " 获胜！");
    }

五、数学正确性验证

    /**
     * 验证 Zeckendorf 分解的正确性：
     * 1. 分解结果之和等于原数
     * 2. 分解结果中没有相邻的斐波那契数
     */
    public static boolean verifyZeckendorf(int n) {
        List<Integer> decomp = zeckendorfDecomposition(n);
        int sum = decomp.stream().mapToInt(Integer::intValue).sum();
        if (sum != n) {
            System.out.println("和错误: " + sum + " != " + n);
            return false;
        }
        // 检查不连续
        for (int i = 0; i < decomp.size() - 1; i++) {
            int idx1 = Collections.binarySearch(FIB, decomp.get(i));
            int idx2 = Collections.binarySearch(FIB, decomp.get(i + 1));
            if (Math.abs(idx1 - idx2) == 1) {
                System.out.println("相邻错误: F(" + idx1 + ") 和 F(" + idx2 + ")");
                return false;
            }
        }
        return true;
    }

    /**
     * 批量测试 Zeckendorf 分解
     */
    public static void runTests() {
        System.out.println("=== 测试 Zeckendorf 分解 ===");
        boolean allPass = true;
        for (int i = 1; i <= 1000; i++) {
            if (!verifyZeckendorf(i)) {
                allPass = false;
                System.out.println("失败: " + i);
                break;
            }
        }
        if (allPass) {
            System.out.println("1-1000 全部通过！");
        }

        System.out.println("
=== 示例分解 ===");
        int[] samples = {10, 20, 50, 100, 1000};
        for (int s : samples) {
            System.out.println(s + " = " + zeckendorfDecomposition(s));
        }
    }

六、主程序

    public static void main(String[] args) {
        // 先运行测试
        runTests();

        // 运行 AI 对战
        System.out.println("
=== AI 自我对战 ===");
        playGame(30, 0);
    }
}

七、算法复杂度与策略分析

策略证明要点：
1. 若 N = F(k) 是斐波那契数，任何合法取子都会使剩余 N’ < F(k)。由于不能取超过 2×lastTaken，对手总能通过 Zeckendorf 分解将局面恢复为斐波那契数。
2. 若 N 不是斐波那契数，取走 Zeckendorf 分解的最小项后，剩余恰好是斐波那契数，将对手送入必败态。

斐波那契博弈完美展示了数论性质如何转化为确定性博弈策略，是组合博弈论入门的经典范例。