问题标题: 酷町堂：1050 字符序列

Question

0

已解决

曾凡一

新手光能

1050 字符序列

点击此处查看题目

题目描述 Description

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

样例输入 Sample Input

1

样例输出 Sample Output

A
B
C
3

谁能够和我说一下解题思路与如何去实现？

Answer 1

已采纳

栾峻岩

初级天翼

void search(int t)
{
    if(t>n) 
    {
        输出，计数
    }
    for (int i=1;i<=3;i++) // A,B,C三个字母循环。
    {
        if ((i!=result[t-2]) || (result[t-1] != result[t-3])) //使得没有两个相邻字的子序列（子序列长度=2）相同
        {
            result[t]= i;
            search（下一个。）
        }
    } 
}

计数时count是全局变量，每次输出要换行，最后输出count.

思路：

A,B,C三个字母循环，使得没有两个相邻字的子序列（子序列长度=2）相同，

例如：

abcde

--->> a b c d e

从a到b判断。

a!=c b!=d 满足！ b!=d c!=e 也满足，则输出，并换行！！

Answer 2

蒋智航

高级天翼

用子程序

Answer 3

黄俊博

资深光能

void search(int t)
{
    if(t>n)
    {
        total++;
        for(int i=1;i<=n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
        return ;
    }
    if(t>3)
    {
        for(char i='A';i<='C';i++)
        {
            if(a[t-2]!=i || a[t-3]!=a[t-1])
            {
                a[t]=i;
                search(t+1);
            }
        }
    }
    else
    {
        for(char i='A';i<='C';i++)
        {
            a[t]=i;
            search(t+1);
        }
    }
}

Answer 4

曾凡一

新手光能

谢谢大家

Answer 5

王文博

缔造者之神

1

问题标题: 酷町堂：1050 字符序列

5 个回答: