Для записи n-значных чисел в системе счисления с основанием b требуется n разрядов, каждый из которых может находиться в b состояниях. Таким образом, суммарное число состояний равно произведению n*b. Рассмотрим двоичную (b=2), восьмеричную (b=8) и шестнадцатеричную (b=16) системы счисления. Какая из них наиболее экономна по суммарному числу состояний для записи чисел в диапазоне 0..N, где N - некоторое достаточно большое число?

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

• # Функция merge слияния двух упорядоченных массивов применяется к двум массивам длины 10 и 20. Может ли в процессе ее выполнения быть сделано ровно 28 сравнений?
• # Дан массив длины 11, требуется циклически сдвинуть его элементы вправо на 3 позиции. Какое минимальное число операций копирования выполняется в любом алгоритме, решающем данную задачу? Имеются в виду операции копирования одного элемента массива в другой, элемента массива в простую переменную, одной простой переменной в другую.
• # Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия. При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче. Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл. Задание: для двух целочисленных массивов построить третий массив, являющийся их пересечением как числовых множеств без повторения элементов. Указать длину получившегося массива.
• # Левым нейтральным элементом (левой единицей) для бинарной операции называется элемент e такой, что для всякого другого элемента x "произведение" e на x равно x: e x = x. Какие элементы будут нейтральными для операций суммы и максимума чисел соответственно?
• # Какое утверждение является инвариантом для следующего фрагмента программы (т.е. из справедливости утверждения до выполнения фрагмента программы вытекает справедливость утверждения после выполнения)? Предполагается, что значение переменной n неотрицательно. double r, x; int n; . . . r *= x*x; r /= ((n+1)*(n+2)); n += 2;