整数划分问题
问题描述:
将正整数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 <yeshaoting@gmail.com>/* * 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);elsereturn 0;}}
http://dl.iteye.com/upload/attachment/446840/e2f07908-bb67-3601-bbeb-b7d8e92b2e91.jpg
问题来自: 王晓东<<算法设计与分析>>
页:
[1]