7-37 整數(shù)分解為若干項之和 (20 分)
將一個正整數(shù)N分解成幾個正整數(shù)相加，可以有多種分解方法，例如7=6+1，7=5+2，7=5+1+1，…。編程求出正整數(shù)N的所有整數(shù)分解式子。
輸入格式：
每個輸入包含一個測試用例，即正整數(shù)N (0<N≤30)。
輸出格式：
按遞增順序輸出N的所有整數(shù)分解式子。
遞增順序是指：對于兩個分解序列 N1 = {n1,n2,?} 和 N2 = {m1,m2,?}
若存在 i 使得 n1 = m1 , ? , ni = mi，但是 ni+1 < mi+1 ,則 N1 序列必定在 N2 序列之前輸出。
每個式子由小到大相加，式子間用分號隔開，且每輸出4個式子后換行。
輸入樣例：
7
輸出樣例：
7=1+1+1+1+1+1+1;7=1+1+1+1+1+2;7=1+1+1+1+3;7=1+1+1+2+2
7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2
7=1+2+4;7=1+3+3;7=1+6;7=2+2+3
7=2+5;7=3+4;7=7
解題思路
這個題目很顯然應(yīng)該用遞歸的想法去做，但是退出條件和遞歸式子還需要仔細(xì)琢磨。
先做例子分析F(5)的結(jié)構(gòu)
可以看到，數(shù)字始終是呈現(xiàn)遞增的形式，無論是上下還是左右，都是后面的數(shù)字比前面的數(shù)字更大。
而且 第1位 數(shù)除了其本身，都不會超過 F(n) 中的 n/2 ，然后就是一種n的本身的特殊情況。
如果我們把第一位數(shù)設(shè)為 i ，將從 i 開始的 F(n)，記為 F(n , i )
那么 F(5) 就可以拆分成 F(5,1) , F(5,2) ，F(xiàn)(5,5)三種情況。
F(5,1) 又可以看成是 1 + F(4) , F(4) 則可以看成 F(4,1) , F(4,2) , F(4,4) ...
又或者可以看成是 2 + F(3,2) , F(3,2) 可以拆分為 F(3,3) 因為 F(3,2) 的從 2 開始，而 2 > 2/3，所以舍去了，...
根據(jù)以上觀察可以發(fā)現(xiàn)，只有在 F(n,n)的時候，條件才會結(jié)束，并且最后的那一位數(shù)字就是 n ,而前面的那一串加法數(shù)與上一級相同。
所以我們可以把上一級的前面那一串加法數(shù)，傳到本級，然后決定在末尾加上 a+ 以后傳遞到下級，或者是直接輸出。
于是式子被改造成F(n , i , str) , n 就是需要求式子的和數(shù)，i 就是本級運算需要放在式子第一位的最小數(shù)字，str就是上一級傳下來的需要被輸出的字符串，即圖中 1+1+F(2,2) 中的 '1+1+' ，2+F(3,2) 的 該式子寫法就是 F(3,2, '2+')。
我這么寫可能理解起來有些困難，我還是直接放代碼吧，配合代碼理解起來應(yīng)該會更容易。
代碼不多，主要算法代碼只有十幾行。
最終答案
def main():
# 輸入，起始條件
n = int(input())
f(n,1,str(n)+'=')
#計數(shù)換行，全局變量
count = 0
def f(n, startnum,out=''):
global count
# 遞歸，從 startnum ,到 n/2 取整 ，range()特性 +1
# 用 out字符串 來存儲前面的數(shù)字，outmp是當(dāng)前式子用的，輸出即棄用
for i in range(startnum,n//2 + 1):
outmp = out
outmp += str(i) + '+'
f(n-i,i,outmp)
# 退出條件就是 startnum == n,把前面的 out字符串 輸出，然后 n 直接輸出在末尾就行
# 判斷是否換行，最后一個沒有';'，用是否包含 '+' 取了巧規(guī)避了
# 由于這是最后一位數(shù)，所以也能控制 '+' 不會添加在末尾
if n == startnum:
print(out + str(n),end='')
count += 1
if (count % 4) ==0:
print()
elif '+' in out:
print(';',end='')
return
# 最后當(dāng)然還要輸出一個前面沒有加和的整數(shù)
# if startnum < n:
f(n,n,out)
main()
參考資料
感謝以下資料在解決該問題時提供的幫助，大家也可以參考看看。
這篇是遞歸方式
7-37 整數(shù)分解為若干項之和（20 分）- lingr7
這篇用了遞推方式
PTA_數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)與實驗指導(dǎo)_題解_2-2.5 整數(shù)分解為若干項之和 - 滿眼星辰
