欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

整数划分问题

程序员文章站 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));
	}
}