Пусть
a — вещественный массив размера
n(индекс элементов меняется от 0 до
n-1).Определить, содержит ли следующий фрагмент программы ошибку(т.е. действительно ли тело цикла сохраняет инвариант):
// Программа Быстрая сортировкадано: цел n; вещ a[n]; // вещественный массив размера nцел m; // индекс медианыутверждение: n >= 2 и 0 <= m и m < n;надо: // разделить массив на три части: // 1) слева элементы, меньшие медианы; // 2) в центре медиана; // 3) справа элементы, большие или равные медиане.цел i, j, k; вещ t;i := (-1); j := n;цикл пока i+1 < m или m < j-1| инвариант: a[0], a[1], ..., a[i] < a[m] и| a[m] <= a[j], a[j+1], ..., a[n-1] и| i < m и m < j|| если i+1 < m| | то| | если a[i+1] < a[m]| | | то i := i+1; // расширяем левую часть| | иначе если j-1 > m| | | иначе| | | утверждение: a[i+1] >= a[m];| | | // меняем местами элементы a[i+1] и a[j-1]| | | t := a[i+1]; a[i+1] := a[j-1]; a[j-1] := t;| | | если j-1 == m| | | | то m := i+1; // новое положение медианы| | | конец если| | | j := j-1; // расширяем правую часть| | конец если| | иначе| | утверждение: j-1 > m;| | . . . // этот случай рассматривается аналогично| | . . . // случаю i+1 < m| || конец есликонец циклаутверждение: 0 <= m и m < n и a[0], a[1], ..., a[m-1] < a[m] и a[m] <= a[m+1], a[m+2], ..., a[n-1]