Рассмотрим следующую функцию, аргументами которой являются два целых неотрицательных числа: int f(int m, int n) { // дано: m >= 0 и n >= 0 int a = m; int b = n; int c = 1; while (a != 0 && b != 0) { if (a%2 == 0 && b%2 == 0) { // a и b четные a /= 2; b /= 2; c *= 2; } else if (a%2 == 0) { // a четное, b нечетное a /= 2; } else if (b%2 == 0) { // a нечетное, b четное b /= 2; } else { // a и b нечетные if (a > b) { a -= b; } else { b -= a; } } } // end while return c*(a + b); } Какое условие является инвариантом цикла? (Через НОД и НОК обозначены наибольший общий делитель и наименьшее общее кратное.)

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

• # К массиву a длины 12 применяется восходящая схема двунаправленного алгоритма сортировки слиянием с использованием дополнительной памяти. В процессе выполнения алгоритма многократно вызывается функция merge слияния двух упорядоченных массивов длины n и m. Каковы длины массивов, которые сливаются при самом последнем вызове функции merge?
• # Сколько раз в алгоритме Гаусса будет выполнена операция перестановки местами двух строк (с изменением знака одной из них) при приведении к ступенчатому виду следующей матрицы: 1 2 3 4 0 1 2 3 2 5 8 11
• # Укажите, какие из приведенных ниже строк языка C/C++ корректно описывают объекты языка.
• # Функция F последовательности цифр в десятичной записи числа n ставит в соответстие единицу, если n делится на 14, и ноль в противном случае. Какая из приведенных ниже функций на последовательности десятичных цифр числа n является индуктивным расширением функции F?
• # Рассмотрим следующий фрагмент программы, вычисляющей частное q и остаток r от деления целых чисел a, b: // дано: целые числа a >= 0, b > 0 int a, b; . . . int q = 0, r = a; int e = 1, m = b; while (r >= b) { if (2*m <= r) { e *= 2; m *= 2; } else if (m > r) { e /= 2; m /= 2; } else { // утверждение: m <= r && r < 2*m q += e; r -= m; } } // q и r - частное и остаток от деления a на b Какое условие является инвариантом цикла?