/*
输入一个整数，如:整数7它的和为 N1+N2+...+Nk=7,且 N1>=N2>=..>=Nk(k>=1),
将其拆分，并打印出各种拆分.对于7有: 6+1=7..5+2=7....1+1+1+1+1+1+1=7共有14种拆分方法。
分解过程:
输入3:
(对5分解) 5=4+1 5=3+2
(用递归对4分解) 4=3+1 4=2+2
(用递归对3分解) 3=2+1
(用递归对2分解) 2=1+1
*/
View Code
1 #include<iostream>
2 #include<list>
3
4 usingnamespace std;
5
6 int count=0;//记录总的分解方法
7 int temp=0;
8
9 list<int> ilist; //保存分解过程中产生的每种分解方法
10
11 void divide(int num, int flag);
12 void print(list<int> ilist, int num) //打印每种分解方法
13 {
14 list<int>::iterator ibegin, iend;
15 ibegin=ilist.begin();
16 iend=ilist.end();
17 if(ibegin==iend)
18 {
19 cout<<"The list is empty!"<<endl;
20 exit(EXIT_FAILURE);
21 }
22 cout<<num<<" = "<<*ibegin;
23 ibegin++;
24 while(ibegin!=iend)
25 {
26 cout<<"+"<<*ibegin;
27 ibegin++;
28 }
29 cout<<endl;
30 }
31
32 int main()
33 {
34 cout<<"Please inpu the num:"<<endl;
35 int num;
36 while(cin>>num , num<=0)
37 {
38 cout<<"请输入大于0的正整数!"<<endl;
39 }
40 temp=num;
41 divide(num,1);
42 cout<<"共有: "<<count<<" 种分法!"<<endl;
43 return0;
44 }
45
46 void divide(int num, int flag)
47 {
48
49 if(num==flag) //当num==flag时到了最底层的分解
50 {
51 if(!ilist.empty())
52 {
53 ilist.pop_front();
54 }
55 ilist.push_front(flag);
56
57 print(ilist,temp);
58 ilist.pop_front(); //当递归回退一层时删除list中的第一个元素
59 return;
60 }
61 if(!ilist.empty())
62 {
63 print(ilist,temp);//每次进入divide一次就产生了一种分法,将其打印输出
64 }
65 for(int i=flag; i<=num/2; i++)
66 {
67 count++;
68
69 if(!ilist.empty())
70 {
71 ilist.pop_front(); //对于ilist.front()产生了一种分解方法，
72 }
73 ilist.push_front(i); //将ilist.front()取出并将两分解元素push到ilist头部
74 ilist.push_front(num-i);
75
76 divide(num-i,i);//递归
77 }
78
79 ilist.pop_front(); //当递归回退一层时删除list中的第一个元素
80 }