问题描述:一个只包含'A'、'B'和'C'的字符串,如果存在某一段长度为 3 的连续子串中恰好'A'、'B'和'C'各有一个,那么这个字符串就是纯净的,否则这个字符串就是暗黑的。
例如:
BAACAACCBAAA 连续子串 "CBA" 中包含了'A','B','C'各一个,所以是纯净的字符串
AABBCCAABB 不存在一个长度为 3 的连续子串包含'A','B','C', 所以是暗黑的字符串
你的任务就是计算出长度为 n 的字符串 (只包含'A'、'B'和'C'),有多少个是暗黑的字符串 (1 ≤ n ≤ 30)。
首先如果题目是如何判断一个字符串是暗黑(纯净)字符串,你会怎么解?
这个问题很简单,直接遍历判断连续的三个字符是否分别为 ABC。额,而我想说的是有一个比较好的想法是
令 A=2,B=3,C=5,如果某三个字母乘积为 30,即这个字符串为纯净的字符串。尽管操作起来比直接判断连续 3 个字符串是否为 ABC 便利不了多少,但是我觉得这是一个比较好的想法。
讲回正题,现在是计算出长度为 n 的字符串,有多少个暗黑的字符串。
下面提供 2 种思路
思路 1
当 n=1 时,3 种情况,暗黑,
当 n=2 时,9 种情况,暗黑。
当 n=3 时,第一个位置 3 种情况,第二个位置 3 种情况,而第三个位置则要考虑前 2 个位置,
如果前 2 个位置相同则第三个位置有三种选择,否则有 2 种选择。
所有有 3*(3*1+2*2)=21 是暗黑的。
当 n=4 时,按照 n=3 的情况继续类推下去,假若第二个位置和第三个位置相同,第四个位置有 3 种选择,否则有 2 种选择。
所以有 3*(3*(1+2)+2*(1*2+2))) = 51(如果看不明白可留言再解答)
如此类推可得出下列规律
当 n>3,sum(n) = 3*(3*num3(n) + 2*num2(n))
num2(n) = 2*num3(n-1) + num2(n-1)
num3(n) = num3(n-1) + num2(n-1)
观察上面第一个式子 3*(3*1+2*2)=21 ,num2(1)=2 num3(1)=1
这个思路主要是从式子里推出来的,也是比较常规的一个方法。
- def dark1():
- dark = [3,9]
- num2 = 2
- num3 = 1
- for i in range(28):
- dark.append(3*(3*num3+2*num2))
- num3,num2 = num2+num3,2*num3+num2
- print(dark)
运行结果:
[3, 9, 21, 51, 123, 297, 717, 1731, 4179, 10089, 24357, 58803, 141963, 342729, 827421, 1997571, 4822563,
11642697, 28107957, 67858611, 163825179, 395508969, 954843117, 2305195203, 5565233523, 13435662249,
32436558021, 78308778291, 189054114603, 456417007497]
思路 2
正如上面的思路 1,我们可以分析出,每增加一个位置的字符,要使其保持暗黑的性质,只需要考虑前 2 个字符。
当前 2 个字符相同,那么第 n 个位置的取法有 3 种,否则有 2 种。
不妨设前 2 个字符相同的情况为 s(n), 前 2 个字符不同为 d(n), 那么我们可得出
sum(n) = 3*s(n-1) + 2*d(n-1) = 2*(s(n-1)+d(n-1)) + s(n-1) = 2*sum(n-1) + s(n-1)
因为前个字符要不就是 d(n) 要不就是 s(n),所以 d(n)+s(n) 就等于 sum(n),剩下的问题就是求解 s(n-1)。
我们知道,对于 s(n-1) AA 第三个字母只能跟之前一样 AAA 才能得到 s(n),对于 d(n-1) AB 第三个字符只有跟最后一个一样 ABB 才能得到 s(n)
所以得出结论 s(n) = s(n-1) + d(n-1) = sum(n-1), s(n-1) = sum(n-2)
sum(n) = 2*sum(n-1) + s(n-1) = 2*sum(n-1) + sum(n-2)
- def dark2():
- dark = [3,9]
- for i in range(28):
- dark.append(dark[-2]+2*dark[-1])
- print(dark)
运行结果:
[3, 9, 21, 51, 123, 297, 717, 1731, 4179, 10089, 24357, 58803, 141963, 342729, 827421, 1997571, 4822563,
11642697, 28107957, 67858611, 163825179, 395508969, 954843117, 2305195203, 5565233523, 13435662249,
32436558021, 78308778291, 189054114603, 456417007497]
来源: http://www.cnblogs.com/lateink/p/6444328.html