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

Question

我有一个难以处理的任务。任务是：创建递归函数，该函数可以生成由字母'A'，'B'和'C'组成的长度为N（N < = 100）的字符串，并且不包含两个相同的相邻子字符串。例如：输入N = 6，程序应该生成这样一个字符串，其中没有其他人重复使用子字符串：ABACAB。错误的字符串是：AA BACA - 因为'A'是'A'; A BCBC A - 作为'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个字母与以前的等你应该能够从这里拿走它。