posts - 71,  comments - 41,  trackbacks - 0

先来个只计算分割数的版本

int  Compute( int  number,  int  maximum)
{
    
if  (number  ==   1   ||  maximum  ==   1 )
        
return   1 ;
    
else   if  (number  <  maximum)
        
return  Compute(number, number);
    
else   if  (number  ==  maximum)
        
return   1   +  Compute(number, maximum  -   1 );
    
else
        
return  Compute(number, maximum  -   1 +  Compute(number  -  maximum, maximum);
}


int  IntPartionNo( int  n)
{
    
return  Compute(n, n);
}

打印所有分割版本
int  IntegerPartition( int  n)
{
    
int   * partition  =   new   int
[n]();
    
int   * repeat  =   new   int
[n]();

    partition[
1 =
 n;
    repeat[
1 =   1
;
    
int  count  =   1
;
    
int  part  =   1
;

    
int
 last, smaller, remainder;

    printf(
" %3d " , partition[ 1
]);
    
do
 
    
{
        last 
=  (partition[part]  ==   1 ?  (repeat[part -- +   1 ) :  1
;
        smaller 
=  partition[part]  -   1
;
        
if  (repeat[part]  !=   1
)
            
-- repeat[part ++
];
        partition[part] 
=
 smaller;
        repeat[part] 
=   1   +  last  /
 smaller;

        
if  ((remainder  =  last  %  smaller)  !=   0
)
        
{
            partition[
++ part]  =
 remainder;
            repeat[part] 
=   1
;
        }


        
++ count;

        printf(
" \n "
);
        
for  ( int  i  =   1 ; i  <=  part;  ++
i)
            
for  ( int  j  =   1 ; j  <=  repeat[i];  ++
j)
                printf(
" %3d "
, partition[i]);

    }
  while (repeat[part]  !=  n);

    
if
 (partition)
    
{
        delete [] partition;
        partition 
=   0
;
    }

    
if  (repeat)
    
{
        delete [] repeat;
        repeat 
=   0
;
    }


    
return  count;
}
没有时间把解释写出来,自己根据变量名结合网上原理凑合看吧,真是对不起观众啊
posted on 2006-12-06 17:59 Charles 阅读(1401) 评论(0)  编辑 收藏 引用 所属分类: 面试小算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2007年1月>
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

决定开始写工作日记,记录一下自己的轨迹...

常用链接

留言簿(4)

随笔分类(70)

随笔档案(71)

charles推荐访问

搜索

  •  

积分与排名

  • 积分 - 47996
  • 排名 - 455

最新评论

阅读排行榜

评论排行榜