Задача 25

В этой задаче нужно написать алгоритм, обрабатывающий целочисленный массив. Обработка в общем случае сводится к следующему:

  1. найти все элементы, удовлетворяющие некоторому предикату P
  2. посчитать композицию найденных элементов в рамках некоторой полугруппы
  3. напечатать результат
  4. либо найти все элементы, удовлетворяющие предикату Q
  5. преобразовать их некоторой унарной операцией, построенной по результату
  6. напечатать преобразованный массив

Задача осложняется наличием ограничения свободы самовыражения — требуется написать алгоритм, использующий стандартные императивные конструкции и очень ограниченный набор переменных.

Вариативность предикатов

Определённую сложность представляет выражение предикатов P и Q на языке программирования. Поэтому сейчас мы разберём самые частовстречающиеся предикаты и их выражения на языке C++.

Договоримся, что массив называется a, а индекс того элемента, на который мы сейчас смотрим (в цикле) — i.

Делимость на что-нибудь

Бывает двух видов: делимость элемента и делимость его номера. Их не нужно путать. Найти чётные элементы:

a[i] % 2 == 0

Найти элементы на чётных местах:

i % 2 == 0

Неделимость на что-нибудь

Здесь нужно быть аккуратным из-за специфического поведения оператора взятия остатка в большинстве языков программирования. Например, на C++ нельзя нечётность проверять конструкцией вида

a[i] % 2 == 1

Она будет работать только для неотрицательных a[i]! Правильно же выражать высказывание «элемент имеет остаток r при делении на d» конструкцией вида

(a[i] - r) % d == 0

Цифры в записи числа

Например, задание вида «найти все числа, у которых совпадает последняя цифра в десятичной и шестнадцатиричной записи». Задание не представляет сложности, если помнить определение d-ичной системы счисления.

Напомним, что система счисления с основанием d состоит из:

  • множества \(D\) цифр
  • биекции \(v:D\to\mathbb{N}[0,d)\) между цифрами и натуральными числами от нуля включительно до \(d\) исключительно (эта биекция называется числовым значением цифр)
  • отображения \(r:[D]\to\mathbb{N}\) из множества конечных последовательностей цифр в множество натуральных чисел
  • отображения \(w:\mathbb{N}\to[D]\)

При этом должно выполняться следующее: во-первых

\[ r(x) = \sum_i v(x_i) d^i \]

Во-вторых, \(r(w(n)) = n\).

Из этого определения, например, сразу следует, что \(w(n)_0=n\bmod d\). Это как раз и есть числовое значение «последней цифры числа \(n\)». Поэтому задание «найти все числа, у которых совпадает последняя цифра в десятичной и шестнадцатиричной записи» можно решить условием вида

a[i] % 10 == a[i] % 16

Количество цифр в записи числа

Например, требуется найти все числа, которые записываются тремя цифрами в шестнадцатиричной системе счисления. Лучше всего подобные условия выражать банальными неравенствами вида:

16*16 <= a[i] and a[i] < 16*16*16

Сумма цифр в записи числа

Встречается очень редко, но встречается. Требует две дополнительных переменных и вложенный цикл:

s = 0;
k = a[i];
while (k > 0) {
    s += k % 10;  // пример для 10-чной системы счисления
    k  = k / 10;
}
// теперь в переменной s находится сумма десятичных цифр числа a[i]

Взаимоотношения с соседями

Например, нужно найти все элементы, большие обоих своих соседей. Единственная тонкость такого задания — границы цикла: вместо стандартного 

for (i = 0; i < N; i++) {
    // нечто
}

нужно писать

for (i = 1; i < N-1; i++) {
    if (a[i] > a[i-1] and a[i] > a[i+1]) {  
        // что-то
    }
}

Вариативность полугруппы

Если Вы вдруг забыли, что такое полугруппа, и ещё не подсмотрели нигде до этого момента, напомним, что полугруппой с носителем \(X\) называется бинарная ассоциативная операция на множестве \(X\). А именно, отображение \(f:X\times X\to X\), для которого выполнено

\[ f(x,f(y,z)) = f(f(x,y),z) \]

или, в инфиксной записи,

\[ x f (y f z) = (x f y) f z \]

В качестве полугруппы в 25-й задаче почти всегда фигурирует одно из трёх: минимум, максимум, сумма. Причём иногда дополнительно задаётся отображение из множества целых чисел в носитель полугруппы (в дальнейшем будем его называть препроцессором).

Например, в задании «найти количество чётных элементов массива» полугруппой является сумма целых чисел, а препроцессором — отображение из множества целых чисел в себя, отображающее все целые числа в единицу.

Следует очень внимательно следить за двумя вещами:

  1. часто в случае, если в массиве нет элементов, удовлетворяющих предикату P, требуется сделать нечто; это самое нечто никаких сложностей не представляет, но про него нужно не забыть
  2. при поиске минимума/максимума требуется либо бинарный флаг вида «ещё не встретили ни одного хорошего числа», либо удобное начальное значение

Например, если требуется найти минимальное чётное число в массиве, следует прибегнуть к конструкции вида

encountered_good = false;
for (i = 0; i < N; i++) {
    if (a[i] % 2 == 0) {
        m = not encountered_good ? a[i] : min(m,a[i]);
        encountered_good = true;
    }
}

if (not encountered_good) {
    // сделать то самое нечто
    return 0;
}

с поправкой на ограничение по использованию переменных. Но в реальности в задании всегда указано ограничение сверху на величину чисел в массиве (например, 10000), а вот лишняя переменная под флаг недоступна. В таком случае работает конструкция вида

m = 10001; // значение на 1 больше максимально возможного значения
for (i = 0; i < N; i++) {
    if (a[i] % 2 == 0) { m = min(m,a[i]); }
}

if (m > 10000) {
    // сделать то самое нечто
    return 0;
}

Примерный вид программы

Рассмотрим, например такое задание:

  1. найти максимальное число в массиве целых положительных чисел, в семиричной записи которого две или три цифры
  2. уменьшить все чётные элементы массива на найденное число или на 1, если чисел указанного вида не было
  3. напечатать получившийся массив

В программе дана константа N (длина массива), массив a и целочисленные переменные i и m (обычно дают на всякий случай ещё одну переменную, но не нужно на это рассчитывать).

m = 0;
for (i = 0; i < N; i++) {
    if (7 <= a[i] and a[i] < 7*7*7) {
        m = max(m,a[i]);
    }
}

if (m == 0) { m = 1; }

for (i = 0; i < N; i++) {
    if (a[i] % 2 == 0) { a[i] -= m; }
}

for (i = 0; i < N; i++) {
    cout << a[i] << endl;  // не забываем про отступы между числами
    // Плюс не забываем уточнить, чем _именно_ нужно разделять элементы
    // массива при печати.
}