0

我最近遇到了以下问题：

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

我试过但找不到有效的解决方案。我确实为此编写了一个蛮力算法，其中我检查了所有可能的此类字符串，但由于它是一个指数算法，所以它非常慢。你可以在这里找到我的代码

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

谢谢你

4

4 回答 4

2

从系列看：3,9,21,51,123 下一个数字是 123 * 2 + 51 = 297

于 2013-11-04T18:13:11.737 回答
1

这里可以应用动态规划。

假设您知道 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-04T18:12:51.640 回答
1

这种动态编程方法怎么样，其中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?

还有一个简单的程序，不确定是否正确，但肯定会冒一些被否决的风险，如果它是错误的，呵呵:)

#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-04T18:17:40.153 回答
0

对于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-04T19:07:20.907 回答