0

Java で分割統治アルゴリズムを作成しました。問題は、それが機能することをテストしたことですが、データに対してなぜ、または何をするのかが本当にわからないことを除いて. 配列がサブパーツに分割されることは知っていますが、それとは別に、すべてを返すとどうなるか混乱しています。たとえば、最小の基本ケースはその数を返し、それを比較しますか? また、関数に複数の再帰呼び出しがある場合、再帰はどのような順序で行われますか? 私のコードは次のとおりです。

public static int FindMin(int[] array, int low, int high)
{
int min = 0, min1 = 0, min2 = 0;
int mid = 0;
if (low == high)
    {
    min = array[low];
    }
else if (low == (high - 1))
    {
    if (array[low] < array[high])
        {
        min = array[low];
        }
    else if (array[low] > array[high]);
        {
        min = array[high];
        }
    }
else
    {
    mid = (low + high)/2;
    min1 = FindMin(array, low, mid);
    min2 = FindMin(array, mid+1, high);
    if (min1 < min2)
        {
        min = min1;
        }
    else
        {
        min = min2;
        }
    }
return min;
}

基本的に私が知りたいのは、次の入力が与えられた場合にアルゴリズムがどのように機能するかです: 3,6,1,5,7,2,1. それが返すものなどのように。

質問があいまいな場合は申し訳ありませんが、コーディング方法は知っています。開始したすべてのGoogleページとPDFに関係なく、すべてを返す方法を理解できないようです。

とにかく助けてくれてありがとう！:D

4

2 に答える 2

1

デバッガーは便利ですが、適切な種類のログファイル出力によってより多くの洞察が得られる場合があります。関数の最後、ステートメントFindMin()の直前に次の関数への呼び出しを追加しました。return min;

public static void pr (int[] array, int low, int high, int min) {
    System.out.print("low = ");
    System.out.print(low);
    System.out.print(", high = ");
    System.out.print(high);
    System.out.print(", array = ");
    for (int i = low; i <= high; i++) {
        System.out.print(array[i]);
        if (i < high) {
            System.out.print(",");
        }
    }
    System.out.print(" min = ");
    System.out.print(min);
    System.out.print("\n");
}

私が得る出力は次のとおりです。

low = 0, high = 1, array = 3,6 min = 6
low = 2, high = 3, array = 1,5 min = 5
low = 0, high = 3, array = 3,6,1,5 min = 5
low = 4, high = 5, array = 7,2 min = 2
low = 6, high = 6, array = 1 min = 1
low = 4, high = 6, array = 7,2,1 min = 1
low = 0, high = 6, array = 3,6,1,5,7,2,1 min = 1

これはFindMin()、このテスト ケースに対して正しい答えを返しているものの、多少の偶然によるものであることを示しています。その理由を今探しています...

（編集）

1 つの問題は、コード:

if (array[low] < array[high])
{
    min = array[low];
}
else if (array[low] > array[high]);  // <- stray semi-colon here
{
    min = array[high];
}

... の場合は考慮しませんarray[low] == array[high]。最初の比較は である<=か、2 番目の比較は である必要があります。そうでない場合、 のどちらの分岐も適用されないため、>=の戻り値が初期化された値 0 になる場合があります。minif

(さらに編集)

バグの原因となっているセミコロンがあります。上記でマークしたテストの後のセミコロンは、ステートメントを終了します。途中で終了したステートメントの後には、前のテストに関係なく、常にequal にelse if設定される別のステートメントが続きます。minarray[high]

このコードを次のように変更します。

if (array[low] < array[high])
    {
    min = array[low];
    }
else 
    {
    min = array[high];
    }

... 次の出力が得られます。

low = 0, high = 1, array = 3,6 min = 3
low = 2, high = 3, array = 1,5 min = 1
low = 0, high = 3, array = 3,6,1,5 min = 1
low = 4, high = 5, array = 7,2 min = 2
low = 6, high = 6, array = 1 min = 1
low = 4, high = 6, array = 7,2,1 min = 1
low = 0, high = 6, array = 3,6,1,5,7,2,1 min = 1

...各再帰呼び出しから正しい結果が生成されていることがわかります。

于 2013-04-07T06:15:48.477 に答える