Сколько раз будет выполнено тело цикла в алгоритме Евклида int gcd(int m, int n) { while (n != 0) { int r = m % n; m = n; n = r; } return m; } при следующих входных значениях аргументов: m=24, n=30?

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

• # К трехзначным десятичным числам (строкам длины 3 из десятичных цифр) применяется алгоритм RADIX-сортировки сначала по младшей цифре, затем по средней и в конце по старшей. Исходный массив содержит следующие числа: 122, 232, 171, 198, 401, 035, 077, 201, 199, 400. Каким будет содержимое массива после выполнения первых двух шагов сортировки (т.е. после сортировки по младшей и средней цифрам)?
• # Сортируемый массив содержит составные ключи из 20 десятичных цифр (например, идентификаторы банковских счетов). Массив имеет длину 1000. Надо выбрать один из двух алгоритмов сортировки: сортировку кучей HeapSort или RADIX-сортировку. Какой из двух алгоритмов будет в среднем работать быстрее в данной ситуации?
• # Интерполяционный многочлен в форме Ньютона, построенный по узлам 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 многочлена pn(x) уже вычислены. Мы добавляем новый узел xn+1, значение в котором должно быть равно yn+1, и строим новый многочлен Ньютона pn+1(x) на единицу большей степени по узлам x0, x1, ..., xn, xn+1 и значениям y0, y1, ..., yn, yn+1. Сколько действий нужно выполнить, чтобы вычислить все коэффициенты нового многочлена?
• # Пусть целочисленный массив содержит элементы 11, 18, 10, 7, 15, 9, 8 в указанном порядке. Услове пирамиды нарушается только для элемента 11, стоящего в вершине пирамиды. Для исправления пирамиды выполняется процедура просеивания, при которой элемент 11 опускается на свое место. Каким будет содержимое массива после окончания этой процедуры?
• # К целочисленному массиву применяется алгоритм сортировки кучей. Пусть после первого этапа алгоритма пирамида (бинарная куча) уже построена и массив содержит элементы 30, 20, 25, 10, 7, 19, 5 в указанном порядке. Затем выполняется второй этап сортировки. На его первом шаге начальный и конечный элементы массива меняются местами, от пирамиды отрезается правая нижняя ветка (т.е. последний элемент массива), затем элемент в вершине пирамиды просеивается, благодаря чему восстанавливается условие пирамиды. Каким будет содержимое массива по окончании этого шага?