查找字符串故宫计划

我最近遇到这个问题，下面说出来：查找字符串故宫计划

的字符串是说，如果有连续的三个字母的其中之一是一个被禁止的，一个是B，一个是C.对于例如BAAAACABCC被禁止，但AAABBBCCC不是。给你一个整数n。你必须找出有多少个长度为n的字符串不被禁止。（n将从1到30）
示例：如果n = 2，则不会禁止任何字符串。所以输出是9.

我试过但找不到一个有效的解决方案。我确实为此写了一个强力算法，其中我检查了所有可能的字符串，但由于它是指数算法，因此速度很慢。你可以找到我的代码here

有人可以指导我一个有效的算法，也许使用动态编程或任何其他方式。

谢谢

来源

2013-11-04 Jignesh

不知道这是否是作弊，但我做了什么是采取蛮力的第一个解决方案，并通过http://oeis.org/并看看你是否有任何点击。 –

作为一般线索，当处理计数访问问题时，答案通常是数学公式或某种动态编程或两者的组合......并且从来不是一个强力解决方案。要开始，使用蛮力来生成系列的第一项可能会给出关于数学公式的线索，或者手动执行第一步可能会给出关于动态编程方法的线索。 –

动态编程可以在这里应用。

假设你知道n = k的非禁止序列的数量。现在如果你添加另一个字母，那么组合的数量变成3k。但是，您必须丢弃被禁止的新组合。

任何序列的最后两个字母可以是：

ab 
ac 
bc 
ba 
ca 
cb 
bb 
aa 
cc

表格，您所提供的系列，似乎组合的数量丢弃其中（k + 1）=（对新增加的数量k）

编辑：这是为什么呢？从3k组合中，我们首先丢弃k个组合，说出所有先前的序列，我们将丢弃1/3。

现在，在这些k个组合被丢弃的情况下，有几个组合在最后有一个重复的字母（aa，bb或cc）。我们不必丢弃这些序列。

这样的序列的数量应该等于（k-1）的非禁止序列的数量，因为对于我们为n = k所做的每个新序列，我们可以只有一个重复字母的新序列。

Hence if f(k) = number of unforbidden combinations for n = k, 
then f(k + 1) = 3f(k) - [f(k)-f(k-1)]. 

For example for n=3 the number of sequences with repeated letter at the end shall be 9. 
For n=4 the number of sequences with repeated letter at the end shall be 21. 
... and so on.

来源

2013-11-04 18:12:51

嘿好方法，但我没有得到hw的组合没有被丢弃是f [k] - f [k-1] – Jignesh

我也不认为，它的12:00在这里！ –

大声笑，好的谢谢（顺便说一句，这是12:07在这里：P） – Jignesh

来自系列的外观：3,9,21,51,123的下一个号码为123 * 2 + 51 = 297

来源

2013-11-04 18:13:11 Carl

嘿，很好的观察这似乎工作，[编辑]确定了它:) – Jignesh

这样如何动态规划方法，其中C[x,y]意味着数长度x的未被禁止的字符串，其中与两个炭序列y结束：

C [n, 'AA'] = C[n-1, 'AA'] + C[n-1, 'AB'] + C[n-1, 'AC'] 
C [n, 'AB'] = C[n-1, 'BA'] + C[n-1, 'BB'] 
C [n, 'AC'] = C[n-1, 'CA'] + C[n-1, 'CB'] + C[n-1, 'CC'] 
C [n, 'BA'] = C[n-1, 'AA'] + C[n-1, 'AB'] + C[n-1, 'AC'] 
C [n, 'BB'] = C[n-1, 'BA'] + C[n-1, 'BB'] + C[n-1, 'BC'] 
C [n, 'BC'] = C[n-1, 'CA'] + C[n-1, 'CB'] + C[n-1, 'CC'] 
C [n, 'CA'] = C[n-1, 'AA'] + C[n-1, 'AB'] + C[n-1, 'AC'] 
C [n, 'CB'] = C[n-1, 'BA'] + C[n-1, 'BB'] + C[n-1, 'BC'] 
C [n, 'CC'] = C[n-1, 'CA'] + C[n-1, 'CB'] + C[n-1, 'CC']

具有边界条件n >= 3, C[3, x] = 3, C[3, 'AB'] = 2？

而且一个简单的程序，不知道是否正确，但果然冒险一些downvoting，如果它是错的，嘿嘿:)

#include <iostream> 

unsigned int C[100][9]; 

// AA 0 
// AB 1 
// AC 2 
// BA 3 
// BB 4 
// BC 5 
// CA 6 
// CB 7 
// CC 8 

void 
calc (unsigned int n) { 
    unsigned int i; 
    for (i = 0; i < 9; ++i) 
     C[3][i] = 3; 
    C[3][1] = 2; 

    for (i = 4; i <= n; ++i) { 
     C[i][0] = C[i-1][0] + C[i-1][1] + C[i-1][2]; 
     C[i][1] = C[i-1][3] + C[i-1][4]; 
     C[i][2] = C[i-1][6] + C[i-1][7] + C[i-1][8]; 
     C[i][3] = C[i-1][0] + C[i-1][1] + C[i-1][2]; 
     C[i][4] = C[i-1][3] + C[i-1][4] + C[i-1][5]; 
     C[i][5] = C[i-1][6] + C[i-1][7] + C[i-1][8]; 
     C[i][6] = C[i-1][0] + C[i-1][1] + C[i-1][2]; 
     C[i][7] = C[i-1][3] + C[i-1][4] + C[i-1][5]; 
     C[i][8] = C[i-1][6] + C[i-1][7] + C[i-1][8]; 
    } 
} 

// C [n, 'AA'] = C[n-1, 'AA'] + C[n-1, 'AB'] + C[n-1,'AC'] 
// C [n, 'AB'] = C[n-1, 'BA'] + C[n-1, 'BB'] 
// C [n, 'AC'] = C[n-1, 'CA'] + C[n-1, 'CB'] + C[n-1, 'CC'] 
// C [n, 'BA'] = C[n-1, 'AA'] + C[n-1, 'AB'] + C[n-1, 'AC'] 
// C [n, 'BB'] = C[n-1, 'BA'] + C[n-1, 'BB'] + C[n-1, 'BC'] 
// C [n, 'BC'] = C[n-1, 'CA'] + C[n-1, 'CB'] + C[n-1, 'CC'] 
// C [n, 'CA'] = C[n-1, 'AA'] + C[n-1, 'AB'] + C[n-1, 'AC'] 
// C [n, 'CB'] = C[n-1, 'BA'] + C[n-1, 'BB'] + C[n-1, 'BC'] 
// C [n, 'CC'] = C[n-1, 'CA'] + C[n-1, 'CB'] + C[n-1, 'CC'] 



int 
main() { 
    for (unsigned int i = 3; i < 10; ++i) { 
     calc (i); 

     unsigned int s = 0; 
     for (unsigned int j = 0; j < 9; ++j) 
      s += C[i][j]; 
     std::cout << s << " "; 
    } 
}

来源

2013-11-04 18:17:40 chill

对于i >= 2：

让same[i]是允许的数量（即不禁止）长度为i的字符串，以两个相同的字符结尾。
让diff[i]为长度为i的允许字符串的数量，以两个不同的字符结尾。

然后same[2] = 3，diff[2] = 6，并为i >= 2，

same[i+1] = same[i] + diff[i] 
diff[i+1] = 2 * same[i] + diff[i]

我们要的是n[i] = s[i] + d[i];上面的公式给我们

n[2] = 9 
n[i+1] = 2 * n[i] + n[i-1]

有了这个，你可以在基本上是线性的时间计算n[i]。

来源

2013-11-04 19:07:20 TonyK

查找字符串故宫计划

回答

相关问题