0

次のように、スパイラル配列にピボットポイントを追加する必要があります。

 21 22 23 24 25 
 20   7   8   9 10
 19 6   1   2 11
 18   5   4   3 12
  17 16 15 14 13

私はまさにそれを行うJavaコードを持っており、上記のような小さな5x5配列で正常に動作します...しかし、大きな1001x1001配列でテストすると、多くのスタックオーバーフローが発生します。私はそれを追跡する方法がわかりません、私はすでにtryとcatchを使用しましたが成功しませんでした。コードは以下のとおりです。誰か提案はありますか？

public class Spiral {
    int[][] arr = new int[1001][1001];
    int counter = 1;
    public int total = 1;
    String direction = "SOUTH";
    public Spiral(){
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                arr[i][j] = 0;
            }
        }
        try {
        arr[500][500] = 1;
        spiral(500, 501);
        total += arr[0][arr.length - 1];
        System.out.println(total);
        } catch (Exception e) {
            e.printStackTrace();
            //System.out.println(x + ", " + y);
        }
    }

    public void spiral(int x, int y) {

            counter++;
            arr[x][y] = counter;

            if(x==900&&y==900)
                System.out.println("here");
            if (direction == "SOUTH") {
                if (arr[x][y - 1] != 0) {
                    if (x + 1 < arr.length)
                    spiral(x + 1, y);
                } else {
                    total += arr[x][y];
                    direction = "WEST";
                    spiral(x, y - 1);
                }
            } else if (direction == "WEST") {
                if (arr[x - 1][y] != 0) {
                    if (y - 1 >= 0) {
                        spiral(x, y - 1);
                    }
                } else {
                    total += arr[x][y];
                    direction = "NORTH";
                    spiral(x - 1, y);
                }
            } else if (direction == "NORTH") {
                if (arr[x][y + 1] != 0) {
                    if (x - 1 >= 0) {
                        spiral(x - 1, y);
                    }
                } else {
                    total += arr[x][y];
                    direction = "EAST";
                    spiral(x, y + 1);
                }
            } else if (direction == "EAST") {
                if (arr[x + 1][y] != 0) {
                    if (y + 1 < arr.length) {
                        spiral(x, y + 1);
                    }
                } else {
                    total += arr[x][y - 1];
                    direction = "SOUTH";
                    spiral(x + 1, y);
                }
            }

    }
}
4

4 に答える 4

4

spiral（int、int）は再帰的であり、スタックをオーバーフローするほど何度も自分自身を呼び出しています。2つのオプションがあります。

  1. アルゴリズムをリファクタリングして、再帰ではなくループする
  2. vmarg-Xssを使用してスタックサイズを増やします。デフォルトでは、VMはスタックに512 KBを使用するため、-Xss1mを使用してそのサイズ（または必要なその他の値）を2倍にすることができます。
于 2012-07-10T16:58:57.647 に答える
0

アルゴリズムは、配列内のすべてのセルに対して繰り返されます。あなたのスタックは本当に1,002,001回繰り返すのに十分な大きさですか？そうでない場合は、スタックを大きくするか、別のアルゴリズムを試す必要があります。

于 2012-07-10T16:58:03.733 に答える
0

再帰がどのように機能するかによって、この問題が発生していると思います。データを印刷するために再帰的に呼び出しspiralていますが、1001x1001データセットで呼び出すと、これも大きなスタックトレースが作成され、JVMがクラッシュし、最終的にスタックオーバーフローエラーが発生します。

于 2012-07-10T16:58:08.833 に答える
0

再帰を使用しているため、大きな入力に対してStackOverFlow例外が発生することは明らかです。

-Xssスイッチを使用してVMを調整してみてください。

于 2012-07-10T17:05:06.433 に答える