递归(二):正整数的拆分

2019-08-16 07:42:41来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

递归(二):正整数的拆分

【例1】求正整数的拆分数。

      将正整数s表示成一系列正整数之和,s=n1+n2+…+nk,其中n1>=n2>=…>=nk, k>=1。正整数s的不同拆分个数称为s的拆分数。例如,正整数6有11种不同的拆分,分别是:

      6;  5+1;  4+2;  4+1+1;  3+3;  3+2+1;   3+1+1+1;

      2+2+2;  2+2+1+1;  2+1+1+1+1;  1+1+1+1+1+1。

      (1)编程思想。

      设m、n均为正整数,m可表示为一些不超过n的正整数之和,f(m,n)为这种表示方式的数目。下面先确定递归关系。

      如果 n>m,则拆分式中n、n-1、…、m+2、m+1这n-m 个数必定不会出现,去掉它们对拆分式的表示数目不产生影响;即    f(m,n) = f(m,m)。

      如果 n=m,则 f(n,m)=1+f(n,n−1)。 其中,“1”表示n的拆分式中只包含n本身,即n=n,只有一种拆分表示;f(n,n−1)表示n的所有其他拆分,即拆分式中最大正整数不超过n−1的拆分数目。

      如果n<m,则  f(n,m)=f(n,m−1)+f(n−m,m)。其中,f(n,m−1)表示拆分式中不包含m的拆分式数目;f(n−m,m)表示拆分式中至少包含一个m的拆分数目,因为如果确定了一个拆分式中包含正整数m,则剩下的部分就是对n−m进行不超过m的拆分。

       确定递归的终止条件。第一个终止条件:f(n,1)=1,表示当拆分式中最大的正整数是1时,该整数n只有一种拆分,即n个1相加。第二个终止条件:f(1,m)=1,表示整数n=1只有一个拆分,不管上限m是多大。

      (2)源程序。

#include <iostream>
using namespace std;
int f(int m,int n)
{
    if(m==1 || n==1)
        return 1 ;
    if(m<n)
        return f(m,m);
    if (m==n)
       return 1+ f(m,n-1);
    return f(m,n-1)+f(m-n, n );
}
int main()
{
    int n, m,k;
    while (cin >>m>>n && n!=0)
    {
         k=f(m,n);
        cout<<k<<endl;
    }
    return 0;
}

【例2】正整数的拆分式。

      正整数s(简称为和数)的拆分是把s分成为某些指定正整数(简称为零数)之和,拆分式中不允许零数重复,且不记零数的次序。

      把指定正整数s拆分为1~m(m<=s)之和,共有多少种不同的拆分方式?输出所有这些拆分式。

      例如,若s=6,m=6,则例1中的11个拆分式只有4个符合本题的要求。即 6;  5+1;  4+2;   3+2+1。

       (1)编程思路。

       由于正整数的拆分与拆分式中各零数的排列顺序无关,因此,可以将正整数s拆分式表示成一系列从大到小排列的正整数之和,即 s=n1+n2+…+nk,其中m>=n1>n2>…>nk>=1, k>=1。

       拆分式中的k个零数都在1~m之间,因此我们需要先解决如何从1~m这m个数中取k(k<m)个数的所有组合。

       设 comb(int a[],int m,int k)为从1~m这m个数中取k个数的所有组合结果。组合的结果保存在数组元素a[1]~a[k]中,数组元素a[0]表示组合结果中元素的个数,显然,a[0]=k。

       为求解comb(int a[],int m,int k),可以先将k个数字组合的第一个数字i放在a[k]中,第一个数字i可以是m,m-1,…,k。注意:第一个数字i不能取k-1,因为后面的数字都会取比第一个数字小的数字,因此最多只能取出1~k-1共k-1个不同的数,达不到取k个数的目的。

       在将确定组合的第一个数字放入数组后,有两种选择:还未确定组合的其余元素时(k>1,即还需取k-1个元素),继续递归comb(a,i-1,k-1)确定组合的其余元素,即在1~i-1中取k-1个数;已确定组合的全部元素时(k==1),输出这个组合。

       实现这一取数组合的递归函数可设计为:

void comb(int a[],int m,int k)
{
    int i,j;
    for (i=m;i>=k;i--)
    {
        a[k]=i;
        if(k>1)
            comb(a,i-1,k-1);
        else
        {
              for (j=a[0];j>=1;j--)
                  cout<<a[j]<<" ";
              cout<<endl;
         }
     }
}

       解决了组合取数后,对所选取的k个数,求其和t并与和数s进行比较:若t=s,即找到一个拆分式,输出拆分式,并设置变量cnt统计拆分式的个数。可将上面的递归函数改写为:

void comb(int a[],int m,int k,int s)   // 加了一个参数s用于传递和数
{
     int i,j,t;
     for (i=m;i>=k;i--)
    {
         a[k]=i;
         if (k>1)
              comb(a,i-1,k-1,s);
         else
         {
                for(t=0,j=a[0];j>0;j--)         // 先计算所取数的和值t
                    t=t+a[j];
                if(t==s)                             //  取数组合的和值等于所求和数s,才输出结果
                {
                      cnt++;

                      cout<<s<<"=";
                      for(j=a[0];j>1;j--)
                           cout<<a[j]<<"+";
                      cout<<a[1]<<endl;
                 }
           }
      }
}

      由于题目要求把指定正整数s拆分为1~m(m<=s)之和,因此拆分式中的数字个数可以为1个,也可以为2个,最多为m个,因此主函数中采用一个循环简单调用递归函数即可:

for (i=1;i<=m;i++)
{
      a[0]=i;
      comb(a,m,i,s);
}

      (2)源程序及运行结果示例。

#include <iostream>

using namespace std;

int cnt=0;

void comb(int a[],int m,int k,int s) 

{

       int i,j,t;

      for(i=m;i>=k;i--)

      {

            a[k]=i;

           if(k>1)

               comb(a,i-1,k-1,s);

           else

              {

               for(t=0,j=a[0];j>0;j--)

                  t=t+a[j];

               if(t==s)

                {

                            cnt++;  cout<<s<<"=";

                            for(j=a[0];j>1;j--)

                                 cout<<a[j]<<"+";

                             cout<<a[1]<<endl;

                 }

              }

       }

}

int main()

{

       int a[100],s,m,i;

       while (cin>>s>>m && s!=0)

       { 

          cnt=0;

          for (i=1;i<=m;i++)

          {

                a[0]=i;

               comb(a,m,i,s);

          }

          cout<<cnt<<endl;

       }

       return 0;

}

        程序运行示例如下:

6 6
6=6
6=5+1
6=4+2
6=3+2+1
4
20 10
20=10+9+1
20=10+8+2
20=10+7+3
20=10+6+4
20=9+8+3
20=9+7+4
20=9+6+5
20=8+7+5
20=10+7+2+1
20=10+6+3+1
20=10+5+4+1
20=10+5+3+2
20=9+8+2+1
20=9+7+3+1
20=9+6+4+1
20=9+6+3+2
20=9+5+4+2
20=8+7+4+1
20=8+7+3+2
20=8+6+5+1
20=8+6+4+2
20=8+5+4+3
20=7+6+5+2
20=7+6+4+3
20=10+4+3+2+1
20=9+5+3+2+1
20=8+6+3+2+1
20=8+5+4+2+1
20=7+6+4+2+1
20=7+5+4+3+1
20=6+5+4+3+2
31
0 0
Press any key to continue

(3)主调函数优化。

        前面给出的主函数中采用一个循环简单调用递归函数。

        for (i=1;i<=m;i++)
        {
             a[0]=i;
             comb(a,m,i,s);
        }

       循环变量i代表拆分式中零数的个数,其范围从1到m。这样会进行大量无效的搜索。

       以程序运行示例中的s=20,m=10进行分析说明。

       要把指定的正整数 20 拆分为1~10之和,主函数中零数个数从1取到10进行搜索。实际上,最大的两个数之和10+9=19小于20,最小的6个数之和 1+2+3+4+5+6=21大于20。也就是说,拆分式中零数的个数只可能是3、4、5这3种情况。因此,前面循环中无需对i的取值1,2,6,7,8,9,10这些情况进行递归处理,而递归的核心是从1~m这m个数中取i个数的进行组合。这样,相当于少处理了C(10,1)+C(10,2)+C(10,6)+C(10,7)+C(10,8)+C(10,9)+C(10,10)=10+45+210+120+45+10+1=441种情况。

       主函数的优化思路是:对于给定的和数s与最大零数m,首先计算拆分式中零数的最少个数min与零数的最多个数max,显然,拆分式中零数的个数I取在区间[min,max]中。

        按这个思路将主函数修改如下:

int main()

{

    int a[100],s,m,i,t,min,max;

    while (cin>>s>>m && s!=0)

   { 

       cnt=0;

       for (t=0,i=1;i<=m;i++)

       {

           t=t+i;

           if (t>s) { max=i-1; break;}

          else if (t==s) { max=i; break; }

       }

       if(i>m)                     // 输入的最大零数太小 

       { 

             cout<<"输入的最大零数太小!1~"<<m<<"的和为"<<t<<",小于"<<s<<endl;

             continue;

       }

       for (t=0,i=1;i<=m;i++)

       {

           t=t+(m-i+1);

           if (t>s) { min=i; break;}

          else if (t==s) { min=i; break; }

      }

     for (i=min;i<=max;i++)

     {

          a[0]=i;

          comb(a,m,i,s);

     }

     cout<<cnt<<endl;

  }

  return 0;

}

【例3】拆分为指定整数之和。

       把指定正整数s拆分为m个指定整数b1,b2…,bm之和,共有多少种不同的拆分法?输出所有这些拆分式。

       例如,输入 零数的个数m=6

       依次由小到大输入指定零数分别为:1,2,3,5,6,9

       输入和数 s=15。

       程序应输出拆分式为:

           15= 9+ 6

           15= 9+ 5+ 1

           15= 9+ 3+ 2+ 1

           15= 6+ 5+ 3+ 1

       (1)编程思路。

      定义一个数组b保存指定的零数。可以在例2程序的基础上,b数组的下标用a数组的值替代。求和过程中把例2程序中对a数组元素的求和 t=t+a[j] 改为对b数组元素求和 t=t+b[a[j]],其中a[j]为b数组的下标。

      (2)源程序。

#include <iostream>

using namespace std;

int cnt=0;

void comb(int a[],int m,int k,int s,int b[]) 

{

    int i,j,t;

    for(i=m;i>=k;i--)

    {

        a[k]=i;

        if(k>1)

           comb(a,i-1,k-1,s,b);

        else

        {

            for(t=0,j=a[0];j>0;j--)

               t=t+b[a[j]];

            if(t==s)

            {

                cnt++;  cout<<s<<"=";

                for(j=a[0];j>1;j--)

                   cout<<b[a[j]]<<"+";

                 cout<<b[a[1]]<<endl;

            }

        }

    }

}

int main()

{

    int a[100],b[100],s,m,i,t,min,max;

    cout<<"输入零数的个数:";

    while (cin>>m && m!=0)

    { 

       cnt=0;

       cout<<"依次由小到大输入指定的整数:";

       for(i=1;i<=m;i++)

           cin>>b[i];

       cout<<"输入和数为:";

       cin>>s;

       for (t=0,i=1;i<=m;i++)

       {

           t=t+b[i];

           if (t>s) { max=i-1; break;}

           else if (t==s) { max=i; break; }

       }

       if(i>m)                  

       {  cout<<"输入的指定整数的和为"<<t<<",小于"<<s<<endl;

          continue;

       }

       for (t=0,i=1;i<=m;i++)

       {

           t=t+b[m-i+1];

           if (t>s) { min=i; break;}

           else if (t==s) { min=i; break; }

       }

       for (i=min;i<=max;i++)

       {

          a[0]=i;

          comb(a,m,i,s,b);

       }

       cout<<cnt<<endl;

    }

    return 0;

}

 


原文链接:https://www.cnblogs.com/cs-whut/p/11086626.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++11智能指针原理和实现

下一篇:C和C++ 变量内存