问题描述：将正整数n划分成一系列正整数之和，输出n的全部划分个数。 例如6有11种划分。

• • 6；
  • 5+1;
  • 4+2, 4+1+1;
  • 3+3, 3+2+1, 3+1+1+1;
  • 2+2+2, 2+2+1+1, 2+1+1+1+1;
  • 1+1+1+1+1+1;

算法分析：在正整数n的所有不同划分中，将最大加数n1不大于m的划分个数记做q(n,m)。可以建立q（n,m）的如下递归关系。

(1)q(n,1) = 1, n>=1 ，当最大加数为1时，任何正整数n都只有一种划分形式，即n=1+1+...+1.

(2)q(1,m)= 1,只有一种拆分方法。1

(3)q(n,m)=q(n,n),m>=n，因为最大加数不能大于被拆分数

(4)q(n,n) =1+q(n,n-1)。正整数n的划分由n1 = n 的划分和n1<=n-1的划分组成

(5)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1.正整数n的最大加数n1不大于m的划分由n1=m的划分和n1<=m-1的划分组成。（自行尝试几个简单例子便很容易理解）

以上的关系实际上给出了q(n,m)的递归式

• 1                                    n=1,m=1
• q(n,n)                             n<m
• 1+q(n,n-1)                     n=m
• q(n,m-1)+q(n-m,m)       n>m>1

1 import java.util.Scanner; 2  3 /** 4  * 输出正整数的全部拆分总数 5  * @author AganRun 6  */ 7 public class NumSplit { 8  9     public static void main(String[] args){10         11         Scanner scan = new Scanner(System.in);    //输入待拆分正整数n12         int n = scan.nextInt();13         System.out.println(n + "的拆分方式有" + q(n,n) + "种");14         15     }16     17     //将正整数n以最大拆分数m的拆分情况总数18     public static int q(int n, int m){19     20         if((n<1) || (m<1)) return 0;    //分情况讨论，同算法分析中的处理方式21         if((n==1) || (m==1)) return 1;22         if( n