1

セグメンテーション違反が発生する理由とその修正方法を教えてください。

以下のコードを書いて、迷路を再帰的に「トラバース」し、パスの総数を見つけます。「次のステップ」を追跡するためにスタックを使用しています。

ROWS と COLUMNS は、迷路のサイズを定義します。これらのパラメータを 9x9 よりも大きくすると、セグメンテーション エラーが発生します。なぜそれを取得しているのかわかりません。

gdb を使用したのはこれが初めてで、次の結果が得られました。

#3  0x0000000000400de0 in std::stack<xy, std::deque<xy, std::allocator<xy> > >::top (this=0x604400 <buff>)
at /usr/lib/gcc/x86_64-unknown-linux-gnu/4.7.2/../../../../include/c++/4.7.2/bits/stl_stack.h:161
161     return c.back();

それが私のスタックと関係があると私に信じさせます。

助けていただければ幸いです。ありがとう。

コード：

#define ROWS 10
#define COLUMNS 10

#include<iostream>
#include<stack>
using namespace std;

struct xy
{
  long i;
  long j;
};

stack<xy> buff;

long goRight (long j)
{
  if (j < COLUMNS-1)
    return 1;
  else
    return 0;
}

long goDown (long i)
{
  if (i < ROWS-1)
    return 1;  
  else
    return 0;
}

long traverse (xy POS)
{
  long fD = goDown(POS.i);
  long fR = goRight(POS.j);

  xy toAdd;

  if (fD == 1)
    {
      toAdd.i=POS.i+1;
      toAdd.j=POS.j;
      buff.push(toAdd);
    }

  if (fR == 1)
    {
      toAdd.i=POS.i;
      toAdd.j=POS.j+1;
      buff.push(toAdd);
    }

  if(buff.empty())
    return 0;

  toAdd = buff.top();
  buff.pop();

  return (traverse(toAdd) + (fD * fR));
}

int main()
{
  xy initial;
  initial.i=0;
  initial.j=0;

  cout << 1 + traverse(initial);

  return 1;
}
4

2 に答える 2

1

あなたcall stackのメモリ量は限られており、呼び出す各関数はそのスタックのメモリを使用しています。したがって、巨大な迷路を再帰的に総当たり攻撃すると、スタック オーバーフローが発生します。gdb の backtrace 関数を使用すると、それがはっきりとわかるはずです。

アルゴリズムを再考し、再帰の代わりに反復を使用する必要があります。あなたの場合、このリンクで説明されているように、繰り返しで簡単に実行できる、ある種のフラッド フィル アルゴリズムを実装したいと思われます。

また、Linux システムを使用している場合、を使用すると、このターミナル エミュレータから実行されるすべてのプログラムulimit -s unlimitedに無制限のメモリを使用できることに注意してください。call stackその場合、プログラムはセグメンテーション違反を起こすべきではありません。

幸運を。

于 2013-01-05T22:36:56.430 に答える
0

あなたが望むものを達成するためにオブジェクトは必要ないと思いstd::stackます（つまり、パスの数を数えます）。また、必ずしも反復に切り替える必要はありません。これにより、このアルゴリズムの作成が難しくなり、アルゴリズムとその終了条件が単純化されます。

考えられる解決策は次のとおりです（ところで、行と列の数を増やしたい場合は、スタックオーバーフローではなく整数long longを回避するために a に切り替えることを検討してください）：

#define ROWS 10
#define COLUMNS 10

#include<iostream>
#include <stack>

using namespace std;

struct xy
{
  long i;
  long j;
};

stack<xy> partialPath;

long goRight (long j)
{
  if (j < COLUMNS - 1)
    return 1;
  else
    return 0;
}

long goDown (long i)
{
  if (i < ROWS - 1)
    return 1;
  else
    return 0;
}

long traverse (xy const& POS)
{
    partialPath.push(POS); // Not needed to count the # of paths, but if you want...

    long fD = goDown(POS.i);
    long fR = goRight(POS.j);

    xy nextPos;
    long numOfPaths = 0;
    if (fD == 1)
    {
        nextPos.i=POS.i+1;
        nextPos.j=POS.j;
        numOfPaths += traverse(nextPos);
    }

    if (fR == 1)
    {
        nextPos.i=POS.i;
        nextPos.j=POS.j+1;
        numOfPaths += traverse(nextPos);
    }

    partialPath.pop(); // Not needed to count the # of paths, but if you want...

    if ((fD == 0) && (fR == 0))
    {
        return 1;
    }

    return numOfPaths;
}

int main()
{
  xy initial;
  initial.i=0;
  initial.j=0;

  cout << traverse(initial);

  return 0;
}

PS: さらに効率を高めるには、POS引数を const ref で渡すことをお勧めします。また、プロセスが成功したことを示すために使用する戻りコードは、1 ではなく 0 にする必要があると思います (つまり、 のreturnステートメントでmain())。

于 2013-01-05T22:58:18.027 に答える