作者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