请教大家这道题如何解
由a b c 组成的n位字符串中不出现图像aa的字符串数目共有多少？ 要分类吧，应该分类 然后求和 我想是这样的 最终是个数列题 我看是不是可以化归为考虑n组三元数组的问题了 递推求解啊，。。。。 本帖最后由 DreaMathing 于 2009-8-12 14:10 编辑我在想可以从a出现的次数上考虑，试图找到通项公式。
k=n时，a出现一次，一共有n×2*(n-1)种情况，
a出现两次，一共有Cn2-(n-1) 种情况，
a出现三次，一共有[(n-4)+(n-5)+...+1]+[(n-5)+(n-6)+...+1]+...+1再加上k=n-1时a出现三次的情况数，
a出现四次，一共有[(n-6)+(n-7)+...+1]+[(n-7)+(n-8)+...+1]+[(n-8)+(n-9)+...+1]+...+1再加上k=n-1时a出现四次的情况数，
......
n为偶数时，a最多出现n/2次，n为奇数时，a最多出现(n+1)/2次
再整理一下，递推式是出得来的吧，然后就好求了。 设n位字符有Sn种,则可以得到递推公式
Sn=3*S(n-1)+2S(n-3)
S1=3
S2=9
S3=22
解特征方程即可.
递推公式是这样来的:要排N个数,只需要先把前面N-1个数排好,后面再排一个数即可,但是当第N-1个数是A的时候,第N位不能是A,第N-1位是A,第N-2位一定不是A,所以只要前面N-3位按要求排好,第N-2位只能是B或C,有2S(n-3)种 设n位字符有Sn种,则可以得到递推公式
Sn=2*S(n-1)+2*S(n-2)
要排N个数,先排最高位,最高位如果是,b或c,则只要后面n-1位没有aa就行,也就是s(n-1),如果首位放a,则第二位只能放b,或c,余下的n-2位没有aa就行.所以递推公式为Sn=2*S(n-1)+2*S(n-2)
S(1)=3,S(2)=8,s(3)=22.....依次下去! 楼主这道题是特定子串的研究范围，请去阅读<Combinatorial Enumeration> Goulden，里面的一节用两种生成函数与组合簇的方法，解决了所有的特定子串问题。
还有楼上给了递归公式是没错，但是要找解析解非常的麻烦。而且如果需要的图案和要求一多，比如要求出含有bababbc和abbcaba的所有长度为n的串，在这种两个图案都可以重复甚至可以以多种方式重复的情况下，离散的递归方法是不可行的。 很好的一道题目呀，有难度但很有意思，特容易实现解答 很好的一道题目呀，有难度但很有意思，特容易实现解答
页:
[1]
2