C语言递归实现正整数拆分组合 - 算法详解及代码示例

C语言递归实现正整数拆分组合 - 算法详解及代码示例

问题描述： 给定一个正整数n (2 <= n <= 10)，使用递归算法求该数的所有不同拆分组合。要求拆分组合不能重复，例如 2+4 和 4+2 被视为重复。

输入格式： 输入一个正整数n (2 <= n <= 10)

输出格式： 输出所有不同的拆分组合，其中被拆分的数据按从大到小的顺序输出。输出的所有符号中间不存在空格，每一种拆分按一行输出。

输入样例： 6

输出样例： 6=5+1 6=4+2 6=4+1+1 6=3+3 6=3+2+1 6=3+1+1+1 6=2+2+2 6=2+2+1+1 6=2+1+1+1+1 6=1+1+1+1+1+1

C语言代码实现：

#include <stdio.h>

void Split(int n, int sum)
{
    if (n == 0)
    {
        printf("%d", sum);
        return;
    }
    else
    {
        for (int i = n; i > 0; i--)
        {
            printf("%d+", i);
            Split(i - 1, sum - i);
            printf("\n");
        }
    }
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        Split(n, n);
    }
    return 0;
}

算法思路：

1. 使用递归函数 Split(n, sum)，其中 n 表示当前需要拆分的数字，sum 表示已经拆分的数字之和。
2. 当 n 等于 0 时，表示已经完成了拆分，输出 sum。
3. 当 n 不等于 0 时，从 n 到 1 进行循环，对于每个 i，打印 i+，然后递归调用 Split(i - 1, sum - i)，继续拆分剩余的数字。
4. 每次递归调用之后，输出一个换行符。

代码解释：

1. Split(n, sum) 函数：
   • 递归出口：当 n 等于 0 时，表示已经完成了拆分，输出 sum。
   • 递归步骤：当 n 不等于 0 时，从 n 到 1 进行循环，对于每个 i，打印 i+，然后递归调用 Split(i - 1, sum - i)，继续拆分剩余的数字。
2. main() 函数：
   • 从标准输入读取一个整数 n，并调用 Split(n, n) 函数进行拆分。

总结： 该代码使用递归算法实现了正整数拆分组合的功能，并通过循环和递归调用实现了所有不同拆分组合的输出。代码清晰易懂，逻辑结构简单，易于理解和维护。