1 
public boolean isConnected(int row, int col) {    //helper Method 
        int i;
        int j;

        if (BOARD[row][col].isEmpty())
            return false;
        for (i = row; i > 0; i--)
            if (hasRed(i, col))
                return true;
            else if (isEmpty(i, col))
                break;
        for (i = row; i < ROWS; i++)
            if (hasRed(i, col))
                return true;
            else if (isEmpty(i, col))
                break;
        for (i = col; i < COLS; i++)
            if (hasRed(row, i))
                return true;
            else if (isEmpty(row, i))
                break;
        for (i = col; i > 0; i--)
            if (hasRed(row, i))
                return true;
            else if (isEmpty(row, i))
                break;
        for (i = row, j = col; i > 0 && j < COLS; i--, j++)
            if (hasRed(i, j))
                return true;
            else if (isEmpty(i, j))
                break;
        for (i = row, j = col; i < ROWS && j > 0; i++, j--)
            if (hasRed(i, j))
                return true;
            else if (isEmpty(i, j))
                break;
        for (i = row, j = col; i > 0 && j > 0; i--, j--)
            if (hasRed(i, j))
                return true;
            else if (isEmpty(i, j))
                break;
        for (i = row, j = col; i < ROWS && j < COLS; i++, j++)
            if (hasRed(i, j))
                return true;
            else if (isEmpty(i, j))
                break;

        return false;

    }

//多くのテストケースが試行された後にアルゴリズムが例外を引き起こす可能性のあるメインメソッドは、真の解決策がある場合は常に終了しますが、偽の解決策で終了する場合と終了しない場合があります。その理由は、再帰ステップが元の問題を単純化しないためだと思いますしかし、実際にはそれを展開します! 正しい解決策を得る機会を得るために、問題は、確かに false を返す必要がある特定の条件では、以前に解決されたサブ問題などをチェックし続けるため、アルゴリズムが終了できないことです。

public boolean isConnected2(int rowCurr, int colCurr) {

            if (rowCurr >= ROWS || rowCurr < 0 || colCurr < 0 || colCurr >= COLS) 
                return false;                  //Base case 1 reached bounds of the 2d array
            if (isEmpty(rowCurr, colCurr))
                return false;
            if (isConnected(rowCurr, colCurr)) // base case 2 current piece is connected according to the method above
                return true;

            else {
                return     isConnected2(rowCurr + 1, colCurr + 1)                                          
                        || isConnected2(rowCurr - 1, colCurr - 1)
                        || isConnected2(rowCurr + 1, colCurr - 1)
                        || isConnected2(rowCurr - 1, colCurr + 1)
                        || isConnected2(rowCurr - 1, colCurr - 1)
                        || isConnected2(rowCurr + 1, colCurr)
                        || isConnected2(rowCurr - 1, colCurr)
                        || isConnected2(rowCurr, colCurr + 1) 
                        || isConnected2(rowCurr, colCurr - 1);
// if any of the above calls returns true we are done


            }

        }

問題は、アルゴリズムが無限に再帰する特殊なケースを処理する方法がわからないことです。また、(||) 演算子の性質により、真の解決策があればそれは終了します。この場合、単に StackOverFlow エラーを処理し、それをメソッドの false リターンとして扱う方がよいのではないでしょうか??

4

3 に答える 3

2

任意の再帰関数を非再帰関数に変換できます。

たとえば、ある種のキューを使用します。メソッドのさまざまなパラメーターをキューにプッシュしisConnected2、キューからパラメーターのセットを継続的にポップして、それらを評価します。その評価の結果、関数への呼び出しが増えた場合は、新しいパラメーターのセットをキューにプッシュします。その後、キューが大きくなりすぎた場合、または一定の時間が経過した後に終了できます。

このようにして、スタックの代わりにヒープを使用し、スタックオーバーフローの可能性を回避します。

于 2012-05-08T00:00:33.013 に答える
1

プログラムにスタック オーバーフローを残さないでください。それを発生させてキャッチすることは、JVM にとって大きな負担となります。再帰が起こらないように修正してください。

于 2012-05-08T12:42:31.033 に答える
0 
public boolean isConnected2(int row, int col) {
        int i; int j;
        if (OutOfBounds(row, col)) 
            return false;
        if (isEmpty(row, col))
            return false;
        if (isConnected(row, col)) 
            return true;

        else {

            for (i = row; i > 0; i--)
                if(isConnected(i,col))
                    return true;
                else if(isEmpty(i, col))
                    break;

            for (i = row; i < ROWS; i++)
                if(isConnected(i,col))
                    return true;
                else if(isEmpty(i,col))
                    break;
            for (i = col; i < COLS; i++)
                if(isConnected(row,i))
                    return true;
                else if(isEmpty(row,i))
                    break;
            for (i = col; i > 0; i--)
                if(isConnected(row,i))
                    return true;
                else if(isEmpty(row,i))
                    break;
            for (i = row, j = col; i > 0 && j < COLS; i--, j++)
                if(isConnected(i,j))
                    return true;
                else if(isEmpty(i,j))
                    break;
            for (i = row, j = col; i < ROWS && j > 0; i++, j--)
                if(isConnected(i,j))
                    return true;
                else if(isEmpty(i,j))
                    break;
            for (i = row, j = col; i > 0 && j > 0; i--, j--)
                if(isConnected(i,j))
                    return true;
                else if(isEmpty(i,j))
                    break;
            for (i = row, j = col; i < ROWS && j < COLS; i++, j++)
                if(isConnected(i,j))
                    return true;
                else if(isEmpty(i,j))
                    break;

        }
        return false;

    }

これは同じメソッド isConnected2 が繰り返し実装されていますが、類似していますか? すべての方向に繰り返し伝搬するのではなく、2 次元配列の各方向を 1 回だけチェックするようになりました。

于 2012-05-08T11:51:52.983 に答える