首页 > 代码库 > 字符序列

字符序列

Problem Description

从三个元素的集合[A,B,C]中选取元素生成一个N个字符组成的序列,使得没有两个相邻字的子序列(子序列长度=2)相同。例:N=5时ABCBA是合格的,而序列ABCBC与ABABC是不合格的,因为其中子序列BC,AB是相同的。
对于由键盘输入的N(1<=N<=12),求出满足条件的N个字符的所有序列总数。

Input

输入有多组数据,每组数据只有一行为一个整数N。

Output

对于每组数据满足条件的N个字符的所有序列总数

Sample Input

4

Sample Output

72

关键是怎样判断相邻的子序列不能相同,我们可以把A B C 三个字母相当于1 2 3,一开始我试试这样想的,每加入一个数,就要看看这个数前面那个数的前面那个数(orz)与它是否相等,

如果相等计数器+1,当计数器加到2时说明有两个子序列相同了,如12123(ABABC)第三个位置和第一个位置上都是1(A),计数器+1,第四个位置和第二个位置都是2(B)计数器+1,

此时计数器已经到2了所以这种情况舍弃///然后学长说ABACA这样计数器也会到2啊,但是却符合要求,我的方法的漏洞是我找到的是不连续的两个子序列,所以一旦所加的位置的数和前两位不一样,计数器清零。(学长的方法:可以把每个字母用不一样的素数代替,然后判断时前面我们是*10,我们可以乘一个比较大的素数,比较和是否相等,素数与素数的和是很难相等的;)

(看不懂也没关系,我表达的很烂‘’‘’‘’‘’学长讲得很清楚)

接下来我说一下这个代码的方法:例如12123(ABABC)每加入一个数(加入我们加入第四个位置的2吧)要计算第一个位置的数*10+第二个位置的数,和第三个位置上的数*10+我们正要加的数,这样 十二和十二相等,说明这个情况我们要舍弃了。

【代码】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int n,js,sum,ans[5];
void search(int);
int main()
{
scanf("%d",&n);
search(1);
cout<<sum<<endl;
return 0;
}
void search(int x)
{
for(int i=1;i<=3;i++)
{
ans[x]=i;
if(x>3&&ans[x-3]*10+ans[x-2]==ans[x-1]*10+ans[x])//判断子序列
continue;
else
{
if(x==n)sum++;
else
search(x+1);
}
}
}

字符序列