整数划分递归相关问题

短命女 2023-10-05 11:50 6阅读 0赞

### 算法设计----整数划分递归相关问题 ###

#### 一.原问题 ####

整数划分，是指把一个正整数n写成如下形式：

假设整数n,能被划分为i段n=a1+a2+...ai，其中ak为n中划分的最大整数（1<=ak<=n，1<=k<=i）,则\{a1,a2...ai\}是n的ak的一个划分

当n=6时我们可以获得以下这几种划分

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hnbnV4Y18xOTkz_size_16_color_FFFFFF_t_70][]

一共有11种

**分析：讨论整数n和划分的最大整数m的关系，可以分为以下几种情况：**

①当整数n==1,只有一种划分，即\{1\}

②当划分的最大整数m==1时，只有一种划分，即\{1，1......1\}

③当n<m时，整数n可以划分的最大的数为n,即f(n,n)种划分

④当n==m时，根据需不需要划分最大整数m,可以分为两种情况：

a:需要划分最大整数为m,只有一种划分，即\{m\}

b:不需要划分最大整数为m,即可能划分的最大整数为m-1，即有f(n,m-1)种划分

⑤当n>m时，根据需不需要划分最大整数m,可以分为两种情况：

a:需要划分最大整数为m,所以继续在n-m中划分，划分的最大整数还可能为m，所以有f(n-m,m)种划分

b:不需要划分最大整数为m，所以划分的最大整数可能为m-1,即有f(n,m-1)种划分

综上所述的转移状态方程：

1 当 n==1或 m==1时

f（n，m）= f(n,n) 当n<m时

1+f(n,m-1) 当n==m时

f(n-m,m)+f(n,m-1) 当n>m时

python源代码：

#整数划分问题
    #假设整数n,能被划分为i段n=a1+a2+...ai，其中ak为n中划分的最大整数（ak<=n，k<=i）,其中{a1,a2...ai}是n的ak的一次划分
    #现在求整数n能够划分成多少种
    def huafen(n,m):  #n为整数，m为划分的最大整数，m<=n
        if(n==1 or m==1):
            return 1
        elif n==m:
            return 1+huafen(n,m-1) 
        elif(n<m):
            return huafen(n,n)
        else:
            return huafen(n,m-1)+huafen(n-m,m)
    
    a=[]
    t=0
    def digui(sum,k,m,l):
        global a
        global t
        if(sum>l):
            return
        elif(sum==l):
            t+=1
            print("第",t,"种：")
            for x in range(len(a)-1):
                print(str(a[x])+"+",end="")
            print(a[-1])
            
        else:
            c=range(m)
            for y in reversed(c):
                y+=1
                sum+=y   
                a.append(y)    #加入到a列表中
                digui(sum,k+1,y,l)  #递归调用
                a.pop()   #出列表，恢复现场，回溯
                sum-=y  #恢复现场，回溯
    
    def main():
        print("请输入一个整数：")
        v=int(input())
        p=huafen(v,v)
        print("该整数的划分一共有"+str(p)+"种")
        print("所有的划分如下：")
        digui(0,0,v,v)
    
    main()

运行结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hnbnV4Y18xOTkz_size_16_color_FFFFFF_t_70 1][]

#### 二.变形1 ####

如果限制每一个划分的整数不能一样，即划分的每一个整数不同 ，则又有多少种划分呢？

其实我们只需在原问题进行修改即可：

①当m==1时，我们需要设置\{1，1，1，....1\}为0种

②当n>m时，我们需要修改的是当需要选取最大整数m时 ，我们将最大值m-1,即f(n-m,m-1) 种

其余的不需要修改

**pythoon源码：**

#整数划分变形问题
    def huafen(n,m):  #n为整数，m为划分的最大整数，m<=n
        if(n==1):
            return 1
        elif(m==1):   #当m==1时，设置1，1，1.....1}为0种
            return 0
        elif n==m:
            return 1+huafen(n,m-1)
        elif(n<m):
            return huafen(n,n)
        else:
            return huafen(n,m-1)+huafen(n-m,m-1)   #使下次划分的整数小于上次的划分的最大整数
    
    a=[]
    t=0
    def digui(sum,k,m,l):
        global a
        global t
        if(sum>l):
            return
        elif(sum==l):
            t+=1
            print("第",t,"种：")
            for x in range(len(a)-1):
                print(str(a[x])+"+",end="")
            print(a[-1])
            
        else:
            c=range(m)
            for y in reversed(c):
                y+=1
                sum+=y
                a.append(y)
                digui(sum,k+1,y-1,l)   #这里需要将下一次的最大划分整数修改为上一次划分最大整数-1，不能与上一次相同
                a.pop()
                sum-=y
    
    def main():
        print("请输入一个整数：")
        v=int(input())
        p=huafen(v,v)
        print("该整数的划分一共有"+str(p)+"种")
        print("所有的划分如下：")
        digui(0,0,v,v)
    main()

运行结果如下：

![20201017110801598.png][]

#### 三.变形2 ####

如果限制每次划分的整数的个数 ，则又有多少种划分呢？**（类似与盘子分苹果问题）**

（其中n为整数，每次划分只能划分为m个数）

**分析：①**当m==1时，只有一种划分，即\{n\}

②当n<m时，由于划分的整数不可能为负数和小数，则划分不尽，所以为0

③当n==m时，也是只有一种划分。即\{1，1，1，1...1\}

④当n>m时，根据划分的整数中是否包含1，可以分为两种情况：

a:划分的整数中至少有一个1，则在n-1中继续划分为m-1份，即f(n-1,m-1)种划分

b:划分的整数中没有1，所以m个部分划分的整数必须都大于1，所以先给m个部分设为1，接着将剩余的n-m整数对m个部分分别加数，即要保证m个部分均大于1，即n-m>=m,则总共有f(n-m,m)种;如果n-m<m,则f(n-m,m)为0，所以条件②不能省略

综上所述方程：

1 当m==1 或者 n==m 时

f( n,m) = 0 当m>n时

f（n-1,m-1）+f(n-m,m) 当n>m时

**python源代码：**

#整数划分变形问题
    def huafen(n,m):  #n为整数，m为每次划分的整数个数
        if(m==1 or n==m):
            return 1
        elif(m>n):   #当m>n时
            return 0
        else:
            return huafen(n-1,m-1)+huafen(n-m,m)   #选取至少有一个1和不选取1的种数
    a=[]
    t=0
    def digui(sum,k,m,l,q):
        global a
        global t
        if(sum>l):
            return
        elif(k==q and sum==l):
            t+=1
            print("第",t,"种：")
            for x in range(len(a)-1):
                print(str(a[x])+"+",end="")
            print(a[-1])
            
        else:
            c=range(m)
            for y in reversed(c):
                y+=1
                sum+=y
                a.append(y)
                digui(sum,k+1,y,l,q)   
                a.pop()
                sum-=y
    
    def main():
        v,g=map(int,input("请输入两个以空格隔开的数：").split())  #整数v,和每次划分的整数个数g
        p=huafen(v,g)  
        print("该整数的划分一共有"+str(p)+"种")
        print("所有的划分如下：")
        digui(0,0,v,v,g)
    main()

**运行结果如下：**

**![20201017190133944.png][]**

#### 三.变形3 ####

如果n划分成若干个奇正整数之和 ,则这样有多少种划分？

（f(n,m)代表有多少种划分，其中n为整数，m为不大于n的最大整数的划分）

**分析：**①当m==1时，只有一种划分，即\{1，1,...1\}

②当m为奇数时：根据m和n的关系可以分成三种情况

a.当n<m时，则有f(n,n)种划分

b.当n==m时，根据是否选取最大整数m，可以分成两种情况

\*选取最大奇整数m,则只有一种划分，即\{m\}

\*不选取最大奇整数m,则共有f(n,m-2)种划分

c.当n>m时，根据是否选取最大整数m，可以分成两种情况

\*选取最大奇整数m,则共有f(n-m,m)种划分

\*不选取最大奇整数m,则共有f(n,m-2)种划分

③当m为偶数时：根据m和n的关系可以分成三种情况：

a.当n<m时，可以分成两类:（m为偶数，则m-1为最大奇数）

\*当n<m-1时，则共有f(n,n)种划分

\*当n==m-1时，则共有f（n，m-1）种划分

b.当n==m时，则共有f(n,m-1)种划分

c.当n>m时，根据是否选取最大奇整数m-1，可以分成两种情况

\*选取最大奇整数m-1,则共有f(n-m+1,m-1)种划分

\*不选取最大奇整数m-1,则共有f(n,m-3)种划分

python源代码：

def huafen(n,m):  #n为整数，huafen(n,m)代表：m为划分的最大整数共有多少种，m<=n
        if(m==1):  #若m==1
            return 1
        elif (m%2):  #若m为奇数
            if(n<m):  #n<m
                return huafen(n,n)
            elif(n==m):   #是否选取最大奇整数m
                return 1+huafen(n,m-2)
            else:    #是否选取最大奇整数m
                return huafen(n-m,m)+huafen(n,m-2)
        else:  #若m为偶数
            if(n<m):
                if(n<m-1):
                    return huafen(n,n)
                else:
                    return huafen(n,m-1)
            elif(n==m):
                return huafen(n,m-1)
            else:   #是否选取最大奇整数m-1
                return huafen(n-m+1,m-1)+huafen(n,m-3)
    a=[]
    t=0
    def digui(sum,k,m,l):
        global a
        global t
        if(sum>l):
            return
        elif(sum==l):
            flg=1
            for x in a:   #在原问题答案的基础下，挑选出整数全部都是偶数的列表
                if(x%2==0):
                    flg=-1
                    break
            if(flg==1):
                t+=1
                print("第",t,"种：")
                for x in range(len(a)-1):
                    print(str(a[x])+"+",end="")
                print(a[-1])
            
        else:
            c=range(m)
            for y in reversed(c):
                y+=1
                sum+=y
                a.append(y)
                digui(sum,k+1,y,l)
                a.pop()
                sum-=y
    
    def main():
        print("请输入一个整数：")
        v=int(input())
        p=huafen(v,v)
        print("该整数的划分一共有"+str(p)+"种")
        print("所有的划分如下：")
        digui(0,0,v,v)
    main()

运行结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hnbnV4Y18xOTkz_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hnbnV4Y18xOTkz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201017095347352.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hnbnV4Y18xOTkz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hnbnV4Y18xOTkz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/202010171040122.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hnbnV4Y18xOTkz,size_16,color_FFFFFF,t_70
[20201017110801598.png]: https://img-blog.csdnimg.cn/20201017110801598.png
[20201017190133944.png]: https://img-blog.csdnimg.cn/20201017190133944.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hnbnV4Y18xOTkz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201018002903731.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hnbnV4Y18xOTkz,size_16,color_FFFFFF,t_70