經典算法2：遞歸求解整數劃分

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

比如：6的整數劃分為11種
 最大數  
    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

編程實例：

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

在正整數n的所有不同的劃分中，將最大加數n1不大于m的劃分個數記為q(n,m)。可以建立q(n,m)如下的遞歸關系：

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

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

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

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

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

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

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

此時就是將n表示成最大加數為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 ) ;  
}  </pre>