如何修改Java程序输出无相邻1的二进制组合数量而非组合本身？

方式一：修改原有生成程序统计总数 #

如果你的原有程序是通过回溯/枚举生成符合条件的二进制串，只需把输出具体组合的逻辑改成计数即可，无需存储或打印串内容：

import java.util.Scanner;

public class NoAdjacentOnesCounter {
    private static int count = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入二进制位数：");
        int n = scanner.nextInt();
        backtrack(n, 0, false);
        System.out.println("符合条件的组合总数：" + count);
        scanner.close();
    }

    // prevIsOne 标记上一位是否为1
    private static void backtrack(int n, int pos, boolean prevIsOne) {
        if (pos == n) {
            count++; // 仅计数，不再输出具体组合
            return;
        }
        // 尝试当前位放0，无论上一位是什么都允许
        backtrack(n, pos + 1, false);
        // 尝试当前位放1，仅当且仅当上一位不是1时允许
        if (!prevIsOne) {
            backtrack(n, pos + 1, true);
        }
    }
}

运行示例：输入3，输出符合条件的组合总数：5。

方式二：动态规划直接计算（高效适配大位数） #

当位数较大时（比如n=100），枚举会出现性能瓶颈，用动态规划公式直接计算更高效：

• 设dp[i]表示i位二进制数中符合条件的组合总数
• 递推逻辑：
  • 若第i位是0，前i-1位所有符合条件的组合都可直接拼接，对应dp[i-1]
  • 若第i位是1，前i-1位必须是0，等价于前i-2位的组合拼接01，对应dp[i-2]
• 递推公式：dp[i] = dp[i-1] + dp[i-2]
• 初始条件：
  • dp[1] = 2（0、1）
  • dp[2] = 3（00、01、10）

对应的Java代码：

import java.util.Scanner;

public class NoAdjacentOnesCounter {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入二进制位数：");
        int n = scanner.nextInt();
        if (n <= 0) {
            System.out.println("请输入正整数");
            return;
        }
        if (n == 1) {
            System.out.println(2);
            return;
        }
        // 若n过大（比如超过100），可将int替换为long避免溢出
        int[] dp = new int[n + 1];
        dp[1] = 2;
        dp[2] = 3;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        System.out.println("符合条件的组合总数：" + dp[n]);
        scanner.close();
    }
}

内容的提问来源于stack exchange，提问作者user20868173