C語言中整數劃分的示例分析

這篇文章主要介紹了C語言中整數劃分的示例分析，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

C語言之整數劃分問題（遞歸法）實例代碼

整數劃分問題是算法中的一個經典命題之一，有關這個問題的講述在講解到遞歸時基本都將涉及。所謂整數劃分，是指把一個正整數n寫成如下形式：

    n=m1+m2+...+mi; （其中mi為正整數，并且1 <= mi <= n），則{m1,m2,...,mi}為n的一個劃分。

如果{m1,m2,...,mi}中的最大值不超過m，即max(m1,m2,...,mi)<=m，則稱它屬于n的一個m劃分。這里我們記n的m劃分的個數為f(n,m);

例如但n=4時，他有5個劃分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};

注意4=1+3 和 4=3+1被認為是同一個劃分。

該問題是求出n的所有劃分個數，即f(n, n)。下面我們考慮求f(n,m)的方法;

1.遞歸法：

   根據n和m的關系，考慮以下幾種情況：

   (1)當n=1時，不論m的值為多少（m>0)，只有一種劃分即{1};

   (2)當m=1時，不論n的值為多少，只有一種劃分即n個1，{1,1,1,...,1};

   (3)當n=m時，根據劃分中是否包含n，可以分為兩種情況：

      (a)劃分中包含n的情況，只有一個即{n}；

      (b)劃分中不包含n的情況，這時劃分中最大的數字也一定比n小，即n的所有(n-1)劃分。

      因此 f(n,n) =1 + f(n,n-1);

   (4)當n<m時，由于劃分中不可能出現負數，因此就相當于f(n,n);

   (5)但n>m時，根據劃分中是否包含最大值m，可以分為兩種情況：

       (a)劃分中包含m的情況，即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和為n-m，因此這情況下

          為f(n-m,m)

       (b)劃分中不包含m的情況，則劃分中所有值都比m小，即n的(m-1)劃分，個數為f(n,m-1);

      因此 f(n, m) = f(n-m, m)+f(n,m-1);

      綜上所述：

   f(n, m)=  1;       (n=1 or 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)

#include<iostream>
using namespace std;

int equationCount(int n,int m)
{
  if(n==1||m==1)
    return 1;
  else if(n<m)
    return equationCount(n,n);
  else if(n==m)
    return 1+equationCount(n,n-1);
  else
    return equationCount(n,m-1)+equationCount(n-m,m);
}

int main(void)
{
  int n;
  while(scanf("%d",&n)!=EOF&&(n>=1&&n<=120))
  {
    printf("%d\n",equationCount(n,n));
  }
  return 0;
}

感謝你能夠認真閱讀完這篇文章，希望小編分享的“C語言中整數劃分的示例分析”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!