#include  < stdio.h >

int  result[ 500 ];

int  main()
{
    
int  n;
    
    
while ( scanf( " %d " , & n) !=  EOF )
    
{
        
int  sum =   0 ;
        
int  len =   0 ;
        
int  value =   2 ;
        
        
while true  ) {
            sum
+=  value;
            result[len
++ ] =  value ++ ;
            
if ( sum +  value >  n )  break ;
        }

        value
-- ;
        
int  left =  n -  sum;
        
if ( value ==  left )
        
{
            
for int  i =   0 ; i <  len;  ++ i ) result[i] ++ ;
            result[len
- 1 ] ++ ;
        }

        
else   for int  i =  len -   1 ; i >=   0 , left >   0 ; i -- , left --  ) result[i] ++ ;
        
        
for int  i =   0 ; i <  len;  ++ i ) 
        
{
            
if ( i ==   0  ) printf( " %d " , result[i] );
            
else         printf( "  %d " , result[i] );
        }

        printf(
" \n " );
    }

    
    
return   0 ;
}


做法就是求出以2起始的最大连续自然数序列之和sum,使得sum的值不超过输入数n,
然后分情况讨论:

设此最大序列为2、3、……、w,则:

1。若剩余值(n-sum)等于w,则最后输出序列为:3、4、……、w、w+2,即将原最大序列每项加1,再将最后剩余的一个1加到最后一项上。

2。若剩余值(n-sum)小于w,则从序列的最大项i开始,从大到小依次将每项加1,直到剩余值用完。

posted on 2008-10-29 10:26 Darren 阅读(427) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

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