<分区>
friend 告诉我下面的挑战题。
给定{A, T, G, C}作为我们的字母表，我们想知 Prop 有指定长度的有效短语的数量 n具有以下递归模式定义:
-
pat=pat1pat2，即将两个模式连接在一起形成一个新模式pat. -
pat=(pat1|pat2)，即选择其中一种模式pat1或pat2形成新格局pat. -
pat=(pat1*)，即重复模式pat1任意次数(可以为 0)以形成新模式pat.
由字母集 {A, T, G, C} 组成的短语如果可以通过上述模式定义形成，则称其满足模式；它的长度是字母的数量。
几个例子:
- 给定一个模式
((A|T|G)*)和n=2, 有效短语的数量 是 9，因为有AA,AT,AG,TA,TT,TG,GA,GT,GG. - 给定一个模式
(((A|T)*)|((G|C)*))和n=2, 有效短语的数量 是 8，因为有AA,AT,TA,TT,GG,GC,CG,CC. - 给定一个模式
((A*)C(G*))和n=3, 有效短语的数量 是 3，因为有AAC,ACG,CGG.
如果您曾经遇到过这个问题，请指出问题的根源以及解决它的想法。