整数划

描述

将正整数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}  为n的一个划分。 如果    {M1,M2,M3...,Mi}  中的最大值不超过m，即  Max(m1,m2,...,mi)<=m  ，则称它属于n的一个m划分。

分析

这里我们记n的m划分的个数为  f(n,m)  。 例如，当n=4时，有5个划分，即  {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，可以分为以下两种情况： （1）划分中包含n的情况，只有一个，即  {n}  。 （2）划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有  (n-1)  划分。 因此  f(n,n)=1+f(n,n-1)  。 （四）当  n<m  时，由于划分中不可能出现负数，因此就相当于  f(n,n)  。 （五）当  n>m  时，根据划分中是否包含最大值m，可以分为以下两种情况： （1）划分中包含m的情况，即  {m,{x1,x1...,xi}}  ，其中  {x1,x2,...,xi}  的和为n-m，因此这种情况下为  f(n-m,m)  。 （2）划分中不包含m的情况，则划分中所有值都比m小，即n的  (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); }