查看: 2727|回复: 0

[转帖]整数的分划问题

字体大小: 正常放大

小杰200521

3 主题	2 听众	21 积分

升级 16.84%

该用户从未签到

电梯直达

1^#

发表于 2006-2-2 19:48 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

[整数的分划问题] 对于一个正整数M的分划就是把M写成一系列正整数之和的表达式。例如，对于正整 数M=6，它可以分划为： 6 5+1 4+2, 4+1+1 3+3, 3+2+1, 3+1+1+1 2+2, 2+2+1+1, 2+1+1+1+1 1+1+1+1+1+1 注意，分划与顺序无关，例如5+1和1+5是同一种分划。另外，这个整数M本身也算 是一种分划。现在的问题是，对于给定的正整数M，要求编程序计算出其分划的数 目P(M)。 解析： 我们定义一个函数Q(M.N)，表示整数M的“任何被加数都不超过N”的分划的数目。 Q(M.N)有以下递归关系： 1)Q(M,1)=1，表示当最大的被加数是1时，该整数M只有一种分划，即M个1相加； 2)Q(1,N)=1，表示整数M=1只有一个分划，不管最大被加数的上限N是多大； 3)Q(M,N)=Q(M,M)，如果M<N。很明显，M的分划不可能包含大于M的被加数N； 4)Q(M,M)=1+Q(M,M-1)。等式的右边分为两部分：第一部分的1表示M只包含一个被 加数等于M本身的分划；第二部分表示M的所有其他分划的最大被加数N<=M-1，所以 其他分划的数目就是等式右边的第二项。 5)Q(M,N)=Q(M,N-1)+Q(M-N,N)，如果M>N。等式右边的第一部分表示被加数中不包 含N的分划的数目；第二部分表示被加数中包含N的分划的数目，因为如果确定了一 个分划的被加数中包含N，则剩下的部分可以按照对M-N的分划进行划分。 上述五个递归关系式对Q(M,N)作了递归定义。因为M的所有分划的数目P(M)=Q(M, M)，所以上述关系式也定义了P(M)。 有了递归关系式后，解决问题的算法就非常简单了：

artition(M, N) 1. if M < 1 or N < 1 2. then Error("输入参数错误") 3. else if M = 1 or N = 1 4. then return 1 5. else if M < N 6. then return Partition(M, M) 7. else if M = N 8. then return (1 + Partition(M, M-1)) 9. else 10. return (Partition(M, N-1) + Partition(M-N, N)); 请注意，正整数的划分的数目随着M的增加增长的非常快（以指数级增长），所以 不要用较大的整数来测试按照上述算法编写出的程序。