实验内容：整数分划, 要求给出分划方式与分化数目的总和
问题分析：
对于n不超过m的划分可以分为三种情况：
（1）n
（2）n=m结果就是{n,x1,x2…},而{x1,x2…}就是n不超过n-1的划分，问题规模减小
（3）n>m 结果分为两部分，一部分是包括m的划分:{m,x1,x2…},而{x1,x2…}就是n-m不超过m的划分。另一部分是不包括m的划分,就相当于n不超过m-1的划分。
数学建模：
针对三种情况建立相应函数：
定义函数Q(n,m)表示整数n任何被加数不超过m的划分数目
递归关系：
（1）m=n Q(n,n)=1+Q(n,n-1)
（2）m
递归终止条件是：
Q(n,1)=1&&Q(1,m)=1
实验代码：
#define _CRT_NO_WARNINGS_SECURE
#include
#include
using namespace std;
void print(int *result,int length) {
if (length > 1) {
for (int i = 0; i < length-1; i++) {
cout << result[i] << "+";
}
cout << result[length - 1];
cout << "n";
}
else cout<1)
{
result[length] = n;
print(result, length + 1);
return 1;
}
//不超过1分解知道n=0分解完成
else if (n>=0&&m==1) {
if (n == 0) {
print(result, length);
}
else {
result[length] = 1;
Divinteger(n - 1, m, result, length + 1);
}
return 1;
}
else if (n < m) {
return Divinteger(n, n, result, length);
}
else if (n == m)
{
//将自己存入数组并输出
result[length] = m;
print(result, length+1);
return 1 + Divinteger(n, m - 1, result, length);
}
else {
result[length] = m;
return Divinteger(n - m, m, result, length + 1) + Divinteger(n, m - 1, result, length);
}
}
int main()
{
int n = 0;
int m = 0;
int result[100] = { 0 };
int length = 0;
int num = 0;
cout << "要划分的数:";
cin >> n;
cout << "划分数不超过:";
cin >> m;
num = Divinteger(n, m, result, length);
cout << "划分的个数为:" << num << endl;
system("pause");
return 0;
}
测试数据：
对10划分且不小于6
实验结果：
时间复杂度： O()
