Сколько раз будет выполнено тело цикла в приведенной ниже программе? Многоточием обозначен фрагмент, не содержащий переменной x. int x = 100; while (x >= 0) { . . . x = x-1; }

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

• # Дан массив длины n, требуется циклически сдвинуть его элементы вправо на одну позицию. Какое минимальное число операций копирования выполняется в любом алгоритме, решающем данную задачу? Имеются в виду операции копирования одного элемента массива в другой, элемента массива в простую переменную, одной простой переменной в другую.
• # Рассмотрим реализацию матрицы вещественных чисел, размеры которой определяются в процессе работы программы, через массив указателей на начала строк, захватываемый в динамической памяти. Каждая строка также представляет собой отдельный массив в динамической памяти: typedef double* doubleptr; int m, n; // Размеры матрицы: число строк, столбцов . . . doubleptr* a = new doubleptr[m]; for (int i = 0; i < m; ++i) { a[i] = new double[n]; } // a[i][j] -- элемент i-й строки и j-го столбца Сколько обращений к памяти необходимо сделать, чтобы прочесть элемент матрицы в i-й строке и j-м столбце (считая, что значения i и j уже находятся в регистрах процессора)?
• # Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел. Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности. Программа должна содержать функцию, которая получает в качестве параметра имя файла и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл. Задание: найти максимальное количество элементов между двумя соседними локальными минимумами последовательности (локальный минимум - элемент строго меньший своих соседей).
• # Пусть m=143. Существуют ли два различных целых числа a, b такие, что a2b2 (mod m), но a±b (mod m)?
• # Оценить сверху время работы (т.е. количество выполнений тела цикла) алгоритма приблизительного вычисления логарифма: double myLog(double x, double a, double eps) { // дано: x > 0, a > 1, eps > 0 // надо: вычислить log_a x с точностью eps double y = 0.0, z = x, t = 1.0; while ( fabs(t) > eps || x <= 1.0/a || z >= a ) { // Invariant: a^y * z^t == x if (z >= a) { z /= a; y += t; } else if (z <= 1.0/a) { z *= a; y -= t; } else { z *= z; t /= 2.0; } } return y; }