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