Рассмотрим следующую функцию, аргументами которой являются два целых неотрицательных числа: int f(int m, int n) { int a = m, b = n; int p = 0; while (b != 0) { if (b%2 == 0) { // b четное b /= 2; a *= 2; } else { // b нечетное --b; p += a; } } return p; } Какое условие является инвариантом цикла?

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

• # В алгоритме получения записи числа n в системе счисления с основанием b мы вычисляем цифры числа справа налево, начиная с последней цифры. На очередном шаге мы делим n с остатком на b, получая частное q и остаток r; остаток представляет очередную цифру числа в порядке справа налево. Затем мы переменной n присваиваем значение частного q, и процесс повторяется, пока n не станет равным нулю. Сколько раз будет выполнена операция деления при переводе числа 2000000 (два миллиона) в восьмеричную систему счисления?
• # Какое максимальное число операций деления может быть выполнено в алгоритме Гаусса в процессе приведения к ступенчатому виду прямоугольной матрицы, содержащей 3 строки и 4 столбца?
• # Каков диапазон целочисленного типа unsigned char?
• # Рассмотрим следующую функцию, аргументами которой являются два целых неотрицательных числа: 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); } Какое условие является инвариантом цикла? (Через НОД и НОК обозначены наибольший общий делитель и наименьшее общее кратное.)
• # Алгоритм пузырьковой сортировки упорядочивает массив из 100 тысяч элементов примерно за 1 минуту. За какое примерно время тот же алгоритм упорядочит массив из 10 тысяч элементов?