👨‍🎓作者简介：一位喜欢写作，计科专业的大三菜鸟

🏡个人主页：starry陆离

📚订阅专栏：『算法笔记HNUCM-OJ』

如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦

『递归』整数划分

1.问题引入

题目描述

使用递归编写一个程序，求一个正整数n的所有划分个数。例如，输入3，输出3；输入4，输出5。

输入

多组输入，每一组是一个正整数n。

输出

输出划分数。

样例输入

3

4

样例输出

3

5

2.问题分析

q(n,m)我们定义为将n的最大加数不大于m的划分个数记作q(n,m)

例如，当n=5时，有7个划分，即

{5}

{4,1}

{3,2}  {3,1,1}

{2,2,1}  {2,1,1,1}

{1,1,1,1,1}

注意：3+2与2+3是同一种划分

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

（一）当n==1时，无论m的值为多少 ，只有一种划分，即{1}

（二）当m==1 时，无论n的值为多少，只有一种划分，即1个n，{n} 。

（三）当n==m时，根据划分中是否包含n，可以分为以下两种情况：

（1）划分中包含n的情况，只有一个，即  {n}

（2）划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分，即q(n,n-1)。

因此q(n,m)=1+q(n,n-1)

（四）当n<m时，由于划分中不可能出现负数，因此就相当于q(n,n)

（五）当n>m 时，根据划分中是否包含最大值m，可以分为以下两种情况：

（1）划分中包含m的情况，即q(n-m,m)（例如求q(5,3)=q(2,3)=q(2,2))

（2）划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分个数为q(n,m-1)

因此q(n,m)=q(n-m,m)+q(n,m-1)

3.递归通式

4.Java题解

importjava.util.Scanner;
publicclassMain {
publicstaticvoidmain(String[] args) {
Scannerscanner=newScanner(System.in);
intn,ans=0;
while(scanner.hasNext()) {
n=scanner.nextInt();
ans=q(n, n);
System.out.println(ans);
         }
scanner.close();
     }
publicstaticintq(intn,intm) {
if((n<1)||(m<1))return0;
if((n==1)||(m==1))return1;
if(n<m)returnq(n, n);
if(n==m)returnq(n, m-1)+1;
returnq(n,m-1)+q(n-m, m);
     }
}