首页 > 代码库 > 整数拆分
整数拆分
将一个整数N拆分成n个连续自然数的和。例如：
15 = 1+2+3+4+5
15 = 4+5+6
15 = 7+8
实现一个函数，打印所有可能，并且统计有多少种方法？
分析过程如下。
对于一个数N，
2个自然数相加：m+(m+1) =2m+1
3个自然数相加：(m-1)+m+(m+1) =3m
4个自然数相加：(m-1)+m+(m+1)+(m+2) =2(2m+1)
5个自然数相加：(m-2)+(m-1)+m+(m+1)+(m+2) =5m
6个自然数相加：(m-2)+(m-1)+m+(m+1)+(m+2)+(m+3) =3(2m+1)
7个自然数相加：(m-3)+(m-2)+(m-1)+m+(m+1)+(m+2)+(m+3) =7m
8个自然数相加：(m-3)+(m-2)+(m-1)+m+(m+1)+(m+2)+(m+3)+(m+4) =4(2m+1)
9个自然数相加：(m-4)+(m-3)+(m-2)+(m-1)+m+(m+1)+(m+2)+(m+3)+(m+4) =9m
可以总结：
对于一个整数N
如果可以表示为偶数个整数连加，则有k*(2m+1)，其中k，m是自然数；
如果可以表示为奇数个整数连加，则有k*m，其中k为奇数，m为自然数。
此外，还要注意，对于偶数的情况，累加的表达式可以总结为m+i，范围是i = 1-k:1:k
对于奇数的情况，累加的表达式可以总结为m+i，范围是i = -k/2:1:k/2
因此，综上可以可以得出最终的程序如下所示：
1 int PrintContinuousAdd(int source) { 2 3 int count = 0; 4 5 // error check 6 7 if(source<3){ 8 9 cout<<"error"<<endl;10 11 }12 13 else {14 15 // the right situation16 17 int m = 0;18 19 int k = 0;20 21 int beg = 0;22 23 int i = 0;24 25 for(m=1;m<=source/2;m++) {26 27 if(!(source%(2*m+1))) {28 29 k = source/(2*m+1);30 31 beg = 1-k;32 33 if(m+beg>0) {34 35 for(i=beg;i<=k;i++) {36 37 cout<<m+i<<" ";38 39 }40 41 cout<<endl;42 43 count++;44 45 }46 47 }48 49 if(!(source%m)) {50 51 k = source/m;52 53 if(1==k%2) {54 55 beg = 0-k/2;56 57 if(m+beg>0) {58 59 for(i=beg;i<=(0-beg);i++) {60 61 cout<<m+i<<" ";62 63 }64 65 cout<<endl;66 67 count++;68 69 }70 71 }72 73 }74 75 }76 77 }78 79 return count;80 81 }