生成字符串的遞歸函數不包含兩個相鄰的相同子字符串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個字母與以前的等你應該能夠從這裏拿走它。