簡(jiǎn)述

用一系列正整數(shù)之和來(lái)表示一個(gè)整數(shù)，稱(chēng)之為整數(shù)劃分。而整數(shù)劃分問(wèn)題則對(duì)于某個(gè)數(shù)字，輸出對(duì)應(yīng)整數(shù)劃分的數(shù)量。
先寫(xiě)遞歸，有了遞歸之后，就換用遞推來(lái)加快速度。

算法思路

• q(n, m)表示，n這個(gè)整數(shù)被劃分，其中最大可能整數(shù)是m的所有劃分情況數(shù)目。明顯，所求，即為q(n,n)
• 當(dāng)m>n時(shí)，明顯有 q(n, m) = q(n, n)。因?yàn)?#xff0c;保證了所有整數(shù)都必須是大于等于1的。所以，限制再高的上限都沒(méi)有任何的意義。
• 當(dāng)m=n時(shí)候，明顯有兩種劃分，第一種就是全部拿走，另一種就是不全部拿走，那最大可能即為n-1。即，q(n,n) = 1+q(n, n-1)。
• 當(dāng)m<n時(shí)候，同之前的方法類(lèi)似。要么是不拿走當(dāng)前最大值的可能，要么就是拿走最大值的。即，q(n, m) = q(n, m-1) + q(n-m, m)

為什么需要考慮后面的兩種分開(kāi)，主要是為了避免n==0 (n-m == 0)的時(shí)候需要求解。

遞歸

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

遞推求解

#include <iostream> using namespace std;unsigned int** arr;void cal(int n){arr = new unsigned*[n+1];for (int i = 0; i <= n; ++i) arr[i] = new unsigned[n+1];for (int i = 1; i <= n; ++i) arr[i][1] = 1; // max number equal to 1// arr[i][j] 表示i這個(gè)數(shù)被劃分時(shí)，最大可能的數(shù)為j的所有可能。for (int i = 1; i <= n; ++i)for (int j = 2; j <= n; ++j)if (i < j) arr[i][j] = arr[i][i];else if (i == j) arr[i][j] = 1 + arr[i][j-1];else arr[i][j] = arr[i][j-1] + arr[i-j][j]; cout << arr[n][n]<< endl;for (int i = 0; i <= n; ++i) delete []arr[i];delete [] arr; }int main(){int n;while(cin >> n && n >= 1)cal(n); }

遞歸方式以及路徑輸出

#include <iostream> using namespace std; #include <string>void cal(int n, int m, string s){if (n == 0 || m == 0) return;if (n==1||m==1) {for (int i = 0; i < n-1; ++i) s += string("1+");cout << s<< "1\n";return;}if (m > n){return cal(n, n, s); } if (n==m) {cout << s<< n<< endl;return cal(n, m-1, s);}if (n-m != 0)cal(n-m, m, s + to_string(m) + string("+"));else {cout << s<< m<< endl;}cal(n, m-1, s); }int main(){int n;string s;while(cin >> n && n >= 1)cal(n, n, s); }

總結(jié)

以上是生活随笔為你收集整理的整数划分问题【递归以及递推求解方式】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。