Пусть элементы массива 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 Какое утверждение является инвариантом этого цикла?

Правильный ответ:

• # Рассмотрим следующую запись числа в троичной системе счисления (для удобства запись разбита запятыми на четверки): 1201,1122,2111,2010. Укажите запись этого числа в системе счисления с основанием 9.
• # Функция 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 ее можно применять? Укажите все правильные ответы из числа перечисленных ниже.
• # Пусть функция f(x) = p*x2 + q*x + r (многочлен степени 2), заданная на отрезке [a, b], принимает значения y0, y1, y2 в точках a, (a+b)/2, b (на концах и в середине отрезка). Чему равен интеграл от этой функции по отрезку [a, b]?
• # Назовем функцию y = f(p) на последовательности p элементов некоторого типа индуктивной, если при добавлении в конец последовательности p еще одного элемента x новое значение функции y1 = f(p&x) можно вычислить, зная только старое значение y и добавленный элемент x. Среди перечисленных ниже функций на последовательностях вещественных чисел укажите индуктивные.
• # Массив a размера 4 содержит элементы 4, 2, 1, 3 в указанном порядке. К нему применяется алгоритм пузырьковой сортировки, использующий сравнение элементов с помощью функции compare и обмен элементов с помощью функции swap. Сколько раз будет вызвана функция swap?