Оценить сверху время работы (т.е. количество выполнений тела цикла) алгоритма Евклида вычисления наибольшего общего делителя двух целых чисел: int gcd(int m, int n) { // дано: целые числа m, n, хотя бы одно отлично от нуля // надо: вычислить НОД пары (m, n) int a = m, b = n; while (b != 0) { // Invariant: НОД(a, b) == НОД(m, n) int r := a % b; // находим остаток от деления a на b a = b; b = r; // заменяем пару (a, b) на (b, r) } return a; // ответ = a }

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

• # Алгоритм сортировки называется стабильным, если он сохраняет относительный порядок равных элементов. Среди перечисленных ниже алгоритмов сортировки (имеются в виду их классические варианты) отметьте все стабильные.
• # При представлении целых чисел в формате Big Endian байты внутри слова нумеруются слева направо, в формате Little Endian - справа налево. Пусть компьютер использует архитектуру Big Endian. Укажите, чему будет равно значение переменной n в результате выполнения следующего фрагмента программы: int k = (-2); int n; signed char *p = (signed char *) &k; n = *p;
• # Функция ln(z) (натуральный логарифм z) представляется в виде степенного ряда следующим образом: ln(1+x) = x - x2/2 + x3/3 - x4/4 + ... (мы обозначили z=1+x). Этот ряд сходится лишь для значений x, по абсолютной величине не превосходящих 1, а эффективно вычислять его сумму можно только для еще более узкого интервала значений x. Какими свойствами функции ln(z) удобнее всего воспользоваться, чтобы свести ее вычисление к суммированию ряда?
• # Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия. При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче. Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл. Задание: переставить элементы массива в обратном порядке.
• # Алгоритм пузырьковой сортировки упорядочивает массив из 100 тысяч элементов примерно за 1 минуту. За какое примерно время тот же алгоритм упорядочит массив из 10 тысяч элементов?