l***r
发帖数: 241 | 1 给一个字符串 A1A2A3..An how may key combinations
for example:
N = 1:
A1 -> A1
N = 2:
A1 -> A1
A2 -> A2
A1A2 -> A1
A1A2 -> A2
A1A2 -> A1A2
证明如果字符串长度是N。 组合的数目是3^n - 2^n | f*******4
发帖数: 64 | 2 g(A_1A_2..A_kA_k+1) = g(A_1A_2..A_k)+g(A_k+1)+g(A_1A_2..A_k).(A_k+1)
= 2*g(A_1..A_k)+1
=> g(A_1..A_k)=2^k-1,记作g(k)
f(A_1..A_k)= g(1)*C(k,1)+..g(i)*C(k,i)+g(k)*C(k,k)
= sigma(2^i * C(k,i)) - sigma(C(k, i))
= (1+2)^k-(1+1)^k | f*****h
发帖数: 10 | 3 a[n+1] = a[n] + 2a[n] + 2^n | c***d
发帖数: 26 | 4 这题啥意思呀？没看懂。什么是key combinations？
没从N＝2的例子里看出规律猜出题意。
能不能给个N＝3的例子？
底下两位回复也没看懂。
【在 l***r 的大作中提到】
: 给一个字符串 A1A2A3..An how may key combinations
: for example:
: N = 1:
: A1 -> A1
: N = 2:
: A1 -> A1
: A2 -> A2
: A1A2 -> A1
: A1A2 -> A2
: A1A2 -> A1A2
| d****n
发帖数: 233 | 5 看了半天， 原来是在考高中（还是初中， 忘了）数学 二项式展开公式。
(m+n)^k = sigma(C(k,i)*m^i*n^(k-i) i = 0… k
g(A_1..A_k)=2^k-1, 可以这样理解:
A1…A_k中每一个要么被选中， 要么不被选， 所以总共是2^k种组合， 需要减去一个
也没有选中的情况。 So。g(A_1..A_k)=2^k-1
比如k = 3：
A1A2A3=> A1
A1A2A3=> A2
A1A2A3=> A3
A1A2A3=> A1A2
A1A2A3=> A1A3
A1A2A3=> A2A3
A1A2A3=> A1A2A3
假设原数组有n个， 那么从n个中选出k个有C（n, k）种可能。 So， 总数是：
f(A_1..A_n)= g(1)*C(n,1)+..g(i)*C(n,i)+g(n)*C(n,n)
= sigma(2^i * C(n,i)) - sigma(C(n, i))
= (1+2)^n-(1+1)^n
【在 c***d 的大作中提到】
: 这题啥意思呀？没看懂。什么是key combinations？
: 没从N＝2的例子里看出规律猜出题意。
: 能不能给个N＝3的例子？
: 底下两位回复也没看懂。
|
|
