【c语言】整数拆分

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

输入格式:

一个正整数n

输出格式:

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

输入样例:

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

4
 

输出样例:

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; }

 

热门相关:仙城纪   第一神算:纨绔大小姐   女演员性爱丑闻   豪门闪婚:帝少的神秘冷妻   薄先生,情不由己