关于计算n的合数?该怎么处理

关于计算n的合数?

C/C++ code

/*****************************************************************************计算的合数,一个整数n可以有多种划分,使其划分的一列整数之和为n,例如,6的分划为:    6    5 1    4 2    .    .    .    1 1 1 1 1 1   共11种,这种分划的程序如下:  这是软考程序设计的一道习题,要求补全代码(程序中打问号的地方,填入一行代码).  我想了一天也想不出来,请各位大侠指点一下这个程序的思路.谢谢*****************************************************************************/#include<stdio.h>int n[1000] = { 0 };int m = 0;int k = 0;void output_sum(){    int j = 0;        for( j = 0; n[j] != 0; j++ )                {        printf("%3d", n[ j ] );        printf("\n");        }}void sum( int i ){        if( m - n[ i ] <= n[ i ] )                    {        //??        i++;        n[ i + 1 ] = 0;        }    else            {        //??        //??                i++;            }    if( m != n[ i ] )                {        //??        }    else                {        output_sum();        }    if( n[ i ] > 1 )            {        //??        //??                }        else            {        while( ( n[ i ] == 1 ) && ( i > 0 ) )                        {            i--;            m += n[ i ];                    }        if( i != 0 )            {            //???                        //???            }        }}int main(){    int i = 0;    int j = 0;    scanf( "%d", &n[ 0 ] );    m = k = n[ 0 ];    for( i = 1; i <= k; i++ )                {        n[ i ] = 0;            }    while( n[ 0 ] != 1 )        {        n[ 0 ] --;        i = 0;        sum(0);        m = k;        }}

C/C++ code

/*给你参考一下*/#include <stdio.h> int a[100]={0}; void shuchu(int m) { int i; for(i=0;i<=m-1;i++) printf("%d ",a[i]); printf("\n"); } void fenjie(int n,int m) { int i; if(n==0) shuchu(m); else for(i=n;i>=1;i--) if(m==0||i<=a[m-1]) {a[m]=i;fenjie(n-i,m+1);} } void main(void) { int n,i,m=0; printf("please input a number(0<n<100): "); scanf("%d",&n); fenjie(n,m); }
[解决办法]
for( j = 0; n[j] != 0; j++ )
      
       {

       printf("%3d", n[ j ] );

       printf("\n");

       }
应该是:

for( j = 0; n[j] != 0; j++ )
      
       {

       printf("%3d", n[ j ] );

      
       }
       printf("\n");

不然对不齐的；

[解决办法]
我把某算法教材上面的算法说一下：
递归，但是需要使用memoziation

PartitionsI_C(num,d)
if(num<=1) or max_digit = 1
return 1
if(d>num) d = num;

if <num,max_digit> in cache  
      return cache(<num,max_digit>)

res = 0
for i=d downto 1
res += PartitionsI_C(num-i,i)
cache(<num,max_digit>) =  res;
return res


PartitionS_C(n)
 return PartitionsI_C(n,n)


当然也可用动态规划，但是状态空间比这个memoziation要大。