1

私は Boggle ゲームに取り組んでいますが、単語を検索する最良の方法は再帰を使用することだという人もいました。単語を検索するための searchWord メソッドを試しています。最初の文字が見つかった場合、メソッドはそれ自体を呼び出し、最初の文字を削除します。このメソッドは、長さ == 0 (単語が見つかった場合) または false (文字が見つからない場合) の場合に true を返します。問題は時々、1つの「サイコロ」の周りに同じ文字が複数回ある...解決するには、その文字を数える必要があり、それが複数回ある場合は、その文字の次の出現を検索する必要があります(検索最初の文字を削除せずに同じ単語)。その文字と、複数の文字がバインドされている文字のインデックスを記憶する方法が必要です。これにより、文字が見つからないときに、他の可能性があるかどうかを確認するために使用できます。以来」

皆さんが助けてくれることを願っています! メソッドは次のとおりです。

public boolean searchWord(String word, int i, int j) {
    boolean res;
    if (word.length() == 0) {
        res = true;
    } else {
        String theWord = word.toUpperCase();
        int[] indexes = searchLetter(Character.toString(theWord.charAt(0)), i, j);
        if (indexes[0] > -1) {
            res = searchWord(theWord.substring(1), indexes[0], indexes[1]);
        } else if(countLetter(Character.toString(/*The value that has to be memorized*/), /*index 1 that has been memorized*/, /*index 2 that has been memorized*/) > 1) {
            res = searchWord(theWord, i, j);
        } else {
            res = false;
        }
    }
    return res;
}

注：はい、文字列の方が良いオプションかもしれないので奇妙な文字列を使用しますが、後で変更できます。

4

4 に答える 4

3

原則として、追加のパラメーターとしてそのような値を渡すことができます。そうすれば、パラメーター/呼び出しスタックがスタックとして機能します。

于 2013-01-22T22:50:37.870 に答える
1

目的: ボグルボードに単語が存在するかどうかを確認する

仮定:

  • 各位置 (立方体) は単語ごとに 1 回だけ使用できます

  • 各文字は隣接している必要があります (垂直、水平、または斜め)

これは、再帰を使用してこれを行うための疑似コードでの試みです (ボグル ボードは文字の 2D 配列であり、このメソッドを呼び出す前に文字が既に入力されている必要があります)。

// searches for a single occurence of a word on the boggle board
boolean searchWord(String word, char[][] board)
    for each position on the board (x,y)
        boolean[][] visited = new boolean[width][height] // all false
        if (searchWord(x,y,board,visited))
            return true
    return false

// searches a position on the board
boolean searchWord(String word, int x, int y, char[][] board, boolean[][] visited)
    if x and y are valid (0 >= x < width and 0 >= y < height)
        if visited[x][y] == false
            visited[x][y] = true
            if the letter at x,y equals the 1st char of the search word
                if word.length() == 1
                    return true
                else
                    for each surrounding position (x2, y2)
                        if searchWord(word.substring(1),x2,y2,board,visited)
                            return true
    return false

ご覧のとおり、再帰はパス検索 (ボグル ワードの検索) に適しています。現在の状態 (この場合は配列) を渡すだけvisitedで、どこに行ったかがわかります。

パラメーターを使用して状態を保存しましたが、本当に必要な場合はインスタンス変数を使用できます。関数型プログラミングのパラダイムに沿っており、予期しない副作用が発生する可能性がはるかに低いため、パラメーターを使用することをお勧めします。

ここでは、明示的にスタックを使用する必要はありません。スタックは、値がscope(Java のローカル変数のように) ある場合に最適であり、特定の順序でアクセスする必要がありますが、ここではあまり役に立ちません。参考までに、再帰を使用すると、とにかく Java のコール スタックを利用していることになり、注意を怠ると、永遠に再帰することができ、StackOverflowException が発生します ;)

于 2013-01-22T23:30:46.273 に答える
1

メソッドに別のパラメーターを追加するだけです。たとえば、単に文字と整数を保持するオブジェクトを作成できます。Java は再帰呼び出しを行うときにこのオブジェクトへの参照を渡すだけなので (ただし、オブジェクト自体はコピーしません)、パラメーターは常に同じオブジェクトを指します。Java のペア クラスを使用することもできます (私の記憶が正しければ、マップで使用されます)。

于 2013-01-22T22:47:11.350 に答える
0

スタックを使用するには、これを書き直す必要があります。ほとんどの場合、再帰は Stack を使用した方が適切です。次に、コンテキストに関する情報を保存し、さらに処理が必要なものをスタックにプッシュし、処理する準備ができたらポップします。

于 2013-01-22T22:43:32.890 に答える