【c语言】整数拆分

2023-03-09 19:31 由箱庭发表于 #后端开发

将一个正整数n拆分成若干个正整数的和（至少两个数,n<=100）。

输入格式:

一个正整数n

输出格式:

若干行，每行一个等式（数与数之间要求非降序排列）。最后一行给出解的总个数

输入样例:

在这里给出一组输入。例如：

输出样例:

4=1+1+1+1
4=1+1+2
4=1+3
4=2+2
4

最后一行的4表示总共有4个解。

主要思路：使用深度优先搜索算法。从n开始，每次枚举所有可能的加数，如果加数满足要求，则将其加入到组成部分中，继续递归处理剩余部分，直到剩余部分被成功分解或者不满足要求，然后回溯，撤销当前加数的选择，尝试下一个加数。这样就能够穷举所有可能的分解方案。使用递归函数dfs()实现深度优先搜索。dfs()函数有三个参数：cur表示当前需要分解的数，sum表示已经分解的数之和，last表示上一个加数。当cur为0且sum为n时，找到了一个分解方案，将其输出；否则，枚举所有可能的加数，并对剩余部分进行递归处理。在dfs()函数中使用数组nums[]存储每个组成部分的数值，使用变量size记录当前组成部分的数量。在递归处理剩余部分时，需要将当前加数加入组成部分，并递归处理剩余部分，成功分解后回溯，撤销当前加数的选择。这里使用回溯法可以避免重复计算。

// 原作者箱庭，请勿转载

#include <stdio.h>

int n;          // 待分解的数
int nums[100];  // 存储每个组成部分的数值
int size;       // 当前组成部分的数量
int cnt;        // 分解方案的数量

// 深度优先搜索函数，cur为当前需要分解的数，sum为已分解的数之和，last为上一个加数
void dfs(int cur, int sum, int last) {
    // 如果已经成功分解出所有数且总和为n，则找到了一个分解方案
    if (cur == 0 && sum == n) {
        cnt++;  // 记录分解方案的数量
        // 输出分解方案
        printf("%d=%d", n, nums[0]);
        for (int i = 1; i < size; i++) {
            printf("+%d", nums[i]);
        }
        printf("\n");
    } else {
        // 枚举所有可能的加数
        for (int i = 1; i <= cur; i++) {
            // 确保加数不小于上一个加数，总和不超过n，并且不能仅剩一个数未加入
            if (i >= last && sum + i <= n && i<n ) {
                nums[size] = i;  // 将当前加数存入组成部分
                size++;          // 组成部分数量加1
                dfs(cur - i, sum + i, i);  // 继续分解剩余部分
                size--;          // 回溯，撤销当前加数的选择
            }
        }
    }
}

//原作者箱庭，请勿转载



int main() {
    scanf("%d", &n);    // 输入待分解的数
    nums[0] = 0;        // 初始化组成部分，第一个数为0
    size = 0;           // 初始化组成部分数量
    dfs(n , 0, 1);      // 开始分解
    printf("%d", cnt);  // 输出分解方案数量
    return 0;
}