0

我正在尝试解决编程难题并遇到一些困难。它类似于Project Euler 问题 215，但块的宽度为 3 和 4.5。无论如何，我最初是通过暴力强制 C 中的组合来接近它，但我试图通过计算第一行中的所有组合并查看有多少有效的组合方式然后从那里开始来加快运行时间。我认为使用布尔向量（尝试过的位集，但我不能使用它们，因为我在编译时没有可用的宽度）会更容易，但我没有使用向量的经验我做了一些事情让段错误的神生气。我只是看不出在哪里。

当我输入程序参数时，我遇到了分段错误 11，所以这绝对是我所做的，当我在 GDB 中运行回溯时，我得到以下信息：

#0  0x0000000100002645 in std::_Bit_reference::operator= ()
#1  0x0000000100001be2 in build ()
#2  0x0000000100002287 in main ()

我知道一定有一些我没有看到的东西。它仅在实际调用 build() 时发生，但我将 main() 包括在内，以防万一我可能在调用中做错了什么。

#include <vector>

void build(std::vector<std::vector<bool> > possibilities, std::vector<bool> current, float width)
{
if(current.size() > 0)
{
    if(current.size() > width) return; // If we went over the specified width, bail out-invalid

    if (current.size() == width) // If we just matched the width for this row, push it on to our vector of possibilities
    {
        possibilities.push_back(current);
        return;
    }
}

// Try adding a block of length 3 and a block of length 4.5
std::vector<bool> branch1;
std::vector<bool> branch2;
if(current.size() > 0)
{
    branch1.assign( current.begin(), current.end() );
    branch2.assign( current.begin(), current.end() );

    branch1[ current.size() + 5 ] = 1;
    branch2[ current.size() + 8 ] = 1;
}
else
{
    branch1[5] = 1;
    branch2[8] = 1;
}
// Split off and check both branches
build(possibilities, branch1, width);
build(possibilities, branch2, width);
}

int main( int argc, char *argv[] )
{
if ( argc == 3 ) // Number of arguments should be 3-the program name, plus our width and height
{
    float width = (atof(argv[1]) * 2); // Width is assumed to be entered first, converting to integer
    int height = atoi(argv[2]); // The second argument should be height, ditto above
    if ( (width < 3) || (height < 1) ) // Catches non-number inputs (atof/i returns 0) and invalid entries
    {
        printf("Expected two numeric arguments, width and height, in that order.");
    }
    else // Continue the program
    {
        std::vector<bool> noo;
        std::vector<std::vector<bool> > possibilities;
        build(possibilities, noo, width);
        printf("%llu", (unsigned long long)possibilities.size());
    }
}
else
{
    printf("Expected two numeric arguments, width and height, in that order.");
}
}
4

1 回答 1

3

你的noo载体：

std::vector<bool> noo;

这是 的第二个参数build：

build(possibilities, noo, width);

是空的。但是，在内部build，您会根据该向量的大小执行一些操作：

std::vector<bool> branch1;
std::vector<bool> branch2;
if(current.size() > 0) //current is actually noo
{
    branch1.assign( current.begin(), current.end() );
    branch2.assign( current.begin(), current.end() );

    branch1[ current.size() + 5 ] = 1;
    branch2[ current.size() + 8 ] = 1;
}
else
{
    branch1[5] = 1;
    branch2[8] = 1;
}

由于它是空的，因此您将访问向量的位置5和以及（它们也是空的），从而导致未定义的行为。8branch1branch2

您应该以某种方式调整大小branch1，branch2以免执行越界访问。

这边走：

std::vector<bool> branch1(someNumber);

会这样做，但你应该看看你的代码逻辑，肯定还有其他问题。此外，您正在按值传递参数，因此您正在制作不必要的副本，并且您不会看到对possibilities来自main.

于 2012-06-25T19:04:18.787 回答