Рассмотрим реализацию матрицы вещественных чисел размера m строк на n столбцов при помощи линейного массива, в котором хранятся сначала элементы нулевой строки матрицы, затем первой и т.д., в конце - элементы (m-1)-й строки: int m, n; // Размеры матрицы: число строк, столбцов . . . double* a = new double[m*n]; // a[i*n + j] -- элемент i-й строки и j-го столбца Пусть функция с прототипом void transp(double* a, int m, int n); реализует транспонирование матрицы, при выполнении которого строки матрицы становятся столбцами, столбцы - строками, а матрица размера m на n превращается в матрицу размера n на m Пусть эта функция применяется к прямоугольной матрице, содержащей 3 строки и 5 столбцов, элементы которой хранятся в линейном массиве a. Сколько элементов массива a при этом останутся на своем месте?

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

• # Дан массив длины 11, требуется циклически сдвинуть его элементы вправо на 3 позиции. Какое минимальное число операций копирования выполняется в любом алгоритме, решающем данную задачу? Имеются в виду операции копирования одного элемента массива в другой, элемента массива в простую переменную, одной простой переменной в другую.
• # Дан массив длины 12, требуется циклически сдвинуть его элементы влево на 5 позиций. Какое минимальное число операций копирования выполняется в любом алгоритме, решающем данную задачу? Имеются в виду операции копирования одного элемента массива в другой, элемента массива в простую переменную, одной простой переменной в другую.
• # Камень, отпущенный с высоты 6-го этажа, падает на землю примерно за 2 сек. За какое примерно время упадет камень с высоты 12-го этажа (в 2 раза большей)? Сопротивлением воздуха пренебречь.
• # Пусть f(x) - вещественная функция функция от вещественного аргумента. Определить, содержит ли следующий фрагмент программы ошибку (т.е. действительно ли тело цикла сохраняет инвариант): // Программа корень функции double a, b, c; double eps = 0.000001; . . . // утверждение: a < b && f(a)*f(b) <= 0.0 // Значения функции на концах отрезка [a, b] разных знаков while (b - a > eps) { // Invariant: f(a)*f(b) <= 0.0 // Делим отрезок [a, b] пополам c = (a + b)/2.0; // c - середина отрезка [a, b] if (f(a) * f(c) < 0.0) { b = c; // выбираем левую половину отрезка } else { a = c; // выбираем правую половину } } // утверждение: b - a <= eps && // f(a)*f(b) <= 0.0
• # Алгоритм сортировки называется стабильным, если он сохраняет взаимный порядок равных элементов. (Такое определение имеет смысл при сортировке массива записей, состоящих из нескольких полей, которые сравниваются лишь по значению одного конкретного поля - например, записи о людях сортируются по их именам, при этом могут быть однофамильцы.) Является ли алгоритм быстрой сортировки стабильным?