1

再帰を使用して、数値の階乗を見つける以外のことをしたのはこれが初めてです。ボグルボードで単語を見つけるプログラムを作成しています。以下は、segfaults の原因となっている関数です。

void findWord(vector<string>& board, set<string>& dictionary,
          string prefix, int row, int column){
  prefix += getTile(board, row, column);
  if(prefix.length() > biggestWordLength)
    return;
  if(isOutOfBounds(row, column))
    return;
  if(isWord(prefix, dictionary) == 1)
    foundWords.insert(prefix);
  if(isWord(prefix, dictionary) == 0)
    return;
  //Note: this does not prevent using the same tile twice in a word
  findWord(board, dictionary, prefix, row-1, column-1);
  findWord(board, dictionary, prefix, row-1, column);
  findWord(board, dictionary, prefix, row-1, column+1);
  findWord(board, dictionary, prefix, row, column-1);
  findWord(board, dictionary, prefix, row, column+1);
  findWord(board, dictionary, prefix, row+1, column-1);
  findWord(board, dictionary, prefix, row+1, column);
  findWord(board, dictionary, prefix, row+1, column+1);
}
4

1 に答える 1

3

すべての場合において、すべての方向に再帰しています。次の縮小再帰バージョンを検討してください。

void findword(... int x, int y, ...) {
   ...
   findword(... x, y+1, ...);
   findword(... x, y-1, ...);
   ...
}

x == 5次に、それがいつ求められるかを考えてみましょうy == 5(たとえば、他のポジションでも同様に適切です)。以下のインデントを使用して、ネストされた呼び出しを表しています。

findword(... 5, 5, ...)
   findword(..., 5, 6, ...)    // x, y+1
      ...
   findword(..., 5, 5, ...)    // x, y-1
      // ouch! this is just the same as before, so it will eventually:
      findword(..., 5, 6, ...)
      findword(..., 5, 5, ...)
          // ouch!... here again! shall I continue?

次に、アルゴリズムについて考えてみましょう。単語を探すときは、まず最初の文字を選択し、次に方向を選択してから、その方向に何文字で単語を構成できるかをテストします。実装したアルゴリズムは、行だけでなくランダムな形で単語を見つけようとします。

于 2014-02-06T04:20:05.897 に答える