整数划分问题
程序员文章站
2022-05-08 19:05:01
...
整数划分的递归实现算法。
输入:输入整数划分的整数(只输入一次,即n==m)。
输出:输入整数的划分个数值。
示例:输入:7,输出:15
q(n,m)的如下递归关系定义如下:
正整数n的划分数p(n)=q(n,n)。
import java.util.Scanner;
/*整数划分的递归实现算法。
输入:输入整数划分的整数(只输入一次,即n==m)。
输出:输入整数的划分个数值。
示例:输入:7,输出:15
q(n,m)的如下递归关系定义如下:
正整数n的划分数p(n)=q(n,n)。
当n=1,m=1时,q(n,m)=1;
当n<m时,q(n,m)=q(n,n);
当n=m时,q(n,m)=1+q(n,n-1);
当n>m>1时,q(n,m)=q(n,m-1)+q(n-m,m)
*/
public class ZhengShuHuaFen {
public static int suan(int n, int m) {
if (n < 1 || m < 1) {
return 0;
}
if (n == 1 && m == 1) {
return 1;
}
if (n < m) {
return suan(n, n);
}
if (n == m) {
return (1 + suan(n, n - 1));
}
return (suan(n, m - 1) + suan(n - m, m));
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(suan(n, n));
}
}
上一篇: 整数划分问题