PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 請問一下有關數字的排列組合

看板Prob_Solve (計算數學 Problem Solving)作者yauhh (喲)時間14年前 (2010/08/12 05:49)推噓1(1推 0噓 3→)

留言4則, 2人參與討論串1/1

※ 引述《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)