作者yauhh (喲)
看板Prob_Solve
標題Re: [問題] 請問一下有關數字的排列組合
時間Thu Aug 12 05:49:24 2010
※ 引述《linkone (小豆豆)》之銘言：
: 例如 2的話 有 2 1+1 這兩種組合
: 3的話 有 3 1+1+1 1+2 2+1 .....
: 請問如果數字在大一點我如何可以計算出這種排列組合
: 而且還必須知道此組合內有幾個1 像1+1+1裡有三個1
: 1+2裡有1個1 這樣. 我想了兩三天想不出來= =
: ps:組合的數字不能超過3 例如: 8的話不能 4+4 OR 5+3 ... 只能 3+3+2這樣
: 或是看能不能計算出 組合裡面沒有1這個數字的個數有幾個 像5的話就有2+3 3+2兩個
如果用 f(N) -> 1+f(N-1) 這一類的遞迴函數拆,應該都會出現重覆值,
特別是 1+1+1+1+....+1 重覆得最多.
可以反用打散並局部合併方式把答案建立出來.
把指定數字 N 拆為 [1,1,1,...,1] , N 個 1 的序列.
然後用遞迴函數 b([1,1,1,...,1]) 取解. b 的定義為:
list of array b (Array a = [a_1, a_2, a_3,..., a_n]):
if length of a = 1
return [a]
// [a]:
// An array containing only a.
if no ajacent elements are combinable
// No ajacent elements sum to a number less than or equivalent to 3.
return [a]
result <- [a]
for i = 1 to (length of a - 1)
append combine(a, a[i], a[i+1], output z) to result
// combine(a, a[i], a[i+1], output z):
// Let a[i] = a[i]+a[i+1], and then remove a[i+1].
b(z)
return result
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.108.129
※ 編輯: yauhh 來自: 218.160.108.129 (08/12 05:56)
1F：推 LPH66:這樣的話 [1,2,1,1]=>[1,3,1] 和 [1,1,2,1]=>[1,3,1] 的重覆 08/12 08:22
2F：→ LPH66:要怎麼辦? 總不能一直對 result 刪除重覆吧... 08/12 08:22
3F：→ yauhh:我錯了,這個方法跟f(N)->解一樣是有重覆的...計算分支的裁 08/12 19:05
4F：→ yauhh:切還是必須做的動作. 待會另貼其他解. 08/12 19:06