Для записи n-значных чисел в системе счисления с основанием b требуется n разрядов, каждый из которых может находиться в b состояниях. Таким образом, суммарное число состояний равно произведению n*b. Рассмотрим двоичную (b=2), троичную (b=3) и десятичную (b=10) системы счисления. Какая из них наиболее экономна по суммарному числу состояний для записи чисел в диапазоне 0..N, где N - некоторое достаточно большое число?

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

• # Завершится ли когда-нибудь выполнение цикла в приведенном ниже фрагменте программы? int x = 1; while (x != 56) { x = (x * 11) % 253; }
• # Формула Бинома Ньютона дает следующее разложение в ряд для функции "кубический корень из z" (обозначим ее croot(z)): (1+x)1/3 = croot(1+x) = 1 + (1/3)x + (1/3)(-2/3)/2! x2 + (1/3)(-2/3)(-5/3)/3! x3 + (1/3)(-2/3)(-5/3)(-8/3)/4! x4 + ... (мы сделали замену z=1+x). Этот ряд сходится лишь для значений x, по абсолютной величине не превосходящих 1, а эффективно вычислять его сумму можно только для еще более узкого интервала значений x. Каким свойством функции croot(z)=z1/3 удобнее всего воспользоваться, чтобы свести ее вычисление для положительных значений z к суммированию ряда?
• # Чему равен ранг следующей матрицы: 1 1 1 1 1 -1 1 -1 1 1 -1 -1
• # В функции с прототипом int f(int x); которая вызывается часто в различных контекстах и должна работать быстро, нам требуется небольшой массив целых чисел размером в 16 элементов. Какое из перечисленных ниже решений является наиболее правильным?
• # Пусть 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