1 /* 2 Subject:计算机算法设计与分析 3 Title:例2-5 整数划分问题：输出一个整数的所有划分并统计总划分数 4 Coder:Hao 5 Class:计科0906 6 Num:0304090614 7 Date:Sept 20th,2011 8 */ 9 10 #include <iostream> 11 using namespace std;12 13 //用于打印(输出)的函数 14 //result为存储某划分结果的数组，length为此划分所占长度-1（从0开始） 15 void display(int *result, int length)16 {17 for (int i = 0; i<length; i++)18 cout << result[i] << " ";19 cout << endl;20 }21 22 //主划分函数q(int n,int m,int *result,int length) 23 //算法参考了书例2-5并为了打印各划分做了一定修改 24 //n为待划分整数，m为最大加数上限,result和length意以同display函数同25 //名变量定义 26 //将q分成五种情况分类讨论，其中包含递归调用27 28 int q(int n, int m, int *result, int length)29 {30 //当n>=1并且m=1时，q(n,m,result,length)=q(n-1,m,result,length) 31 if (n >= 0 && m == 1) {32 //直至n=0并且m=1时，输出 33 if (n == 0) {34 display(result, length);35 }36 else {37 result[length] = 1;38 q(n - 1, m, result, length + 1);39 }40 return 1;41 }42 43 44 // 当 n=1并且m>1 时，分解已经完成，进行输出 45 else if (n == 1 && m>1)46 {47 result[length] = n;48 display(result, length + 1);49 return 1;50 }51 52 //当n<m时，q(n,m,result,length)=q(n,n,result,length) 53 else if (n<m)54 {55 return q(n, n, result, length);56 }57 58 //当n=m时，q(n,m,result,length)=q(n,m-1,result,length)+1（划分数目） 59 else if (n == m)60 {61 result[length] = m;62 display(result, length + 1);63 return q(n, m - 1, result, length) + 1;64 }65 66 //当n>m>1时，67 //q(n,m,result,length)=q(n-m,m,result,length+1)+q(n,m-1,result,length) 68 else69 {70 result[length] = m;71 return q(n - m, m, result, length + 1) + q(n, m - 1, result, length);72 }73 }74 void main()75 {76 int n; 77 char c;78 //定义待划分整数 79 int result[100] = { 0 }, length = 0; //初始化80 81 cout << "please input the integer:";82 cin >> n;83 cout << "整数" << n << "的划分个数为" << q(n, n, result, length) << endl;84 85 cin >> c;86 }