作者yauhh (哟)
看板Prob_Solve
标题Re: [问题] 请问一下有关数字的排列组合(已使用动먠…
时间Thu Aug 12 22:32:10 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两个
另一个想法. 原问题是求任一数值拆解成多个不大於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