0

Foundations of Algorithmsの中央値アルゴリズムの中央値を使用して k 番目の要素を選択していますが、Java での実装に問題があります。範囲外の配列エラーが発生しており、誰かがこのアルゴリズムを正しく実装するのを手伝ってくれるかどうか疑問に思っていました.

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
    at test2.selection2(test2.java:23)
    at test2.select4(test2.java:16)
    at test2.partition2(test2.java:55)
    at test2.selection2(test2.java:27)
    at test2.select4(test2.java:16)
    at test2.partition2(test2.java:55)
    at test2.selection2(test2.java:27)
    at test2.select4(test2.java:16)
    at test2.main(test2.java:11)

変数の値は次のとおりです。

N size = 10
low = 0
high = 10
k = 3
arraysize = 10
r = 2
i = 1,2,3
first = 0,5,10
last = 4,9,11
lower = 7, 33
upper = 10, 44

-pivotitem
T size = 2
low = 0
high = 2
k = 1
arraysize = 10
r = 0

high==low [0]
list is empty

私の配列はサイズ 10 から始まるため、r は 2 になります。partition2 が pivotitem から再度呼び出されると、r は 0 になり、配列 T のサイズは 0 になります。その後、low と high は 0 に等しくなり、何も返されません。エラーが発生しています。私のコードは本のアルゴリズムに似ているため、なぜこれが起こっているのかわかりません。

4

3 に答える 3

0

オリジナルはCコードですか？partition2は＆で呼び出されます

index& pivotpoint)

つまり、参照、つまり変更された結果が呼び出し元に表示されます。

あなたは静的な「thepivotpoint」でそれに対処しているように見えましたが、それをパラメータとして使用することはできません。静的メンバーを非表示にするだけです。

public static void partition2 (int[] list, int low, int high) // , int pivotpoint)
/* unchanged */
    thepivotpoint = j - 1;
    list = swap (mark, thepivotpoint, list);
}

まだ完成していません。

于 2011-03-08T11:07:10.847 に答える
0

swap メソッドは引数としてインデックスを受け取るように見えますが、値を入力します

list = swap (list[i], list[j], list);

それはエラーの根本ではなく、呼び出しを変更した後もエラーは持続しますが、何度も間違っている可能性があります。ところで: コードはどこに行ったのですか?

于 2011-03-08T05:10:53.627 に答える
0

解決策のない他のいくつかの改善点がありますが、さらに先に進むためのより良い基礎になるかもしれません:

  • すべての変数がメソッドの先頭で宣言されているわけではありません (パスカル スタイル)。これにより、コードについての推論がより簡単になります。
  • パラメータの順序を少し統一しました(int[], int, ...)
  • から他を削除しましたif ... return else ...。
  • partition2 を 2 つのメソッドに分割しました。
  • show無限ループで停止するカウンターをトリガーするデバッグ用メソッドを追加しました。

  • 私を助けなかったコメントを削除しました。たぶん、より良いコメントを追加できます。

    import java.util.Arrays;

public class Pivot
{
    static int thepivotpoint;

    public static void main(String[] args)
    {
        int[] list = {17, 10, 44, 7, 7, 33, 24, 10, 48, 49 };
        thepivotpoint = 0;
        System.out.println (select4 (list, list.length, 3));
    }

    public static int select4 (int[] list, int high, int k)
    {
        return selection2 (list, 0, high, k);
        // return selection2 (list, 1, high, k);
    }

    public static int selection2 (int[] list, int low, int high, int k)
    {
        if (high == low)
            return list[low];
        partition2 (list, low, high);
        if (k == thepivotpoint)
            return list [thepivotpoint];
        if (k < thepivotpoint)
            return selection2 (list, low, thepivotpoint - 1, k);
        return selection2 (list, thepivotpoint + 1, high, k);
    }

    static int count = 0;
    public static void show (int [] T)
    {
        for (int i : T)
            System.out.print (i + "\t");    
        System.out.println ();  
        if (++count > 20) System.exit (1);
    }

    public static void partition2 (int[] list, int low, int high) 
    {
        int arraysize = high - low;
        int r = (int) Math.ceil (arraysize / 5);
        int [] T = new int[r+1];
        for (int i = 1; i <= r; i++)
        {
            int first = low + 5 * i - 5;
            int last = Math.min (low + 5 * i - 1, arraysize);
            T [i] = median (list, first, last);
        }
        show (list);
        approximateTheMedian (T, r, low, high, list);
    }

    public static void approximateTheMedian (int [] T, int r, int low, int high, int [] list) 
    {
        int pivotitem = select4 (T, r, (r + 1) / 2); 
        int j = low;
        int mark = 0;
        for (int i = low; i < high; i++)
        {
            if (list[i] == pivotitem)
            {
                list = swap (i, j, list);
                mark = j; //mark where pivotitem placed
                j++;
            }
            else if (list[i] < pivotitem)
            {
                list = swap (i, j, list);
                j++;
            }
        }
        thepivotpoint = j - 1;
        list = swap (mark, thepivotpoint, list);
    }

    public static int median (int[] list, int start, int end)
    {
        int [] copy = (int[]) list.clone ();
        Arrays.sort (copy);
        return copy [(start + end) / 2];
    }

    public static int[] swap (int one, int two, int[] list)
    {
        int dummy = list[one];
        list[one] = list[two];
        list[two] = dummy;
        return list;
    }
}
于 2011-03-08T16:55:30.447 に答える