0

私はプログラミングのパズルを解こうとしていて、いくつかの困難に立ち向かっています。これは、プロジェクトオイラー問題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;

これはの2番目の引数です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と8ベクトルbranch1、およびbranch2（これも空です）にアクセスし、未定義の動作につながります。

範囲外のアクセスを実行しないように、何らかの方法でサイズbranch1を変更する必要があります。branch2

こちらです：

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

それはできますが、コードのロジックを確認する必要があります。確かに他に何か問題があります。possibilitiesさらに、引数を値で渡すため、不要なコピーが作成され、からのベクトルに加えられた変更は表示されませんmain。

于 2012-06-25T19:04:18.787 に答える