C語言之整數(shù)劃分問題（遞歸法）實(shí)例代碼

更新時(shí)間：2017年02月27日 15:02:09 投稿：lqh

這篇文章主要介紹了C語言之整數(shù)劃分問題（遞歸法）實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下

C語言之整數(shù)劃分問題（遞歸法）實(shí)例代碼

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

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

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

例如但n=4時(shí)，他有5個(gè)劃分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};

注意4=1+3 和 4=3+1被認(rèn)為是同一個(gè)劃分。

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

1.遞歸法：

根據(jù)n和m的關(guān)系，考慮以下幾種情況：

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

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

(3)當(dāng)n=m時(shí)，根據(jù)劃分中是否包含n，可以分為兩種情況：

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

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

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

(4)當(dāng)n<m時(shí)，由于劃分中不可能出現(xiàn)負(fù)數(shù)，因此就相當(dāng)于f(n,n);

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

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

為f(n-m,m)

(b)劃分中不包含m的情況，則劃分中所有值都比m小，即n的(m-1)劃分，個(gè)數(shù)為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;
}

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

您可能感興趣的文章:

相關(guān)文章

深入了解C語言中的const和指針
這篇文章將具體為大家介紹一下C語言中const和指針的使用，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)const和指針有一定幫助，需要的可以參考一下
2022-02-02
單鏈表實(shí)現(xiàn)反轉(zhuǎn)的3種方法示例代碼
單鏈表的反轉(zhuǎn)是常見的面試題目，下面這篇文章主要給大家介紹了關(guān)于單鏈表實(shí)現(xiàn)反轉(zhuǎn)的3種方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧
2019-02-02
C++ 多線程編程建議之 C++ 對多線程/并發(fā)的支持（下）
這篇文章主要介紹的是 C++ 多線程編程建議之 C++ 對多線程/并發(fā)的支持的相關(guān)資料，承接前文現(xiàn)代 C++ 對多線程/并發(fā)的支持，接下來我們看看回發(fā)生什么吧
2021-10-10
c++如何分割字符串示例代碼
因?yàn)閏++字符串沒有split函數(shù)，所以字符串分割單詞的時(shí)候必須自己手寫，也相當(dāng)于自己實(shí)現(xiàn)一個(gè)split函數(shù)吧！下面跟小編一起來看看如何實(shí)現(xiàn)這個(gè)功能。
2016-08-08
使用C語言操作樹莓派GPIO的詳細(xì)步驟
今天抽空給大家普及使用C語言操作樹莓派GPIO的詳細(xì)步驟，本文大概分五步給大家介紹樹莓派GPIO安裝步驟，首先需要安裝GPIO庫然后進(jìn)行一步步設(shè)置，具體操作方法跟隨小編一起學(xué)習(xí)吧
2021-06-06
C++ cin.get用法案例詳解
這篇文章主要介紹了C++ cin.get用法案例詳解,本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
2021-08-08
C++實(shí)現(xiàn)快速排序(Quicksort)算法
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)快速排序(Quicksort)算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-04-04
C語言中#pragma?pack(1)的用法與注意點(diǎn)
#pragma用于指示編譯器完成一些特定的動(dòng)作,下面這篇文章主要給大家介紹了關(guān)于C語言中#pragma?pack(1)的用法與注意點(diǎn)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
2023-02-02
C語言數(shù)組超詳細(xì)講解下篇掃雷
數(shù)組是一組有序的數(shù)據(jù)的集合，本篇將帶你結(jié)合數(shù)組來實(shí)現(xiàn)掃雷小游戲，上手實(shí)練更快的能夠掌握數(shù)組使用，感興趣的朋友來看看吧
2022-04-04
用C語言舉例講解數(shù)據(jù)結(jié)構(gòu)中的算法復(fù)雜度結(jié)與順序表
這篇文章主要介紹了講解數(shù)據(jù)結(jié)構(gòu)中的算法復(fù)雜度結(jié)與順序表的C語言版示例,包括對時(shí)間復(fù)雜度和空間復(fù)雜度等概念的簡單講解,需要的朋友可以參考下
2016-02-02