递归程序，用于在 c 中打印给定长度 n 的 'a' 和 'b' 的所有字符串组合

Question

任务是：

编写一个完整的程序，该程序使用intn > 0，并在屏幕上递归地打印字符"a"one_answers"b"的所有组合。n=3的示例：aaa、baa、bba、aba、bab、aab、abb、bbb。

我想我必须使用类似于回溯的东西。这就是我所拥有的，但我想不出其他的了

void rep(int n, char str, int pos) {  //n would be the length and str would be the pointer
char c[n + 1];
char d[3];
d[0] = 'a';
d[1] = 'b';
for (int j = 0; j < 2; j++) {
if (strlen(c) == n) {    // if c is n long recursion ends
printf("%s", c);
} else {
c[pos] = d[j];       // put 'a' or 'b' in c[pos]
rep(n, c, pos + 1);  // update pos to next position
}
}
}

Answer 1

可变长度数组c未初始化

char c[n+1]

因此strlen在这个if语句中的调用

if(strlen(c) == n){ 

调用未定义的行为。

此外，参数str未在函数内使用。

我可以建议以下解决方案，如下面的演示程序所示

#include <stdio.h>
#include <string.h>
void rep( char *s )
{
puts( s );
char *p = strchr( s, 'a' );
if (p != NULL)
{
memset( s, 'a', p - s );
*p = 'b';
rep( s );
}
}
int main()
{
char s[] = "aaa";
rep( s );
}

程序输出为

aaa
baa
aba
bba
aab
bab
abb
bbb

也就是说，函数rep最初用包含所需大小的字符串n(在演示程序中n等于3(的数组调用，该字符串由等于字符'a'的所有字符组成，并且递归地输出所有组合，直到该字符串包含等于字符'b'的所有字符。

Answer 2

您的代码中存在一些问题：

• str参数的类型应为char *
• 因此，在递归函数中不需要新的数组，而是使用str参数所指向的数组
• 您不会在char数组的末尾设置null终止符
• 使用pos而不是strlen()来确定递归是否应该停止

这是的修改版本

#include <stdio.h>
// n is the length and str points to an array of length n+1
void rep(int n, char *str, int pos) {
if (pos >= n) {
str[n] = '';        // set the null terminator
printf("%sn", str);
} else {
str[pos] = 'a';
rep(n, str, pos + 1);
str[pos] = 'b';
rep(n, str, pos + 1);
}
}
#define LEN  3
int main() {
char array[LEN + 1];
rep(LEN, array, 0);
return 0;
}