递归函数生成不包含两个相邻相同子串的字符串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 个字母与之前的字母等。您应该可以从这里获取它。

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

Recursive function to generate string does not contain two adjacent identical substring c++

c++

string

recursion

substring

function