Программирование - тест 69

Упражнение 1:

---

Номер 1

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

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

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

Ответ:

---

Номер 2

Выполняется ли инвариант цикла в процессе выполнения
тела цикла?

Ответ:

---

Номер 3

Укажите, в какие моменты работы программы выполняется
инвариант цикла.

Ответ:

---

Упражнение 2:

---

Номер 1

Пусть целочисленная переменная n
содержит некоторое положительное целое число.
Указать, что вычисляет следующая функция f(n):

int f(int n) {
    int s = 2; int k = 0;
    while (s <= n) {
        // Invariant: s == 2^(k+1)
        s *= 2; ++k;
    }
    return k;
}

Ответ:

---

Номер 2

Пусть целочисленная переменная n
содержит некоторое положительное целое число.
Указать, что вычисляет следующая функция f(n):

int f(int n) {
    int x = 1; int y = 4;
    while (y <= n) {
        // Invariant: y == (x+1)^2
        ++x;
        y += 2*x+1;
    }
    return x;
}

Ответ:

---

Номер 3

Пусть целочисленная переменная n
содержит некоторое положительное целое число.
Указать, что вычисляет следующая функция f(n):

int f(int n) {
    int s = 10; int k = 0;
    while (s <= n) {
        // Invariant: s == 10*(k+1)
        s += 10; ++k;
    }
    return k;
}

Ответ:

---

Упражнение 3:

---

Номер 1

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

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;
}

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

Ответ:

---

Номер 2

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

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);
}

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

Ответ:

---

Номер 3

Рассмотрим следующий фрагмент программы, вычисляющей
частное 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

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

Ответ:

---

Упражнение 4:

---

Номер 1

Какое утверждение является инвариантом для следующего
фрагмента программы (т.е. из справедливости утверждения
до выполнения фрагмента программы вытекает справедливость утверждения
после выполнения)? Предполагается, что значение переменной
n неотрицательно.

    double r, x; int n;
    . . .
    r *= x*x;
    r /= ((n+1)*(n+2));
    n += 2;

Ответ:

---

Номер 2

Какое утверждение является инвариантом для следующего
фрагмента программы (т.е. из справедливости утверждения
до выполнения фрагмента программы вытекает справедливость утверждения
после выполнения)? Предполагается, что n > 0.

    double r, x; int n;
    . . .
    r *= -x;
    r *= n/(n+1);
    ++n;

Ответ:

---

Номер 3

Какое утверждение является инвариантом для следующего
фрагмента программы (т.е. из справедливости утверждения
до выполнения фрагмента программы вытекает справедливость утверждения
после выполнения)? Предполагается, что
n не меньше k.
Восклицательным знаком обозначается операция вычисления факториала.

    int n, k, c;
    . . .
    c *= (n+1);
    c /= (n+1-k);
    ++n;

Ответ:

---

Упражнение 5:

---

Номер 1

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

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
}

Ответ:

---

Номер 2

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

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;
}

Ответ:

---

Номер 3

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

double myLog(double x, double a, double eps) {
    // дано: x > 0, a > 1, eps > 0
    // надо: вычислить log_a x с точностью eps
    double y = 0.0, z = x, t = 1.0;

    while (
        fabs(t) > eps ||
        x <= 1.0/a ||
        z >= a
    ) {
        // Invariant: a^y * z^t == x
        if (z >= a) {
            z /= a; y += t;
        } else if (z <= 1.0/a) {
            z *= a; y -= t;
        } else {
            z *= z; t /= 2.0;
        }
    }
    return y;
}

Ответ:

---

Упражнение 6:

---

Номер 1

Пусть 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

Ответ:

---

Номер 2

Пусть 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]

Ответ:

---

Номер 3

Пусть 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

Ответ:

---