活动地址:CSDN21天学习挑战赛
👨🎓作者简介:一位喜欢写作,计科专业大二菜鸟
🏡个人主页:starry陆离
🕒首发日期:2022年8月11日星期三
🍁每日推荐:『牛客网-面试神器』
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦
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题解
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);
}
}
本文含有隐藏内容,请 开通VIP 后查看