問題描述：將正整數(shù)n表示成一系列正整數(shù)的和，n=n1+n2+……+nk，返回劃分的方法數(shù)。

比如：6的整數(shù)劃分為11種
 最大數(shù)  
    6           6
    5           5 + 1
    4           4 + 2, 4 + 1 + 1
    3           3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1
    2           2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1
    1           1 + 1 + 1 + 1 + 1 + 1

編程實例：

將正整數(shù)n表示成一系列正整數(shù)之和， n=n1+n2+……+nk,其中n1>=n2>=……nk,k>=1,正整數(shù)的這種劃分稱為正整數(shù)n的劃分。正整數(shù)n的不同劃分的個數(shù)稱為正整數(shù)n的劃分數(shù)。

在正整數(shù)n的所有不同的劃分中，將最大加數(shù)n1不大于m的劃分個數(shù)記為q(n,m)�？梢越�立q(n,m)如下的遞歸關系：

1、 q(n,1) = 1 ，n>=1 ;    當最大加數(shù)不大于1時，任何正整數(shù)n只有一種表示方式：n = 1+1+……+1 。n個1的  和。

2、q( n,m ) = q( n,n )，n<=m;  最大加數(shù)不能大于n。

3、 q( n,n ) = 1 +  q( n , n-1 );   正整數(shù)的劃分由n1=n和n1<=n的劃分組成。

4、q( n,m ) = q( n,m-1 )+q( n-m,m ), n>m>1；正整數(shù)n的最大加數(shù)不大于m的劃分由 n1=m的劃分和n1<m的劃分組成。

注意：q(n-m,m)表示最大加數(shù)n1=m的劃分。分析如下：

q(n-m，m)是表示將n-m表示成最大加數(shù)不大于m的劃分，因此我們可以知道：

n-m = x,其中x表示最大加數(shù)不大于m的劃分。將m移到右邊，得：n = m + x ;

此時就是將n表示成最大加數(shù)為m的劃分。寫出如下程序：（程序在wintc下編譯通過，運行結果正確）

    #include <stdio.h>  
    #include <stdlib.h>  
    int intPart( int n , int m ) ;  
    void main()  
    {  
        int num ;  
        int partNum = 0 ;  
        printf("Please input an integer:/n") ;  
        scanf("%d",&num) ;  
        partNum = intPart(num,num);  
        printf("%d/n",partNum) ;  
        getch() ;  
    }  
      
    int intPart( int n , int m )  
    {  
         
        if( ( n < 1 ) ||( m < 1 ) ) return 0 ;  
         
         
        if( ( n == 1 )||( m == 1 ) ) return 1 ;  
         
         
        if( n < m ) return intPart( n , n ) ;  
         
         
        if( n == m ) return intPart( n , m-1 ) + 1 ;  
          
         
        return intPart( n , m-1 ) + intPart( n - m , m ) ;  
    }  

標簽：

版權申明：本站文章部分自網(wǎng)絡，如有侵權，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權歸原作者所有，如需使用，請與原作者聯(lián)系。