c++ - c++中的递归（生成二进制代码）

Question

我正在尝试编写一个程序，该程序在给定输入数字（位数）的情况下生成所有二进制代码。例如，如果用户输入 3，它应该生成以下所有数字：

该函数称为 generateBinaryCode()，它必须是递归的（这是问题的挑战）。

以下是我的尝试，但它不起作用。谁能给我一些见解？

提前致谢。

#include <iostream>
#include <string>
#include <vector>

using namespace std;
vector<string> generateBinaryCode(int nBits);

int main()
{
    int input;

    while (true)
    {
        cout << "Enter an integer (any negative numbers are sentinel): ";
        cin >> input;
        if (input < 0) break;

        for (unsigned i = 0; i < generateBinaryCode(input).size(); i++)
            cout << generateBinaryCode(input).at(i) << endl;
    }

    return 0;
}

vector<string> generateBinaryCode(int nBits)
{
    vector<string> result;
    int size = result.size();
    std::vector<string>::iterator it;

    if (nBits == 1) {

        result.push_back("0");
        result.push_back("1");

    } else {
        result = generateBinaryCode(nBits - 1);

        for (unsigned int i = 0; i < result.size(); i++)
        {
            result.push_back("0" + result.at(i));
            result.at(i) = "1" + result.at(i);
        }

    }

    return result;
}

score 1 · Accepted Answer

您的代码非常接近正确，但自我修改result会出现问题。插入向量会做很多事情，其中包括使当前在序列上打开的迭代器无效。但它也会改变结果size()（出于显而易见的原因，我希望）。

最简单的答案是使用子列表向量，然后枚举它，将所有条目附加到“0”和“1”中，然后将这些结果插入到返回向量中。下面是一个例子：

std::vector<std::string> getBitStrings(unsigned int n)
{
    std::vector<std::string> result;

    if (n <= 1)
    {
        result.push_back("0");
        result.push_back("1");
    }
    else
    {   // recurse, then add extra bit chars
        std::vector<std::string> sub = getBitStrings(n-1);
        for (std::vector<std::string>::const_iterator it = sub.cbegin();
             it != sub.cend(); ++it)
        {
            result.push_back(*it+'0');
            result.push_back(*it+'1');
        }
    }
    return result;
}

这与您的实现有些不同，因为它需要介于 1 和 n位数之间的值。运行n=5，产生以下内容：

int main()
{
    std::vector<std::string> bs = getBitStrings(5);
    std::copy(bs.begin(), bs.end(), 
         std::ostream_iterator<std::string>(std::cout, "\n"));
    return 0;
}

输出

老实说，有很多方法可以做到这一点，这只是其中一种。我故意按照您的原始实现对其进行建模，以限制算法更改。我希望它可以帮助您理解问题以及解决问题的一种方法。

score 1 · Accepted Answer

主要缺陷在以下循环中：

    for (unsigned int i = 0; i < result.size(); i++)
    {
        result.push_back("0" + result.at(i));
        result.at(i) = "1" + result.at(i);
    }

简而言之，您不想result在迭代时添加元素。你现在拥有的是一个无限循环（最终会耗尽内存）。

此外，您不想generateBinaryCode()在主循环的每次迭代中都调用它。调用一次并将结果存储在变量中。

最后（也是最不重要的），0在提示符下输入将导致无限递归。

score 0 · Accepted Answer

What you are trying to do at this line

result.push_back("0" + result.at(i));

is basically this, and that may be dodgy, and cause of your problem.

score 0 · Accepted Answer

更简单和简洁的解决方案

void printBin(std::string prefix, int n)
{
    if(prefix.size() == n)
    {

        std::cout <<prefix <<std::endl;
        return;
    }

    printBin(prefix + '0', n);
    printBin(prefix + '1', n);

    return;

}

int main()
{
    int n;
    std::cin >> n;
    printBin("", n);
    return 0;
 }

score -1 · Accepted Answer

这是一个简单的：（
用C写的，不是C++，但大纲应该是一样的）

void generateBinaryCode(char* txt, int i, int len)
{
    if (len != 0)
    {   txt[i] = '0';
        makeBinary(txt, i+1, len-1);

        txt[i] = '1';
        makeBinary(txt, i+1, len-1);
    } else
    {
        puts(txt);
    }
}


int main()
{
    char str[4] = {0};

    generateBinaryCode(str, 0, sizeof(str)-1);

    getchar();
    return 0;
}

c++ - c++中的递归（生成二进制代码）

5 回答 5

Related

Reference