Оцените примерно, во сколько раз алгоритм бинарного поиска работает быстрее алгоритма последовательного поиска для массива из 64 миллионов элементов.

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

• # При вычислении (x+y)7 раскрываются скобки и приводятся подобные члены. Чему будет равен коэффициент при x3y4?
• # Формула Бинома Ньютона дает следующее разложение в ряд для функции "квадратный корень из z": (1+x)0.5 = sqrt(1+x) = 1 + 0.5 x + 0.5(-0.5)/2! x2 + 0.5(-0.5)(-1.5)/3! x3 + 0.5(-0.5)(-1.5)(-2.5)/4! x4 + ... (мы обозначили z=1+x). Рассмотрим реализованную на C/C++ функцию mySqrt(z), вычисляющую значение квадратного корня с точностью до одной миллионной: static const double EPS = 1e-6; double mySqrt(double z) { double x = z - 1.; double s = 1; double k = 0.5; double n = 1.; double a = k*x; while (fabs(a) > eps) { s += a; k -= 1.; n += 1.; a *= (k/n)*x; } return s; } Для каких значений z ее можно применять так, чтобы функция завершала работу за разумное время и ошибка вычисления результата была бы не более 0.0001? Укажите все правильные ответы из числа перечисленных ниже.
• # Рассмотрим следующий фрагмент программы на C++: double a[5][3]; const double *p = &(a[0][0]); const double *q = &(a[2][2]); int n = q - p; Чему равно значение n после выполнения этого фрагмента?
• # Интерполяционный многочлен в форме Ньютона, построенный по узлам x0, x1, ..., xn и принимающий в этих узлах значения y0, y1, ..., yn, представляется формулой pn(x) = a0 + a1(x-x0) + a1(x-x0)(x-x1) + ... + an(x-x0)(x-x1)...(x-xn-1) Сколько действий нужно выполнить, чтобы вычислить все его коэффициенты a0, a1, ..., an?
• # Укажите, чему будет равно значение переменной k в результате выполнения следующего фрагмента программы: int n=11, k, *p; p = &n; ++*p; k = 4-*p*2+n;