分解（一）

輸入自然數n（n<100），輸出所有和的形式。不能重復。
如：4=1+1+2；4=1+2+1;4=2+1+1 屬于一種分解形式。
樣例輸入：
7
輸出：
1:7=1+6
2:7=1+1+5
3:7=1+1+1+4
4:7=1+1+1+1+3
5:7=1+1+1+1+1+2
6:7=1+1+1+1+1+1+1
7:7=1+1+1+2+2
8:7=1+1+2+3
9:7=1+2+4
10:7=1+2+2+2
11:7=1+3+3
12:7=2+5
13:7=2+2+3
14:7=3+4

?

這道題當時我確實是做出來了，但是分解的順序不對，結果自然就GG了。

?

這道題的分解思路是一直分解最后一個數，而且為了避免重復，分解的得到的數一定是嚴格遞增的，所以遞歸邊界就是后一個數小于等于前面的數的時候。

但這并不是這道題的難點，而是在于搜索域。回想一下其他類型的搜索題目，搜索域都是一定的，只不過下一步的判斷條件不同。而這道題這一步分解的數的搜索域受前面的數的影響，搜索域是時刻在改變的。

那么搜索域改變會導致什么結果呢？就是無法建圖，因為圖中的結點是不固定的。這樣的話就只能試著畫出搜索樹了。

根據遞歸的規則：不斷分解最后一個數，直到分解出來的前一個數小于等于后一個數，以n=7為例畫出搜索樹：

?

理論上這樣代碼就能寫出來了，但每一步都要改變上一步的值，跟常規的搜索不太一樣，所以我就才用了另一種寫法：

很顯然，對于每一次的分解，最后一個數一定是n減去前面數的和，所以只用枚舉倒數第二個數就行了。那么接下來要確定的就是這個數的搜索域：

首先最后兩個數的和一定等于n減去前面的數的和，我們不妨設倒數第二個數為a，最后一個數為b，前面的數的和為sum，存答案的數組ans[]，又因為整個分解序列嚴格遞增，那么a必須滿足a>=ans[step-1] && a <= b。那么第step步的a的搜索域就是

　　　　　ans[step-1] 到 (n-sum)/2

?

然后提一下遞歸邊界

　　　　　if(n - sum - ans[step] <= 1) return;

?

1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 #define rep(i, a, n) for(int i = a; i <= n; ++i) 8 #define per(i, n, a) for(int i = n; i >= a; --i) 9 typedef long long ll; 10 int n, ans[105], tot = 0, sum = 0; 11 void print(int tot, int step, int sum) 12 { 13 printf("%d:%d=", tot, n); 14 rep(i, 1, step) printf("%d+", ans[i]); 15 printf("%d\n", n - sum); //最后一個數 16 } 17 void dfs(int step) 18 { 19 if(n - sum - ans[step] <= 1) return; 20 rep(i, ans[step - 1], (n - sum) >> 1) //此時的sum是不包括后兩個數的和 21 { 22 sum += i; //此時的sum就變成了不包括最后一個數的和 23 ans[step] = i; 24 print(++tot, step, sum); 25 dfs(step + 1); 26 sum -= i; 27 } 28 } 29 int main() 30 { 31 // freopen("p6.in", "r", stdin); 32 // freopen("p6.out", "w", stdout); 33 scanf("%d", &n); 34 ans[0] = 1; //特別強調，若默認ans[0]=0的話，分解的結果就會出現7=0+...的情況 35 dfs(1); 36 return 0; 37 }

?

?

?

分解（二）

若規定每一項不大于m呢？

?

只要加兩個特判

for(int i = ans[step - 1]; i <= ((n - sum) >> 1) && i <= k; ++i)　　表示倒數第二個數不大于m

{

。。。

if(n - sum <= k) print(++tot, step, sum);　　　　表示最后一個數不大于m　　

。。。

}

?

?

分解（三）

如規定項數不大于m呢？

一個特判就夠

在dfs開頭　　 if(step >= k) return;

注意，是step >= k 的時候，而不是step > k時，因為這個寫法時枚舉倒數第二個數，到最后一個數時的項數大于k就是到倒數第二個數時的項數大于等于k。

?

轉載于:https://www.cnblogs.com/mrclr/p/8638462.html

總結

以上是生活随笔為你收集整理的分解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。