字符序列(characts)

问题描述：

从三个元素的集合[A,B,C]中选取元素生成一个N 个字符组成的序列，使得没有两个相邻的

子序列（子序列长度＝2）相同，例：N＝5 时ABCBA 是合格的，而序列ABCBC 与ABABC 是不

合格的，因为其中子序列BC，AB 是相同的。

输入N（1<=N<=12）,求出满足条件的N 个字符的所有序列和其总数。

输入样例：

输出样例：

 1 #include<iostream>
 2 
 3 #include<cstdlib>
 4 
 5 using namespace std;
 6 
 7 int n,a[100],s;
 8 
 9 void go(int x)
10 
11 {
12 
13          if (x>n)
14 
15          {
16 
17                    s++;
18 
19                    return;
20 
21                    }  //如果这个长度等于要求的长度，就把可能性加一重新进行下一次搜索
22 
23          int i;
24 
25          for (i=1;i<=3;i++)
26 
27          if (a[x-3]*10+a[x-2]!=a[x-1]*10+i)  //判断子序列，如果满足要求则把这个位置放这个值
28 
29          {
30 
31                    a[x]=i;
32 
33                    go(x+1);  //进行下一次搜索
34 
35                    }
36 
37 }
38 
39 int main()
40 
41 {
42 
43          cin>>n;
44 
45          if (n<=2)
46 
47          {
48 
49                    if (n==1) cout<<3;
50 
51                    else cout<<9;
52 
53                    cout<<endl;   
54 
55                    exit(0);
56 
57                    }
58 
59          s=0;
60 
61          int i,j,k;
62 
63          for (i=1;i<=3;i++)
64 
65            for (j=1;j<=3;j++)
66 
67              for (k=1;k<=3;k++)
68 
69            {
70 
71                             a[1]=i; a[2]=j; a[3]=k; //枚举出前三个位置所有的可能性在这个情况下进行下一步搜索
72 
73                             go(4);
74 
75                             }
76 
77          cout<<s<<endl;
78 
79          return 0;
80 
81 }

前三位位置枚举，后面的值判断满足要求就留在那个位置，满足数量就加一。

一开始的时候我就直接，枚举前四个数的可能性