К трехзначным десятичным числам (строкам длины 3 из десятичных цифр) применяется алгоритм RADIX-сортировки сначала по младшей цифре, затем по средней и в конце по старшей. Исходный массив содержит следующие числа: 232, 102, 307, 901, 835, 215, 105, 301, 323, 811. Каким будет содержимое массива после выполнения первых двух шагов сортировки (т.е. после сортировки по младшей и средней цифрам)?

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

• # Формула Бинома Ньютона дает следующее разложение в ряд для функции "кубический корень из 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 к суммированию ряда?
• # Укажите минимальное значение x > 0 типа signed char, удовлетворяющее неравенству x+x <= 0?
• # Назовем функцию y = f(p) на последовательности p элементов некоторого типа индуктивной, если при добавлении в конец последовательности p еще одного элемента x новое значение функции y1 = f(p&x) можно вычислить, зная только старое значение y и добавленный элемент x. Среди перечисленных ниже функций на последовательностях вещественных чисел укажите индуктивные.
• # Для конкретного массива длины 1000 применяются алгоритмы пузырьковой сортировки и сортировки методом прямого выбора. Какой из этих двух алгоритмов работает быстрее?
• # Целочисленный массив содержит элементы 20, 18, 10, 15, 7, 7, 9, 8, 10, 6, 4, 5 в указанном порядке. Образуют ли они бинарную кучу (пирамиду)?