C++ 这个题目怎么写

  • Z时代
  • 2024-01-10
  • 分类：IT

图片描述

组合排列没什么思路

回答：

生成长度为 n 的所有 0/1 序列

递归的话：
长度为 n 的所有 0/1 序列 = "0".长度为 n-1 的所有 0/1 序列 + "1".长度为 n-1 的所有 0/1 序列

终止条件：长度为 0 的 0/1 序列只有 "" 。

所以，递归函数可以设计为 （以下为伪代码）：

vector<string> str_gen(int k/*需要生成的长度*/) {
    if (l == 0) {
       return{""};
    }
    // 生成长度为 k-1 的所有 0/1 串
    vector<string> v0 = str_gen(k-1);
    // 复制一份
    vector<string> v1 = v0;
    // 为 v0 中每个串前面拼接一个 "0"
    v0 <-- "0".v0
    // 为 v1 中每个串前面拼接一个 "1"
    v1 <-- "1".v1
    return { v0 与 v1 的并集 };
}

这样做，需要在内存里保持所有生成串。

如果可以边生成边使用（打印），不需要再内存里保持所有的结果，也可以用一下的方法，节省很多内存：

void str_gen2(string prefix/*已经生成的前缀*/，int k/*还需要生成的长度*/) {
    if (l == 0) {
       cout << prefix;
       return;
    }
    str_gen2(prefix+"0", k-1);
    str_gen2(prefix+"1", k-1);
}

生成长度为 n 的所有 0/1 串，调用 str_gen2("", n) 即可

以上是 C++ 这个题目怎么写 的全部内容， 来源链接： utcz.com/p/193026.html

回到顶部