数的不同递增求和项分解计数递归程序的错误修正求助

问题分析 #

你的需求是统计将一个数分解为至少两个不同递增正整数之和的方式数，比如n=6时有3种分解方式（1+2+3、2+4、1+5）。当前程序在n=4时输出错误，核心问题在于Main函数的条件判断逻辑错误，且未排除单个数字的无效分解情况。

错误原因 #

1. Main函数中针对不同n范围的分支判断完全多余且逻辑错误：比如n=4时，程序调用CountStairs(3,1)，得到的结果和n=4的分解需求无关，导致输出错误。
2. 递归函数CountStairs会将单个数字本身算作一种分解情况（比如n=4时，会包含“4”这一项），但我们需要的是至少两个数的组合，因此需要排除这种无效情况。

修正后的代码 #

using System;

namespace Stairs
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Enter the number of cubes: ");
            int n = int.Parse(Console.ReadLine());

            int count = 0;
            if (n >= 3)
            {
                // 调用递归后减去单个数字的无效情况
                count = CountStairs(n, 1) - 1;
            }

            Console.WriteLine("Number of different staircases: " + count);
        }

        static int CountStairs(int n, int min)
        {
            if (n == 0)
            {
                return 1;
            }

            int count = 0;

            // 从min开始遍历，保证分解项严格递增
            for (int i = min; i <= n; i++)
            {
                count += CountStairs(n - i, i + 1);
            }

            return count;
        }
    }
}

修正说明 #

• 移除了Main函数中多余的分支判断，统一处理逻辑：当n≥3时，调用递归函数后减1（排除单个数字的无效分解）；n<3时直接返回0，因为无法分解为至少两个不同正整数。
• 递归函数CountStairs的核心逻辑正确，它计算了将n分解为若干个≥min的递增正整数之和的所有方式（包括单个数字），减去1即可得到符合需求的有效分解数。

测试验证 #

• n=3：CountStairs(3,1)返回2（1+2、3），减1后得到1，正确。
• n=4：CountStairs(4,1)返回2（1+3、4），减1后得到1，正确。
• n=6：CountStairs(6,1)返回4（1+2+3、2+4、1+5、6），减1后得到3，符合预期。

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