C語言之整數(shù)劃分問題（遞歸法）實例代碼
C語言之整數(shù)劃分問題（遞歸法）實例代碼
整數(shù)劃分問題是算法中的一個經(jīng)典命題之一，有關(guān)這個問題的講述在講解到遞歸時基本都將涉及。所謂整數(shù)劃分，是指把一個正整數(shù)n寫成如下形式：
n=m1+m2+...+mi; （其中mi為正整數(shù)，并且1 <= mi <= n），則{m1,m2,...,mi}為n的一個劃分。
如果{m1,m2,...,mi}中的最大值不超過m，即max(m1,m2,...,mi)<=m，則稱它屬于n的一個m劃分。這里我們記n的m劃分的個數(shù)為f(n,m);
例如但n=4時，他有5個劃分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};
注意4=1+3 和 4=3+1被認(rèn)為是同一個劃分。
該問題是求出n的所有劃分個數(shù)，即f(n, n)。下面我們考慮求f(n,m)的方法;
1.遞歸法：
根據(jù)n和m的關(guān)系，考慮以下幾種情況：
(1)當(dāng)n=1時，不論m的值為多少（m>0)，只有一種劃分即{1};
(2)當(dāng)m=1時，不論n的值為多少，只有一種劃分即n個1，{1,1,1,...,1};
(3)當(dāng)n=m時，根據(jù)劃分中是否包含n，可以分為兩種情況：
(a)劃分中包含n的情況，只有一個即{n}；
(b)劃分中不包含n的情況，這時劃分中最大的數(shù)字也一定比n小，即n的所有(n-1)劃分。
因此 f(n,n) =1 + f(n,n-1);
(4)當(dāng)n<m時，由于劃分中不可能出現(xiàn)負(fù)數(shù)，因此就相當(dāng)于f(n,n);
(5)但n>m時，根據(jù)劃分中是否包含最大值m，可以分為兩種情況：
(a)劃分中包含m的情況，即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和為n-m，因此這情況下
為f(n-m,m)
(b)劃分中不包含m的情況，則劃分中所有值都比m小，即n的(m-1)劃分，個數(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)文章
在應(yīng)用程序開發(fā)時經(jīng)常會遇到數(shù)據(jù)分頁的需求,每一頁展示特定數(shù)量的數(shù)據(jù),通過點擊按鈕翻頁或者輸入頁碼跳轉(zhuǎn)到指定頁,本文就來介紹一下Qt 自定義分頁控件的實現(xiàn),感興趣的可以了解一下2023-11-11
C++中memcpy函數(shù)的使用以及模擬實現(xiàn)
memcpy是c和c++使用的內(nèi)存拷貝函數(shù)，本文主要介紹了C++中memcpy函數(shù)的使用以及模擬實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07
學(xué)習(xí)了這么多年C語言，說實話對宏自以為了如指掌了，沒想到看內(nèi)核代碼的時候還是那么吃力，設(shè)備驅(qū)動代碼中有很多這樣或者那樣的宏定義，各種define，在學(xué)習(xí)的過程中將C語言中所出現(xiàn)的#define定義整理總結(jié)了一下，供大家借鑒和學(xué)習(xí)。2016-01-01
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)線性代數(shù)矩陣行簡化，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
這篇文章主要介紹了C語言判斷回文數(shù)的小例子，有需要的朋友可以參考一下2014-01-01
這篇文章主要為大家詳細(xì)介紹了C++判斷一個點是否在圓內(nèi)的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-05-05
從比較簡單的層面來看，智能指針是RAII(Resource Acquisition Is Initialization，資源獲取即初始化)機制對普通指針進(jìn)行的一層封裝。這樣使得智能指針的行為動作像一個指針，本質(zhì)上卻是一個對象，這樣可以方便管理一個對象的生命周期2022-08-08
這篇文章主要介紹了使用C語言求解撲克牌的順子及n個骰子的點數(shù)問題的方法,解答實例主要為了突出解題的算法,需要的朋友可以參考下2016-03-03
iniparser是針對INI文件的解析器。ini文件則是一些系統(tǒng)或者軟件的配置文件。本文就來介紹一下如何利用Iniparser庫實現(xiàn)ini文件讀寫吧2023-03-03
QTimer是Qt中的定時器類,用于執(zhí)行定時操作,如在一段時間間隔后觸發(fā)某個槽函數(shù)或執(zhí)行特定的代碼,下面就來介紹一下Qt之QTimer使用及技巧小結(jié),感興趣的可以了解一下2023-10-10