数学建模社区-数学中国

标题: 请教大家这道题如何解 [打印本页]

作者: xiangyunl 时间: 2009-4-19 20:56
标题: 请教大家这道题如何解
由a b c 组成的n位字符串中不出现图像aa的字符串数目共有多少？

作者: liujiandong 时间: 2009-5-7 11:22
要分类吧，应该分类然后求和我想是这样的最终是个数列题

作者: liujiandong 时间: 2009-5-7 11:29
我看是不是可以化归为考虑n组三元数组的问题了

作者: xuxiaolong 时间: 2009-6-14 15:19
递推求解啊，。。。。

作者: DreaMathing 时间: 2009-8-12 14:09
本帖最后由 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次
再整理一下，递推式是出得来的吧，然后就好求了。

作者: jtdu007 时间: 2009-9-15 16:50
设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)种

作者: muaqin 时间: 2009-9-16 11:09
设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.....依次下去!

作者: 索路最高 时间: 2010-3-27 04:16
楼主这道题是特定子串的研究范围，请去阅读<Combinatorial Enumeration> Goulden，里面的一节用两种生成函数与组合簇的方法，解决了所有的特定子串问题。
还有楼上给了递归公式是没错，但是要找解析解非常的麻烦。而且如果需要的图案和要求一多，比如要求出含有bababbc和abbcaba的所有长度为n的串，在这种两个图案都可以重复甚至可以以多种方式重复的情况下，离散的递归方法是不可行的。

作者: l0ivesuxing 时间: 2010-4-11 20:44
很好的一道题目呀，有难度但很有意思，特容易实现解答

作者: l0ivesuxing 时间: 2010-4-11 20:45
很好的一道题目呀，有难度但很有意思，特容易实现解答

作者: iminto 时间: 2010-4-15 12:39
很好的一道题，该眼珠下下，哈哈

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)