Рассмотрим следующую функцию, аргументами которойявляются два целых неотрицательных числа:

int f(int m, int n) {    // дано: m >= 0 и n >= 0    int a = m; int b = n;    int c = 1;    while (a != 0 && b != 0) {        if (a%2 == 0 && b%2 == 0) {            // a и b четные            a /= 2; b /= 2;            c *= 2;        } else if (a%2 == 0) {            // a четное, b нечетное            a /= 2;        } else if (b%2 == 0) {            // a нечетное, b четное            b /= 2;        } else {            // a и b нечетные            if (a > b) {                a -= b;            } else {                b -= a;            }        }    } // end while    return c*(a + b);}

Какое условие является инвариантом цикла?(Через НОД и НОК обозначены наибольший общий делитель инаименьшее общее кратное.)

Рассмотрим следующую функцию, аргументами которойявляются два целых неотрицательных числа:

int f(int m, int n) {    int a = m, b = n;    int p = 0;    while (b != 0) {        if (b%2 == 0) { // b четное            b /= 2;            a *= 2;        } else { // b нечетное            --b;            p += a;        }    }    return p;}

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

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма быстрого возведения в степень:

int fastPow(double a, int n) {    // дано: основание a и показатель степени n >= 0    // надо: вычислить a в степени n    double b = a, p = 1.0; int k = n;    while (k > 0) {        // Invariant: b^k * p == a^n        if (k%2 == 0) {            // k четное            k /= 2;            b *= b;        } else {            // k нечетное            --k;            p *= b;        }    }    return p;}

Рассмотрим максимальное по абсолютной величинецелое число, которое в языке C/C++ представимотипом short. Четное оно или нечетное?

Рассмотрим следующий фрагмент программы, вычисляющейчастное q и остаток r от деленияцелых чисел a, b:

    // дано: целые числа a >= 0, b > 0    int a, b;    . . .    int q = 0, r = a;    int e = 1, m = b;    while (r >= b) {        if (2*m <= r) {            e *= 2; m *= 2;        } else if (m > r) {            e /= 2; m /= 2;        } else {            // утверждение: m <= r && r < 2*m            q += e; r -= m;        }    }    // q и r - частное и остаток от деления a на b

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

Рассмотрим следующий фрагмент программы:

утверждение: A(x)цикл пока B(x)| инвариант: A(x)| x := T(x)конец цикла

Здесь через A(x) и B(x)обозначены условия, зависящие от переменной x.Какое условие выполняется по окончании цикла?

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма Евклидавычисления наибольшего общего делителя двух целых чисел:

int gcd(int m, int n) {    // дано: целые числа m, n, хотя бы одно отлично от нуля    // надо: вычислить НОД пары (m, n)    int a = m, b = n;    while (b != 0) {        // Invariant: НОД(a, b) == НОД(m, n)        int r := a % b; // находим остаток от деления a на b        a = b; b = r;   // заменяем пару (a, b) на (b, r)    }    return a;           // ответ = a}

Рассмотрим следующую запись числа в двоичной системе счисления(для удобства запись разбита запятыми на триады):

100,001,010,110,111,101,011.

Укажите восьмеричную запись этого числа.

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

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

Функция arctg(x) раскладываетсяв ряд Тейлора следующим образом:

    arctg(x) = x - x3/3 + x5/5 - x7/7 + ...

Рассмотрим реализованную на C/C++ функцию myAtan(x),вычисляющую значение arctg(x) с точностью до одной миллионной:

static const double EPS = 1e-6;double myAtan(double x) {    double s = 0.;    double p = x;    double n = 1.;    double a = x;    while (fabs(a) > EPS) {        s += a;        p = (-p*x*x);        n += 2.;        a = p/n;    }    return s;}

Для каких значений x ее можно применять?Укажите все правильные ответы из числа перечисленных ниже.