игра брюс 2048
Главная / Программирование / Основы программирования - обучения основам / Тест 5

Основы программирования - обучения основам - тест 5

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

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

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

Ответ:

 (1) Условие (не A(x) и B(x)).  

 (2) Условие (A(x) и B(x)).  

 (3) Условие (A(x) и не B(x)).  

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

Ответ:

 (1) Да, выполняется.  

 (2) Не обязательно.  

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

Ответ:

 (1) Перед первым выполнением тела цикла и после последнего выполнения тела цикла.  

 (2) Перед каждым выполнением тела цикла.  

 (3) Перед каждым выполнением тела цикла и после каждого выполнения тела цикла.  

Упражнение 2:
Номер 1 
Указать, что вычисляет следующий фрагмент программы:

дано: цел n;
цел s, k;
s := 2; k := 0;
цикл пока s <= n
| инвариант: s = 2k+1
| s := s * 2; k := k + 1;
конец цикла
ответ := k;

Ответ:

 (1) Целую часть квадратного корня из n.  

 (2) Целую часть от log2 n.  

Номер 2 
Указать, что вычисляет следующий фрагмент программы:

дано: цел n;
цел x, y;
x := 1; y := 4;
цикл пока y <= n
| инвариант: y = (x + 1)2;
| x := x + 1;
| y := y + 2*x + 1;
конец цикла
ответ := x;

Ответ:

 (1) Целую часть от n / 2;  

 (2) Целую часть квадратного корня из n.  

 (3) Целую часть от log2 n.  

Номер 3 
Указать, что вычисляет следующий фрагмент программы:

дано: цел n;
цел s, k;
s := 10; k := 0;
цикл пока s <= n
| инвариант: s = 10 * (k + 1)
| s := s + 10; k := k + 1;
конец цикла
ответ := k;

Ответ:

 (1) Целую часть частного n/10.  

 (2) Произведение 10·n.  

 (3) Целую часть десятичного логарифма log10 n.  

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

    цел m, n;
    цел a, b, p;
    . . .
    a := m; b := n;
    p := 0;
    цикл пока b != 0
    | если b четное
    | | то
    | |     b := b / 2;
    | |     a := a * 2;
    | | иначе
    | |     b := b - 1;
    | |     p := p + a;
    | конец если
    конец цикла
    ответ := p;

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

Ответ:

 (1) Равенство ab p = mn.  

 (2) Равенство a b + p = m n.  

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

    цел m, n;
    . . .
    дано: m >= 0 и n >= 0
    цел a, b, c;
    a := m; b := n;
    c := 1;
    цикл пока a != 0 и b != 0
    | если a четное и b четное
    | | то  a := a / 2;
    | |     b := b / 2;
    | |     c := c * 2;
    | иначе если a четное
    | | то  a := a / 2;
    | иначе если b четное
    | | то  b := b / 2;
    | иначе
    | | если a > b
    | | | то    a := a - b;
    | | | иначе b := b - a;
    | | конец если
    | конец если
    конец цикла
    ответ := c * (a + b);

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

Ответ:

 (1) Равенство НОД(a, b) = НОД(m, n)·c.  

 (2) Равенство НОК(m, n) = c·(a + b).  

 (3) Равенство НОД(a,b)·c = НОД(m, n).  

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

  дано: целые числа a >= 0, b > 0
  цел q, r, e, m;

  q := 0; r := a; e := 1; m := b
  цикл пока r >= b
  | если 2*m <= r
  | | то e := e*2; m := m*2;
  | иначе если m > r
  | | то e := e/2; m := m/2;
  | иначе
  | | утверждение: m <= r  и  r < 2*m
  | | q := q + e; r := r - m;
  | конец если
  конец цикла

  // q и r -- частное и остаток от деления a на b

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

Ответ:

 (1) Число e является степенью двойки, а также выполняются равенства a - q·b = r и m = e·b.  

 (2) Число e является степенью двойки, а также выполняются равенства a - q·m = r и m = e·b.  

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

вещ r, x; цел n;
. . .
r := r * x * x;
r := r / ((n + 1) * (n + 2));
n := n + 2;

Ответ:

 (1) Утверждение r = xn / n!, где восклицательным знаком обозначен факториал числа n.  

 (2) Утверждение r = xn / ((n+1)·(n+2)).  

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

вещ r, x; цел n;
. . .
r := -r * x;
r := r * n / (n + 1);
n := n + 1;

Ответ:

 (1) Утверждение r = (-1)n xn/n!, где восклицательным знаком обозначен факториал числа n.  

 (2) Утверждение r = (-1)n-1 xn/n.  

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

цел n, k, c;
. . .
c := c * (n + 1);
c := c/(n + 1 - k);
n := n + 1;

Ответ:

 (1) Утверждение c = n! / (k! (n-k)!).  

 (2) Утверждение c = (n+k)! / (n! (n-k)!).  

 (3) Утверждение c = (k)! / (n! (n-k)!).  

Упражнение 5:
Номер 1 
Оценить сверху время работы (т.е. количество
выполнений тела цикла) алгоритма Евклида
вычисления НОД двух целых чисел:

дано: целые числа m, n, хотя бы одно отлично от нуля
надо: вычислить наибольший общий делитель пары (m, n)
цел a, b, r;
a := m; b := n;

цикл пока b != 0
| инвариант: НОД(a, b) == НОД(m, n)
| r := a % b;     // находим остаток от деления a на b
| a := b; b := r; // заменяем пару (a, b) на (b, r)
конец цикла

ответ := a;

Ответ:

 (1) Время работы не больше, чем C·log2 max(m, n), где C — некоторая константа (т.е. время пропорционально количеству цифр в двоичной или десятичной записи максимального из чисел m, n).  

 (2) Время работы не больше, чем C·r, где C — некоторая константа, r — квадратный корень из max(m, n) (т.е. время пропорционально квадратному корню из максимального числа).  

 (3) Время работы не больше, чем C·max(m, n), где C — некоторая константа (т.е. время пропорционально максимальному из чисел m, n).  

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

дано: основание a и показатель степени n >= 0
надо: вычислить a в степени n
вещ b, p; цел k;
b := a; p := 1.0; k := n;

цикл пока k > 0
| инвариант: bk p = an
| если k четное
| | то
| |   k := k / 2;
| |   b := b * b;
| | иначе
| |   k := k - 1;
| |   p := p * b;
| конец если
конец цикла

ответ := p;

Ответ:

 (1) Время работы не больше, чем C·n, где C — некоторая константа (т.е. время пропорционально числу n).  

 (2) Время работы не больше, чем C·log2 n, где C — некоторая константа (т.е. время пропорционально количеству цифр в двоичной или десятичной записи числа n).  

 (3) Время работы не больше, чем C·r, где C — некоторая константа, r — квадратный корень из числа n (т.е. время пропорционально квадратному корню из n).  

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

дано: x > 0, a > 1, ε > 0
надо: вычислить loga x с точностью ε
вещ y, z, t;
y := 0.0; z := x; t := 1.0;

цикл пока |t| >= ε или z <= 1.0/a или z >= a
| инвариант: ay * zt = x
| если z >= a
| | то
| |   z := z/a; y := y + t;
| иначе если z <= 1.0/a
| | то
| |   z := z*a; y := y - t;
| иначе
| |   z := z*z; t := t/2.0;
| конец если
конец цикла

ответ := y;

Ответ:

 (1) Время работы не больше, чем C·log2 [x+1], где C — некоторая константа, [x+1] — целая часть числа x+1 (т.е. время пропорционально количеству цифр в двоичной или десятичной записи целой части числа x).  

 (2) Время работы не больше, чем C·log2 [x+1]·log2 (1/ε), где C — некоторая константа, а квадратные скобки обозначают целую часть. Иначе говоря, время пропорционально количеству цифр в двоичной или десятичной записи целой части x, умноженному на требуемое количество значащих цифр в дробной части результата.  

 (3) Время работы не больше, чем C·log2 [x+1] + log2 (1/ε), где C — некоторая константа, а квадратные скобки обозначают целую часть. Иначе говоря, время пропорционально сумме количества цифр в двоичной или десятичной записи целой части x и требуемого количества значащих цифр в дробной части результата.  

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

// Программа корень функции
цел a, b, c;
. . .
утверждение: a < b  и  f(a) * f(b) <= 0;
// Значения функции на концах отрезка [a,b] разных знаков

цикл пока b - a > 1
| инвариант: f(a) * f(b) <= 0
| // Делим отрезок [a, b] пополам
| c := (a + b) / 2; // c -- целая часть (a+b)/2
| если f(a) * f(c) < 0
| | то    b := c;   // выбираем левую половину отрезка
| | иначе a := c;   // выбираем правую половину отрезка
| конец если
конец цикла

утверждение: a == b - 1  и  f(a) * f(b) <= 0;

Ответ:

 (1) Ошибки нет, фрагмент программы корректный.  

 (2) Фрагмент программы содержит ошибку.  

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

// Программа Поиск
дано: цел n;
      цел a[n]; // a[0] < a[1] < ... < a[n-1]
цел x;          // искомый элемент
цел b, e, c;
. . .           // рассматриваются исключительные случаи
утверждение: a[0] < x  и  x <= a[n-1];  // общий случай
b := 0; e := n - 1;

цикл пока e - b > 1
| инвариант: a[b] < x  и  x <= a[e];
| c := (b + e) / 2; // c -- целая часть (b+e)/2
| если x < a[c]
| | то    e := c;   // выбираем левую половину отрезка
| | иначе b := c;   // выбираем правую половину отрезка
| конец если
конец цикла

утверждение: b == e - 1  и
             a[b] < x  и  x <= a[e];

Ответ:

 (1) Ошибки нет, фрагмент программы корректный.  

 (2) Фрагмент программы содержит ошибку.  

Номер 3 
Пусть 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]

Ответ:

 (1) Ошибки нет, фрагмент программы корректный.  

 (2) Фрагмент программы содержит ошибку.  



Главная / Программирование / Основы программирования - обучения основам / Тест 5