m*****f
发帖数: 1243 | 1 已知由字符a, b, c 组成的长度为20的字符串s, 问不含有substring "ab"的s有多少种?
比如 "aaaaaaaaaaaaaaaccccc" 就是一种 |
b****j
发帖数: 78 | 2 递推即可
N[L][x]表示长度为L最后字符为x的不含'ab'的字符串个数
N[L]['a'] = N[L]['c'] = N[L-1]['a'] + N[L-1]['b'] + N[L-1]['c']
N[L]['b'] = N[L-1]['b'] + N[L-1]['c']
种?
【在 m*****f 的大作中提到】
: 已知由字符a, b, c 组成的长度为20的字符串s, 问不含有substring "ab"的s有多少种?
: 比如 "aaaaaaaaaaaaaaaccccc" 就是一种
|
S*********N
发帖数: 6151 | 3
种?
多元排列组合排除法
【在 m*****f 的大作中提到】
: 已知由字符a, b, c 组成的长度为20的字符串s, 问不含有substring "ab"的s有多少种?
: 比如 "aaaaaaaaaaaaaaaccccc" 就是一种
|
g*******y
发帖数: 1930 | 4 correct!
不知道大家发现没有
结果是fibonacci数列
【在 b****j 的大作中提到】
: 递推即可
: N[L][x]表示长度为L最后字符为x的不含'ab'的字符串个数
: N[L]['a'] = N[L]['c'] = N[L-1]['a'] + N[L-1]['b'] + N[L-1]['c']
: N[L]['b'] = N[L-1]['b'] + N[L-1]['c']
:
: 种?
|
g*******y
发帖数: 1930 | 5 你说的是exclusion-inclusion吧
也能做
不过我觉得还是递归的显得巧妙一些
【在 S*********N 的大作中提到】
:
: 种?
: 多元排列组合排除法
|
g*******y
发帖数: 1930 | 6 不知道大家发现没有
结果是fibonacci数列
也就是说，至少有O(logN)的算法
^_^
其实就是这个递归式：
fa[n] = fa[n-1] + fb[n-1] + fc[n-1]
fb[n] = fb[n-1] + fc[n-1]
fc[n] = fa[n-1] + fb[n-1] + fc[n-1]
注意到fc = fa，用fa替换fc
fa[n] = 2*fa[n-1] + fb[n-1]
fb[n] = fa[n-1] + fb[n-1]
起始fa[1] = fb[1] = 1
这样你算算，fb[1],fa[1],fb[2],fa[2],...这个就是fib |
m*****f
发帖数: 1243 | 7 哇, 全被你们发现了.
【在 g*******y 的大作中提到】
: 不知道大家发现没有
: 结果是fibonacci数列
: 也就是说，至少有O(logN)的算法
: ^_^
: 其实就是这个递归式：
: fa[n] = fa[n-1] + fb[n-1] + fc[n-1]
: fb[n] = fb[n-1] + fc[n-1]
: fc[n] = fa[n-1] + fb[n-1] + fc[n-1]
: 注意到fc = fa，用fa替换fc
: fa[n] = 2*fa[n-1] + fb[n-1]
|
g*******y
发帖数: 1930 | 8 呵呵，这个还有点隐蔽啊~
【在 m*****f 的大作中提到】
: 哇, 全被你们发现了.
|
k***e
发帖数: 556 | 9 提一点，为什么要设三个变量
define:
f(n): the # of abc array with length n and contains no ab
g(n): # of length n, begin with a and no ab
then f(n)=g(n）＋ 2f(n-1)
g(n)=g(n-1)+f(n-2)
第二个式子直接可以得到g(n)=sum(f(1)...f(n-2)) + 2
代入前面，用f(n) f(n-1)差一下就可以得到
f(n)=3f(n-1)-f(n-2)
【在 g*******y 的大作中提到】
: 不知道大家发现没有
: 结果是fibonacci数列
: 也就是说，至少有O(logN)的算法
: ^_^
: 其实就是这个递归式：
: fa[n] = fa[n-1] + fb[n-1] + fc[n-1]
: fb[n] = fb[n-1] + fc[n-1]
: fc[n] = fa[n-1] + fb[n-1] + fc[n-1]
: 注意到fc = fa，用fa替换fc
: fa[n] = 2*fa[n-1] + fb[n-1]
|
g*******y
发帖数: 1930 | 10 我是觉得分以a,b,c结尾的三种情况有最简单直接的递推式，然后一看fa跟fc是一模一
样的，然后就剩个二元递推数组了，再一看，很像是fib，再想想，果然是fib
你这个递推式应该也是对的，不过你这个式子，我觉得不是很容易能看出来跟
fibonacci的关系~
【在 k***e 的大作中提到】
: 提一点，为什么要设三个变量
: define:
: f(n): the # of abc array with length n and contains no ab
: g(n): # of length n, begin with a and no ab
: then f(n)=g(n）＋ 2f(n-1)
: g(n)=g(n-1)+f(n-2)
: 第二个式子直接可以得到g(n)=sum(f(1)...f(n-2)) + 2
: 代入前面，用f(n) f(n-1)差一下就可以得到
: f(n)=3f(n-1)-f(n-2)
|
|
|
k***e
发帖数: 556 | 11 那两个roots是1。618和0。618的平方
【在 g*******y 的大作中提到】
: 我是觉得分以a,b,c结尾的三种情况有最简单直接的递推式，然后一看fa跟fc是一模一
: 样的，然后就剩个二元递推数组了，再一看，很像是fib，再想想，果然是fib
: 你这个递推式应该也是对的，不过你这个式子，我觉得不是很容易能看出来跟
: fibonacci的关系~
|
g*******y
发帖数: 1930 | 12 呵呵，也是，更0.618都扯上关系了，肯定跟fib有关系，呵呵
对了，我问你个问题，是不是所有f(n) = a*f(n-1) + b*f(n-2)这类型的递推式，都能够像fib数组一样表示成矩阵乘方从而达到logN的优化
【在 k***e 的大作中提到】
: 那两个roots是1。618和0。618的平方
|
k***e
发帖数: 556 | 13 我觉得是的
就按照 F(n)=(f(n),f(n-1))^T
F(n) = A * F(n-1). where A = ((a, b), (1,0)),
we can always find B such that B^-1AB = ((root_1,0) (root_2,0)).
其实可以直接求出根来算。也可以用矩阵相乘来算来避免float甚至虚数的运算。
能够像fib数组一样表示成矩阵乘方从而达到logN的优化
【在 g*******y 的大作中提到】
: 呵呵，也是，更0.618都扯上关系了，肯定跟fib有关系，呵呵
: 对了，我问你个问题，是不是所有f(n) = a*f(n-1) + b*f(n-2)这类型的递推式，都能够像fib数组一样表示成矩阵乘方从而达到logN的优化
|
g*******y
发帖数: 1930 | 14 我想的也是差不多这样。
btw，你也这么晚还没睡觉？
【在 k***e 的大作中提到】
: 我觉得是的
: 就按照 F(n)=(f(n),f(n-1))^T
: F(n) = A * F(n-1). where A = ((a, b), (1,0)),
: we can always find B such that B^-1AB = ((root_1,0) (root_2,0)).
: 其实可以直接求出根来算。也可以用矩阵相乘来算来避免float甚至虚数的运算。
:
: 能够像fib数组一样表示成矩阵乘方从而达到logN的优化
|
k***e
发帖数: 556 | 15 哈哈 我好不容易排除万难稍微早睡了一点，结果四点醒了就睡不着了。
看了会书，上了会网。你也该睡了吧。 |
r********t
发帖数: 395 | 16 对头。20个位置，所有可能的cases是3^20
至于ab，把它看成一个整体，相当于19个位置，ab可能出现在这19个位置；所以是19*3
^18种可能性。
然后相碱……
【在 S*********N 的大作中提到】
:
: 种?
: 多元排列组合排除法
|
b****j
发帖数: 78 | 17 错的，ababcccccc...c会被减两次
*3
【在 r********t 的大作中提到】
: 对头。20个位置，所有可能的cases是3^20
: 至于ab，把它看成一个整体，相当于19个位置，ab可能出现在这19个位置；所以是19*3
: ^18种可能性。
: 然后相碱……
|
c****p
发帖数: 32 | 18 这个小小修改一下就好了，问题是出在把"ab"当作一个item后，这个会跟其它的重复，
形成：
*ab*(ab)*
所以减一半就好了。
我比较喜欢这种方法，看起来更精巧，有programming pearl的感觉。
【在 b****j 的大作中提到】
: 错的，ababcccccc...c会被减两次
:
: *3
|
b****j
发帖数: 78 | 19 还是错的
abababccccc...
ababababccc...
你可以写个程序试试小的n就知道了
【在 c****p 的大作中提到】
: 这个小小修改一下就好了，问题是出在把"ab"当作一个item后，这个会跟其它的重复，
: 形成：
: *ab*(ab)*
: 所以减一半就好了。
: 我比较喜欢这种方法，看起来更精巧，有programming pearl的感觉。
|
g*******y
发帖数: 1930 | 20 呵呵，你就直接给人家说该用exclusion-inclusion嘛
【在 b****j 的大作中提到】
: 还是错的
: abababccccc...
: ababababccc...
: 你可以写个程序试试小的n就知道了
|
r********t
发帖数: 395 | 21
can I try adding 1+2+3+...10 to the original wrong result?
abab: once more deducted
ababab: twice more...
abababab......
【在 b****j 的大作中提到】
: 还是错的
: abababccccc...
: ababababccc...
: 你可以写个程序试试小的n就知道了
|
b****j
发帖数: 78 | 22 请查阅容斥原理，基本上包含ab的string个数等于:
1 - 2 + 3 - 4 + 5 - 6 ...
【在 r********t 的大作中提到】
:
: can I try adding 1+2+3+...10 to the original wrong result?
: abab: once more deducted
: ababab: twice more...
: abababab......
|
