c++ - 递归函数生成不包含两个相邻相同子串的字符串c++

Question

我有一项任务对我来说很难处理。任务是:创建递归函数，可以生成长度为 N(N <= 100)的字符串，由字母“A”、“B”和“C”组成，并且不包含两个相同的相邻子字符串。例如:输入 for N = 6，程序应该生成这样一个字符串，其中没有其他人重复子字符串:ABACAB。错误的字符串是:AABACA - 因为“A”是“A”； ABCBCA - 因为“BC”是“BC”，ABCABC也是错误的，因为“ABC”是“ABC”。

我做了一个版本的程序，但是是迭代的方式，这里是代码:

#include <iostream>
#include <ctime>

using namespace std;

const char letters[] = "ABC";

char generate_rand()
{

     return letters[rand() % 3];

}

int check(char *s, int pos) 
{

    for (int i = 1; i <= (pos + 1)/2; i++) 
    {

        int flag = 1;

        for (int j = 0; j < i; j++)

        if (s[pos-j] != s[pos-i-j]) 
        {

            flag = 0; 
                break;

        }

        if (flag)
            return 1;

    }
    return 0;
}

int main() 
{

    char s[100];
    int n;

    cout << "enter n: ";
    cin >> n;

    srand(time(NULL));

    for (int i = 0; i < n; i++) 
    {

        do
        {

            s[i] = generate_rand();

        } while (check(s, i));

        cout << s[i] << " ";

    }

    cout << " ok" << endl;

    system("pause");
    return 0;
}

我觉得递归函数的入口可能需要是字符串的字符个数，会找一个相邻的字符串重复，每次加1，但不能超过原字符串长度的一半, 但不知道该怎么做。

Answer 1

所以让我们从一个简单的递归函数开始，它打印 10 个字母但不检查任何内容:

void addLetter(char* buf, int max_length)
{
   int len = strlen(buf);
   buf[len] = generate_rand();
   if (strlen(buf) < max_length) 
      addLetter(buf);
}

int main()
{
   srand(time(NULL)); //I forgot srand!
   int max_length = 10; //ask user to input max_length, like you had earlier
   char buf[100];
   memset(buf,0,sizeof(buf));
   addLetter(buf, max_length);
   printf("\n%s\n", buf);
   return 0;
}

现在让我们改变递归函数，让它只检查 1 个字母:

void addLetter(char* buf, int max_length)
{
   int len = strlen(buf);
   buf[len] = generate_rand();

   if (len > 0)
   {
      if (buf[len] == buf[len-1])
         buf[len] = 0;
   }

   if (strlen(buf) < max_length) 
      addLetter(buf);
}

下一步，检查 2 个字母与之前的字母等。您应该可以从这里获取它。