风的方向
厚德致远,博学敦行!
posts - 52,comments - 21,trackbacks - 0
        以前做过这么一个题目,在我们学校ACM网上,找了很久没找到,郁闷!网上走了一遭,基本和书上介绍的差不多,虽然做过但是重新去看思路的时候还是比较慢!!!我再写一下,加深影响!
         整数划分就是将一个正整数表示成一系列正整数之和,问有多少种不同划分方案!
         例如整数6可以划分成一下11中方案:
        6
        5 + 1
        4 + 2, 4 + 1 + 1
        3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1
        2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1
        1 + 1 + 1 + 1 + 1 + 1 
       如果你是编程好手看到这样的排列,可能一下子就能想到一种解题思路了!感慨,算法就是在培养解决问题的思路!!言归正传!先介绍下书上的思路:
                     一、p(n,m)含义:在正整数n的所有不同划分中,最大加数不大于m的划分数(m<=n;m,n>=1)!求整数6有几种划分时,既求p(6,6)。。。
                     二、函数递归关系:
                            1、n<1||m<1,return 0;
                            2、n==1||m==1,p(n,m)=1;
                            3、n<m,p(n,m)=p(n,n);例如:p(6,10)=p(6,6)   
                            4、n>m,p(n,m)=p(n,m-1)+p(n-m,m);例如:p(6,5)=p(6,4)+p(2,4); p(6,2)=p(6,1)+p(4,2);(这个等式是关键)
代码如下
#include<cstdio>
int q(int n,int m)
{
    
if((n<1)||(m<1)) return 0;
    
if(n==1||m==1return 1;
    
if(n<m) return q(n,n);
    
if(n==m) return q(n,m-1)+1;
    
return q(n,m-1)+q(n-m,m);
}


int main()
{
    printf(
"%d\n", q(6,6));
    
return 0;
}

      写完书上的解题思路,我突然发现前面我想到的一种解题思路错了!!不过这种递归算法运行效率低,计算整数35分解方案数的时候,计算速度很慢(大概两秒出现答案14930352),40的时候更慢了- -,我想用二维数组填表的方式应该会快一点!!有更好算法的可以留言!!随时候教~~
      
posted on 2010-08-31 15:25 jince 阅读(1968) 评论(2)  编辑 收藏 引用 所属分类: 算法设计与分析

FeedBack:
# re: 整数划分
2012-06-03 12:09 | JsDoItao
return q(n,m-1)+q(n-m,n-m);
上面有错误,完全忽视了加数由大到小有序,
最后n>m的情况,分成1)最大加数为m和2)最大加数<=m-1两种情况,对于2)其划分数是q(n,m-1)没错,但是对于1)因为限定了最大的加数为m,所以必须是q(n-m,m),而不是q(n-m,n-m),这个只对m>n-m的情况有效,但是如果m<n-m,那么你就计算错了~~
:-)


  回复  更多评论
  
# re: 整数划分[未登录]
2012-06-03 14:11 | jince
@JsDoItao
嗯,在递归关系中的等式是正确的。  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理