整数划

描述

将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，

其中n1≥n2≥…≥nk≥1，k≥1。

正整数n的这种表示称为正整数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。

输入

第一行是测试数据的数目M（1<=M<=10）。以下每行均包含一个整数n（1<=n<=10）。

输出

输出每组测试数据有多少种分法。

样例输入

1

6

样例输出

11

所谓整数划分，是指把一个正整数n写成为

 Mi 

为正整数，并且

 1<=Mi<=n 

；

 {M1,M2,M3...,Mi} 

 {M1,M2,M3...,Mi}

中的最大值不超过m，即

 Max(m1,m2,...,mi)<=m 

分析

 f(n,m) 

 {4} 

，

 {3,1} 

，

 {2,2} 

，

 {2,1,1} 

，

 {1,1,1,1} 

 4=1+3 

和

 4=3+1 

根据n和m的关系，考虑一下几种情况：

 n=1 

时，无论m的值为多少

 (m>0) 

，只有一种划分，即

 {1} 

 m=1 

时，无论n的值为多少，只有一种划分，即n个1，

 {1,1...1} 

 n=m 

 {n} 

 (n-1) 

 f(n,n)=1+f(n,n-1) 

 n<m 

时，由于划分中不可能出现负数，因此就相当于

 f(n,n) 

 n>m 

 {m,{x1,x1...,xi}} 

，其中

 {x1,x2,...,xi} 

的和为n-m，因此这种情况下为

 f(n-m,m) 

 (m-1) 

划分，个数为

 f(n,m-1) 

 f(n,m)=f(n-m,m)+f(n,m-1) 

综上所述：

/函数：q(int n,int m)
//作用：用来得到正整数n，最大加数不大于m的划分个数
public static int q(int n,int m){
    //若正整数或最大加数小于1，则返回0
    if(n<1||m<1) return 0;
    //若正整数或最大加数等于1，则划分个数为1（n个1相加）
    if(n==1||m==1) return 1;
    //若最大加数实际上不能大于正整数n，若大于则划分个数等于最大加数为n的划分个数
    if(n<m) return q(n,n);
    //若正整数等于最大加数，则划分个数等于
    if (n==m) return 1+q(n,n-1);
    return q(n,m-1)+q(n-m,m);
}      

public static void main(String[] args){ 
    Scanner sc=new Scanner(System.in);
    int a=sc.nextInt();
    int[] i=new int [a];
    for(int d=0;d<a;d++){
      int b=sc.nextInt();
      int c=b;
      i[d]=num(b,c);
    }
    for(int d=0;d<a;d++){
      System.out.println(i[d]);
    }
  }
  public static int num(int n,int m){
    if(n<1||m<1){
      return 0;
    }
    if(n==1||m==1){
      return 1;
    }
    if(n<m){
      return num(n,n);
    }
    if(n==m){
      return num(n,m-1)+1;
    }
    return num(n,m-1)+num(n-m,m);
  }