【题目描述】
从三个元素的集合[A,B,C]中选取元素生成一个 N 个字符组成的序列,使得没有两个相邻字的子序列(子序列长度=2)相同。例:N = 5 时 ABCBA 是合格的,而序列 ABCBC与 ABABC 是不合格的,因为其中子序列 BC,AB 是相同的。对于由键盘输入的 N(1<=N<=12),求出满足条件的 N 个字符的所有序列和其总数。
样例
输入
4
输出
72
【参考代码】
#include<bits/stdc++.h>
using namespace std;
char a[13];
int n,sum;
void f(int k) {
if(k==n+1) {
sum++;
return;
}
for(char i='A'; i<='C'; i++) {
a[k]=i;
if(a[k]!=a[k-2]||a[k-1]!=a[k-3]||k==1)
f(k+1);
else {
a[k]=0;
continue;
}
}
}
int main() {
cin>>n;
f(1);
cout<<sum<<endl;
return 0;
}