整数划分问题

 

问题描述:

将正整数n表示成一系列正整数之和,n=n1 + n2 + n3 + … + nk,其中n1≥n2≥n3≥…≥nk≥1,k≥1.正整数n的这种表示称为正整数n的划分.正整数n的不同划分个数称为正整数n的划分数,记作q(n).

 

实现程序:

/**
 * Copyright (c) 2011 Trusted Software and Mobile Computing(TSMC)
 * All right reserved.
 *
 * Created on 2011
 *
 *		http://jarg.iteye.com/
 *
 */
// Contributors:  Jarg Yee <[e-mail]>
/*
 * TODO 整数划分问题
 */
public class Division
{
	public static void main(String[] args)
	{
		System.out.println("整数划分数:\t" + q(7));
	}

	/* TODO 求整数问题划分数 */
	private static int q(int n)
	{
		return q(n,n);
	}

	/* TODO 求子问题划分数 */
	private static int q(int n, int m)
	{
		if(m<0 || n<0)
			return 0;
		if(m==1 || n==1)
			return 1;
		if(n<m)
			return q(n,n);
		if(n==m)
			return 1 + q(n,m-1);
		if(n>m)
			return q(n,m-1) + q(n-m,m);
		else
			return 0;
	}

}

 

 

问题来自: 王晓东<<算法设计与分析>>