Re: [問題] 請問一下有關數字的排列組合(已使用動먠…
※ 引述《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兩個
另一個想法. 原問題是求任一數值拆解成多個不大於3的正整數之和.
反過來想,把問題解為另一個意思相同的問題:
求多個不大於3的正整數數字序列,使總和為指定數值.
演算法改成:
goal number: N, range: {1, 2, 3}
cases <- [[]]
// [[]]: a list containing an empty list.
while not every case is finished, do:
// every case is finished:
// A finished case ends up with a special sign, such as 0.
Copy all cases three-fold.
Append every number in the range {1, 2, 3} to each copy of cases.
Reject any case that sums up to exceed N.
// Remove the exceeding case from cases.
Mark any case that sums up to N with a `done' sign:
for example, let it finish by appending a zero.
最後 cases 全部都是有0結尾,已經完成的序列, 並且每個 case 總和是 N.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.210.84
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：