12 / 2 页下一页

查看: 6964|回复: 11

请教大家这道题如何解

[复制链接]

字体大小: 正常放大

xiangyunl

2 主题	0 听众	403 积分

升级 34.33%

该用户从未签到

群组: 数学趣味、游戏、IQ等

电梯直达

1^#

发表于 2009-4-19 20:56 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

由a b c 组成的n位字符串中不出现图像aa的字符串数目共有多少？

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

liujiandong

2 主题	2 听众	14 积分

升级 9.47%

该用户从未签到

2^#

发表于 2009-5-7 11:22 |只看该作者 |招呼Ta 关注Ta

要分类吧，应该分类然后求和我想是这样的最终是个数列题

我也说一句

发表

使用道具举报

liujiandong

2 主题	2 听众	14 积分

升级 9.47%

该用户从未签到

3^#

发表于 2009-5-7 11:29 |只看该作者 |招呼Ta 关注Ta

我看是不是可以化归为考虑n组三元数组的问题了

我也说一句

发表

使用道具举报

xuxiaolong

9 主题	4 听众	124 积分

升级 12%

TA的每日心情

	郁闷 2012-11-6 13:05

签到天数: 7 天

[LV.3]偶尔看看II

自我介绍: 比较平和，热爱求知，爱好有下棋，看书

4^#

发表于 2009-6-14 15:19 |只看该作者 |招呼Ta 关注Ta

递推求解啊，。。。。

我也说一句

发表

使用道具举报

DreaMathing

0 主题	0 听众	3 积分

升级 60%

该用户从未签到

5^#

发表于 2009-8-12 14:09 |只看该作者 |招呼Ta 关注Ta

本帖最后由 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

0 主题	3 听众	752 积分

TA的每日心情

	奋斗 2021-11-15 21:08

签到天数: 33 天

[LV.5]常住居民I

6^#

发表于 2009-9-15 16:50 |只看该作者 |招呼Ta 关注Ta

设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

5 主题	4 听众	176 积分

升级 38%

该用户从未签到

7^#

发表于 2009-9-16 11:09 |只看该作者 |招呼Ta 关注Ta

设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.....依次下去!

我也说一句

发表

使用道具举报

索路最高

0 主题	3 听众	15 积分

升级 10.53%

该用户从未签到

自我介绍: 200 字节以内

不支持自定义 Discuz! 代码

8^#

发表于 2010-3-27 04:16 |只看该作者 |招呼Ta 关注Ta

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