c语言递归形式整数拆分
时间: 2023-08-02 11:09:42 浏览: 68
整数拆分问题是指将一个正整数分解成若干个正整数的和的形式,且分解出的每个正整数必须大于等于1,且分解的顺序不同视为不同的拆分方法。例如,对于正整数5,可以有以下拆分方法:
- 5
- 4 + 1
- 3 + 2
- 3 + 1 + 1
- 2 + 2 + 1
- 2 + 1 + 1 + 1
- 1 + 1 + 1 + 1 + 1
下面是使用递归实现整数拆分的C语言代码:
```c
#include <stdio.h>
// 分解整数n,最大值为m
void integerPartition(int n, int m)
{
static int a[100]; // 用静态数组存储分解结果
if (n == 0) { // 边界条件:n为0,输出分解结果
for (int i = 0; i < m; i++) {
printf("%d ", a[i]);
}
printf("\n");
return;
}
for (int i = 1; i <= n; i++) { // 枚举分解出的第一个正整数
if (m == 0 || i <= a[m-1]) { // 保证分解出的正整数不递减
a[m] = i; // 将分解出的正整数存储在数组中
integerPartition(n-i, m+1); // 递归分解剩余部分
}
}
}
int main()
{
int n;
printf("请输入一个正整数:");
scanf("%d", &n);
printf("整数 %d 的所有拆分结果为:\n", n);
integerPartition(n, 0); // 从0开始存储分解结果
return 0;
}
```
在上面的代码中,使用一个静态数组a来存储分解结果。递归函数integerPartition的参数n表示要分解的整数,m表示已经分解出的正整数个数。函数先判断边界条件,如果n为0,则输出分解结果;否则,枚举分解出的第一个正整数,并将其存储在数组中,然后递归分解剩余部分。在枚举分解出的第一个正整数时,需要保证分解出的正整数不递减,这样可以避免重复计算。