经典算法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 ) ;  
    }  

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。