Пусть a - целочисленный массив размера n(индекс элементов меняется от 0 до n-1),элементы которого строго возрастают:a[0] < a[1] <... < a[n-1].Определить, содержит ли следующий фрагмент программы ошибку(т.е. действительно ли тело цикла сохраняет инвариант):

// Программа Поиск    int n; int *a;    . . .    // дано: целое n;    //       целочисленный массив a[n],    //           элементы которого строго возрастают    //           a[0] < a[1] < ... < a[n-1]    // надо: найти элемент x в массиве    int x;          // искомый элемент    . . .           // рассматриваются исключительные случаи    // общий случай    // утверждение: a[0] < x  &&  x <= a[n-1];    int b = 0; int e = n - 1;    while (e - b > 1) {        Invariant: a[b] < x  &&  x <= a[e]        int c := (a + b)/2; // c - целая часть (a+b)/2        if (x < a[c]) {            e = c;  // выбираем левую половину отрезка        } else {            b = c;  // выбираем правую половину        }    }    // утверждение: b == e - 1   &&    //              a[b] < x  &&  x <= a[e]

Пусть f(x) - целочисленная функция от целочисленногоаргумента. Определить,содержит ли следующий фрагмент программы ошибку(т.е. действительно ли тело цикла сохраняет инвариант):

// Программа корень функции    int a, b, c;    . . .    // утверждение: a < b  && f(a)*f(b) <= 0    // Значения функции на концах отрезка [a,b] разных знаков    while (b - a > 1) {        // Invariant: f(a)*f(b) <= 0        // Делим отрезок [a, b] пополам        c = (a + b)/2; // c - целая часть (a+b)/2        if (f(a) * f(c) < 0) {            b = c;     // выбираем левую половину отрезка        } else {            a = c;     // выбираем правую половину        }    }    // утверждение: a == b-1  &&    //              f(a)*f(b) <= 0

Пусть f(x) - вещественная функция функцияот вещественногоаргумента. Определить,содержит ли следующий фрагмент программы ошибку(т.е. действительно ли тело цикла сохраняет инвариант):

// Программа корень функции    double a, b, c;    double eps = 0.000001;    . . .    // утверждение: a < b  && f(a)*f(b) <= 0.0    // Значения функции на концах отрезка [a, b] разных знаков    while (b - a > eps) {        // Invariant: f(a)*f(b) <= 0.0        // Делим отрезок [a, b] пополам        c = (a + b)/2.0; // c - середина отрезка [a, b]        if (f(a) * f(c) < 0.0) {            b = c;     // выбираем левую половину отрезка        } else {            a = c;     // выбираем правую половину        }    }    // утверждение: b - a <= eps  &&    //              f(a)*f(b) <= 0.0

Пусть дан массив a длины n,элементы которого нестрого возрастают, т.е. соседниеэлементы могут быть равными.Рассмотрим фрагмент программы бинарного поискаэлемента x в массивеa длины n, гдепосле отбрасывания особых ситуаций рассматриваетсяосновной случай:

        . . .        // Утверждение: a[0] <= x && x < a[n-1]        int beg = 0; int end = n-1;        while (end-beg > 1) {            // Инвариант: a[beg] <= x && x < a[end]            int c = (beg + end) / 2;            if (a[c] <= x) {                beg = c;            } else {                end = c;            }        }        if (a[beg] == x) {            *idx = beg;        } else  {            *idx = end;        }        . . .

Пусть значение x содержится в массивев нескольких экземплярах. Индекс какого элементамассива a будет записан в переменную *idx?

Пусть дан массив a длины n,элементы которого нестрого возрастают, т.е. соседниеэлементы могут быть равными.Рассмотрим фрагмент программы бинарного поискаэлемента x в массивеa длины n, гдепосле отбрасывания особых ситуаций рассматриваетсяосновной случай:

        . . .        // Утверждение: a[0] < x && x <= a[n-1]        int beg = 0; int end = n-1;        while (end-beg > 1) {            // Инвариант: a[beg] < x && x <= a[end]            int c = (beg + end) / 2;            if (a[c] < x) {                beg = c;            } else {                end = c;            }        }        *idx = end;        . . .

Пусть значение x содержится в массивев нескольких экземплярах. Индекс какого элементамассива a будет записан в переменную *idx?

Пусть дан массив a длины n,элементы которого нестрого возрастают, т.е. соседниеэлементы могут быть равными.Рассмотрим фрагмент программы бинарного поискаэлемента x в массивеa длины n, гдепосле отбрасывания особых ситуаций рассматриваетсяосновной случай:

        . . .        // Утверждение: a[0] < x && x <= a[n-1]        int beg = 0; int end = n-1;        while (end-beg > 1) {            // Инвариант: a[beg] < x && x <= a[end]            int c = (beg + end) / 2;            if (a[c] < x) {                beg = c;            } else if (a[c] > x) {                end = c;            } else {                // Утверждение: x == a[c]                *idx = c;                return true;            }        }        *idx = end;        return (x >= a[end]);        . . .

Пусть значение x содержится в массивев нескольких экземплярах. Индекс какого элементамассива a будет записан в переменную *idx?

Следующий фрагмент программы для последовательностивещественных чисел вычисляет количество n элементов,строго меньших предыдущего, причем самый первый элемент такжеучитывается (считается меньше предыдущего).Например, для последовательности{2, 1, 3, 5, 4} ответ n=3(элементы 2, 1 и 4).

n = 0x0 = ...цикл пока в последовательности есть непрочитанные элементы|выполнять|  прочесть очередной элемент посл-ти в <вых: x>|  если x < x0|  | то n = n + 1|  конец если|  x0 = xконец цикла

Каким значением надо инициализировать переменнуюx0, чтобы программа работала правильно?

Следующий фрагмент программы для последовательностивещественных чисел вычисляет количество n элементов,строго больших предыдущего, причем самый первый элемент неучитывается (не считается больше предыдущего).Например, для последовательности{2, 1, 3, 5} ответ n=2(элементы 3 и 5).

n = 0x0 = ...цикл пока в последовательности есть непрочитанные элементы|выполнять|  прочесть очередной элемент посл-ти в <вых: x>|  если x > x0|  | то n = n + 1|  конец если|  x0 = xконец цикла

Каким значением надо инициализировать переменнуюx0, чтобы программа работала правильно?

Пусть элементы массива aнестрого возрастают (соседние элементы могут быть равными).Дано произвольное значение x, требуетсянайти минимальный индекс i такой, чтоa[i] >= x. Используется идея алгоритмабинарного поиска. Каким должен быть инвариант цикла,в котором рассматривается основной случай после отбрасыванияисключительных ситуаций?(Условие завершения циклаend == beg+1.)

Пусть элементы массива aнестрого возрастают (соседние элементы могут быть равными).Дано произвольное значение x, требуетсянайти максимальный индекс i такой, чтоa[i] <= x. Используется идея алгоритмабинарного поиска. Каким должен быть инвариант цикла,в котором рассматривается основной случай после отбрасыванияисключительных ситуаций?(Условие завершения циклаend == beg+1.)

Пусть элементы массива aнестрого возрастают (соседние элементы могут быть равными).Дано произвольное значение x, требуетсянайти максимальный индекс i такой, чтоa[i] <= x. Используется идея алгоритмабинарного поиска. В приведенном ниже циклерассматривается основной случай после отбрасыванияисключительных ситуаций:

    while (end-beg > 1) {        int c = (beg+end)/2;        if (a[c] <= x)            beg = c;        else            end = c;    }    // ответ в переменной beg

Какое утверждение являетсяинвариантом этого цикла?