活动地址：CSDN21天学习挑战赛

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

🏡个人主页：starry陆离

🕒首发日期：2022年8月11日星期三

🍁每日推荐：『牛客网-面试神器』

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

1.问题引入

题目描述

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

输入

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

输出

输出划分数。

样例输入

 3
 4
1
2

样例输出

 3
 5
1
2

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}
1
2
3
4
5
6
7
8
9

注意：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)

（四）当nq(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题解

 
 import java.util.Scanner;
 public class Main {
 
     public static void main(String[] args) {
         Scanner scanner=new Scanner(System.in);
         int n,ans=0;
         while(scanner.hasNext()) {
             n=scanner.nextInt();
             ans=q(n, n);
             System.out.println(ans);
         }
         scanner.close();
     }

     public static int q(int n,int m) {
         if((n<1)||(m<1))return 0;
         if((n==1)||(m==1))return 1;
         if(n<m)return q(n, n);
         if(n==m)return q(n, m-1)+1;
         return q(n,m-1)+q(n-m, m);
     }
 }
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24