0

配列には、最初に値が増加し、次に値が減少する整数が含まれます。どの時点で数が減少し始めるかは不明です。2 番目の配列が昇順で並べ替えられるように、最初の配列の数値を別の配列にコピーする効率的なコードを記述します。

コードは以下のとおりです。

int _tmain(int argc, _TCHAR* argv[])
{
    int a[10] = { 17, 24, 31, 39, 44, 49, 36, 29, 20, 18 };
    int b[10];

    int i = 0, j = 9, k = 0;

    while (i <= j) {
        if (a[i] < a[j]) {
            b[k++] = a[i++];
        }
        else {
            b[k++] = a[j--];
        }
    }

    return 0;
}

ここでのループ不変条件は何ですか?

4

2 に答える 2

1

ループ不変条件とは、ループの各反復の前後で true を保持するものです。これには、ループの終了後と開始前が含まれます。それらのほとんどは重要ではありませんが、かなりの数があります。アルゴリズムが正しいことを証明するのに役立つものを選択する必要があります。そのためのループ不変条件は次のようになります。

長さkのサブ配列bは、配列aの項目で構成されますが、ソートされた順序になっています。

この不変式を証明するとき、配列bに対して elementi+1が element より大きいことを示したいと思うでしょうi。

于 2015-05-28T04:45:29.663 に答える
0

不変条件は while ループの条件なので、i <= j.

ループの不変条件は、各繰り返しの前 (および後) に保持されるプロパティです。

出典：ウィキ

于 2015-05-28T04:18:50.680 に答える