Общее оглавление

Цели и критерии

Цели: наработка навыков определения линейных алгоритмов, оперирующих последовательностями.

Критерии полноты

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

1. Написать функцию, вычисляющую требуемый результат, обрабатывая как последовательность произвольный массив (функция должна принимать адрес и размер массива, либо диапазон, заданный парой указателей).
2. Написать функцию, выполняющую тестирование функции из п.1 на не менее чем трёх массивах (если в задании не сказано иначе), заданных непосредственно в этой функции (т.е. предполагаемый результат работы можно посчитать “вручную” заранее).
3. Написать функцию, вычисляющую требуемый результат, читая последовательность произвольной длины (и не сохраняя её в память) с потока ввода до первой ошибки или конца ввода.
4. Написать функцию, выполняющую тестирование функции из п.3 на не менее чем трёх последовательностях (если в задании не сказано иначе), заданных непосредственно в этой функции (т.е. предполагаемый результат работы можно посчитать “вручную” заранее).
5. Написать программу, прогоняющую все тесты и выводяющую отчёт.

Замечание. Тесты из п.2 и п.4 могут использовать одинаковые входные данные (и, соответственно, ожидать одинаковые результаты), различаясь только промежуточным представлением данных (массив и поток). Поэтому разумно разделить “данные” для теста и способ его выполнения (см. примеры).

Примеры

В примерах используются указатели на функции.

Максимальная подпоследовательность дубликатов

Задача. Пусть требуется определить длину максимальной подпоследовательности (непрерывного участка исходной последовательности), состоящей из идущих подряд равных элементов (дубликатов).

Пример: { 1, 2, 3, 3, 0, 0, 0, 1, 2 } → 3 (три нуля подряд).

Решение

В каждый момент помимо значения текущего элемента нам также надо знать значение предыдущего элемента, чтобы можно было определить, кончилась ли подпоследовательность дубликатов, или же она всё ещё продолжается. Соответственно, мы или увеличиваем значение переменной cur_run, содержащей длину текущей подпоследовательности дубликатов, или сбрасываем её в 1, поправляя значение переменной max_run, содержащей максимальную из длин подпоследовательностей дубликатов, обнаруженных к данному моменту.

// П.1: обработка произвольного массива, переданного как адрес + размер
size_t max_duprun(const double a[], size_t n)
{
  if (n == 0)
    return 0;

  // По крайней мере, один элемент в массиве есть.
  size_t max_run = 1; // максимальная длина на данный момент
  size_t cur_run = 1; // текущая длина
  for (size_t i = 1; i < n; ++i)
  {
    if (a[i] != a[i - 1]) // соседние элементы не равны
      cur_run = 1;
    else // продолжается подпоследовательность равных
      ++cur_run;

    max_run = max(max_run, cur_run);
  }

  return max_run;
}

// П.3: считывание чисел с потока ввода.
size_t max_duprun(istream &in)
{
  size_t max_run = 0; // максимальная длина на данный момент
  double x, prev_x; // последнее и предпоследнее прочитанные числа
  if (in >> prev_x)
  {
    // Последовательность содержит не менее одного элемента.
    size_t cur_run = 1; // текущая длина
    max_run = 1; // по крайней мере, есть один элемент

    while (in >> x)
    {
      if (x != prev_x) // соседние элементы не равны
      {
        cur_run = 1;
        prev_x = x;
      }
      else // продолжается подпоследовательность равных
      {
        ++cur_run;
      }

      max_run = max(max_run, cur_run);
    }
  }

  return max_run;
}

Чтобы не дублировать тест для этих двух вариантов одного алгоритма, выполним тест в виде одной функции, которая вызывает обёртку тестируемой функции для заранее заданного массива и результата. Обёртка возвращает истину, если результат совпал.

Обёртки имеют следующий вид:

// П.2: тестирование функции из п.1 на заданном массиве с заданным результатом.
bool test_max_duprun_array(const double a[], size_t n, size_t result)
{
  return result == max_duprun(a, n);
}

// П.4: тестирование функции из п.3 на заданном массиве с заданным результатом.
bool test_max_duprun_stream(const double a[], size_t n, size_t result)
{
  stringstream test;
  for (size_t i = 0; i < n; ++i)
    test << a[i] << ' ';

  return result == max_duprun(test);
}

Тип указателя на функцию-обёртку:

using Max_duprun_tester = bool (*)(const double a[], size_t n, size_t result);

Наконец, сама тестирующая функция:

// П.2 и п.4: тестирование функции из п.1 или п.3 (выбирается через tester).
int test_max_duprun(Max_duprun_tester tester)
{
  const double test1[] = { 1, 1, 2, 2, 2, 2, 0, 4, 2, 2 };
  if (!tester(test1, 0, 0)) return 1;
  if (!tester(test1, 1, 1)) return 2;
  if (!tester(test1, 2, 2)) return 3;
  if (!tester(test1, 5, 3)) return 4;
  
  // sizeof возвращает размер статического массива в байтах
  // (!) при этом массив должен быть виден в данном контексте непосредственно,
  // (!) иначе программист рискует получить вместо размера массива размер указателя на него
  if (!tester(test1, sizeof(test1) / sizeof(double), 4))
      return 5;

  const double test2[] = { -4, -3, -2, -1 };
  if (!tester(test2, sizeof(test2) / sizeof(double), 1))
    return 6;

  const double test3[] = { 1, 2, 3, 3, 0, 0, 0, 1, 2 };
  if (!tester(test3, sizeof(test3) / sizeof(double), 3))
    return 7;

  // Все тесты пройдены успешно.
  return 0;
}

C++, HTML

Частоты цифр

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

Решение

Для определения принадлежности символа цифрам воспользуемся стандартной функцией isdigit (из стандартного заголовочного файла cctype), для определения принадлежности символа графическим символам воспользуемся стандартной функцией isgraph.

Вспомогательные определения: BYTES — количество разных “байт” (как правило, 256); Counter — тип счётчика для символа, символ может повториться в потоке не более раз, чем максимальный возможный размер потока (файла), поэтому в качестве типа счётчика взят тип, используемый для смещений в потоке; Histogram (гистограмма) — массив счётчиков.

// Количество разных байт. Байт и char -- синонимы в C и C++.
const size_t BYTES = 1u << CHAR_BIT;

// Целочисленный тип для представления счётчиков.
// Тип streamoff -- целочисленный тип, достаточный для того, чтобы описать смещение в потоке
// или размер любого файла в данной системе, т.е. "достаточно большое целое".
using Counter = streamoff;

// Тип "гистограмма" -- массив счётчиков.
using Histogram = Counter[BYTES];

После того, как построена гистограмма, из неё можно извлечь всю необходимую информацию о частотах определённых символов (например, цифр), в том числе, об относительных частотах. Накопление гистограммы на основе данных в потоке или массиве, по сути, идентичные операции — надо для каждого символа увеличить на единицу счётчик по индексу, равному коду этого символа:

// Строит гистограмму байт потока. Добавляет количества к счётчикам h.
// Возвращает общее количество.
Counter byte_histogram(istream &in, Histogram h)
{
  Counter bytes_read = 0;
  // Читать по символу из потока, увеличивая на каждой итерации соответствующий счётчик в h.
  for (char ch; in.get(ch); ++bytes_read)
    h[(unsigned char)ch]++; /* Приведение к unsigned char необходимо так как
    по стандарту char может быть "знаковым" и "верхняя половина" диапазона
    в таком случае попадает в отрицательные индексы, что (при прямом использовании char)
    повлекло бы выход за пределы массива h. */
  return bytes_read;
}

// Строит гистограмму массива. Добавляет количества к счётчикам h.
// Возвращает переданный размер.
size_t byte_histogram(const char a[], size_t sz, Histogram h)
{
  for (size_t i = 0; i < sz; ++i)
    h[(unsigned char)(a[i])]++; /* Приведение к unsigned char необходимо так как
    по стандарту char может быть "знаковым" и "верхняя половина" диапазона
    в таком случае попадает в отрицательные индексы, что (при прямом использовании char)
    повлекло бы выход за пределы массива h. */
  return sz;
}

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

// Тип: указатель на функцию, принимающую и возвращающую целое число.
using Char_predicate = int (*)(int);

// Возвращает сумму элементов гистограммы, для индексов которых предикат filter возвращает истину.
Counter histogram_filter_sum(const Histogram h, Char_predicate filter)
{
  Counter s = 0;
  for (size_t i = 0; i < BYTES; ++i)
    s += filter((int)i)? h[i]: 0; /* i приводится к int, 
    т.к. стандартные функции --- символьные предикаты принимают int, а не size_t */
  return s;
}

Наконец, напишем функцию, вычисляющую относительные частоты цифр. Данная функция будет принимать общее количество total символов некоторого класса, относительного которого вычисляются частоты, т.е. попросту принимает делитель количеств, который посчитан как-то вовне этой функции — на самом деле, либо с помощью histogram_filter_sum, либо total просто равен количеству всех символов (сумме гистограммы, возвращаемой функцией byte_histogram), если это абсолютные частоты.

// Для заданной гистограммы и заданного общего количества символов total получить частоты цифр.
// Возвращает суммарную частоту.
// Данную функцию удобно использовать для тестирования.
double digits_freqs(const Histogram h, Counter total, double freqs[10])
{
  Counter h_digit_sum = 0;
  const auto divisor = double(total);
  for (int digit = 0; digit < 10; ++digit)
  {
    const auto h_digit = h[dec_digit(digit)];
    h_digit_sum += h_digit;
    freqs[digit] = h_digit / divisor;
  }

  return h_digit_sum / divisor;
}

Вспомогательная функция dec_digit выполняет преобразование номер десятичной цифры → символ цифры. Её можно реализовать по-разному. Например, если мы хотим максимально возможной переносимости кода, то можно написать так (unsigned char используется потому, что результат данной функции подставляется в качестве индекса массива):

inline unsigned char dec_digit(int n)
{
  assert(0 <= n && n < 10);
  return "0123456789"[n]; // или n["0123456789"];
}

Однако, автору не известны кодировки символов, в которых коды десятичных цифр идут не подряд. Поэтому, можно считать вполне переносимым более простой и вычислительно эффективный “арифметический” вариант:

inline unsigned char dec_digit(int n)
{
  assert(0 <= n && n < 10);
  return '0' + n;
}

C++, HTML

Варианты

1

Вычислить разность между максимумом элементов последовательности, стоящих на нечётных позициях (если считать с единицы), и минимумом элементов, стоящих на чётных позициях.

Пример: { 5, 1, 6, 10, 3, –1, 4, 2 } → max { 5, 6, 3, 4 } – min { 1, 10, –1, 2 } → 6 – (–1) → 7.

2

Определить количество смен знаков элементов последовательности.

Пример: { 1, 2, –1, –2, 0, 0, –2, –1, 0, 0, 5, 0 } → 2 (ноль не даёт смены знака).

3

Определить количество смен направления роста последовательности.

Пример: { 1, 1, 1, 2, 2, 3, 4, 1, 0, 1 } → { –, –, –, ↗, –, ↗, ↗, ↘, ↘, ↗ } → { ↗, ↘, ↗ } → 2.

4

Определить, к какому из нижеперечисленных классов принадлежит последовательность. Написать тесты для последовательностей всех классов.

• Класс –1: монотонно (нестрого) убывающая.
• Класс 0: состоящая из одинаковых элементов или пустая.
• Класс +1: монотонно (нестрого) возрастающая.
• Класс 2: содержащая как возрастающие, так и убывающие подпоследовательности (в этот класс попадают все последовательности, которые не попали в предыдущие три класса).

Пример: { 1, 2, 3, 3, 3, 4, 5 } → +1; { 4, 4, 4, 3, 1, 0 } → –1; { 4, 0, 4, 4, 4, 4 } → 2.

5

Вычислить максимум гармонических средних участков последовательности, разделённых нулями.

Формула для вычисления среднего гармонического для последовательности a₁, a₂, …, a_n имеет вид n / (1/a₁ + 1/a₂ + … + 1/a_n).

Пример: { 1, 2, 3, 0, 4, 5, 6, 0, 1, 2, 10, 16, 0, 0, 0, 2 } → участки разделённые нулями: { 1, 2, 3 }, { 4, 5, 6 }, { 1, 2, 10, 16 }, { 2 } → гармонические средние: 1.(63), 4.(864), 2.406015, 2 → максимум из них равен 4.(864).

6

Определить число участков, заполненных нулями.

Пример: { 0, 1, 2, 3, 0, 0, 0, 0, 4, 1, 2, 0 } → 3 (один нуль в начале, четыре нуля “по середине” и один нуль в конце).

7

Определить длину самого длинного строго монотонного участка.

Пример: { 1, 2, 3, –3, –4, –5, 10, 0 } → 4 (участок 3, –3, –4, –5).

8

Определить частоты всех возможных значений отдельных байт и сочетаний пар соседних байт в последовательности байт. Выводить только те байты и пары байт, что имеют ненулевые частоты.

9

Определить частоты всех сочетаний трёх строго соседних букв (определять принадлежность символа к множеству “буквы” с помощью стандартной функции isalpha) в последовательности символов. Выводить только те сочетания букв, что имеют ненулевые частоты.

10

Пусть дана последовательность натуральных чисел a_i и натуральное число K. Будем называть a_i K-последовательностью, если для всех a_i и a_i+1 выполнено

a_i + 1 = a_i+1 (mod K)

Задача: в заданной последовательности найти длину наибольшей подпоследовательности, являющейся K-последовательностью (K — параметр функции).

Пример: K = 3, { 1, 2, 6, 4, 8, 7, 6, 10, 2, 3, 1, 20, 3, 22 }, если взять остаток от деления на K, получим { 1, 2, 0, 1, 2, 1, 0, 1, 2, 0, 1, 2, 0, 1 }. Здесь видим K-последовательности: 1, 2, 0, 1, 2 (длина 5); 0, 1, 2, 0, 1, 2, 0, 1 (длина 8). Ответ: 8.

11

Пусть задана константа времени компиляции CHUNK_SIZE > 0. Для заданной последовательности вычислить максимум сумм всех групп соседних элементов размера CHUNK_SIZE. Вернуть сумму элементов исходной последовательности, если её длина меньше или равна CHUNK_SIZE.

Пример. Пусть CHUNK_SIZE = 4, дана последовательность { 1, –1, 2, 3, –3, 5, 6, 7, –5 }, имеем группы (1, –1, 2, 3) → 5, (–1, 2, 3, –3) → 1, (2, 3, –3, 5) → 7, (3, –3, 5, 6) → 11, (–3, 5, 6, 7) → 15, (5, 6, 7, –5) → 13, откуда получаем, что максимум сумм = 15.

12

Пусть задана константа времени компиляции WINDOW_SIZE > 0. Для заданной последовательности вычислить максимум разностей максимума и минимума элементов всех групп соседних элементов размера WINDOW_SIZE. Вернуть разность максимума и минимума элементов исходной последовательности, если её длина меньше или равна WINDOW_SIZE.

Пример. Пусть WINDOW_SIZE = 4, дана последовательность { 1, –1, 2, 3, –3, 5, 6, 7, –5 }, имеем группы (1, –1, 2, 3) → 4, (–1, 2, 3, –3) → 6, (2, 3, –3, 5) → 8, (3, –3, 5, 6) → 9, (–3, 5, 6, 7) → 10, (5, 6, 7, –5) → 12, откуда получаем, что максимум равен 12.

13

Для заданной последовательности вычислить арифметическое среднее медиан подряд идущих троек элементов. Для неполных троек брать арифметическое среднее.

Пример. Дана последовательность { 1, 5, 1, 4, 5, 6, 2, 1, 3, 4, 4, 4, 5, 7 }. Разбиваем на тройки: { 1, 5, 1 }, { 4, 5, 6 }, { 2, 1, 3 }, { 4, 4, 4 }, { 5, 7 }, последняя “тройка” неполная — два элемента. Получаем набор медиан (последнее значение — арифметическое среднее последних двух элементов): 1, 5, 2, 4, 6. Арифметическое среднее этих значений равно 3.6.

14

Реализовать дельта-кодирование и кодирование длин последовательностей (определения даны ниже). Закодировать и раскодировать произвольную строку (дельта-кодирование → кодирование длин последовательностей нулей → декодирование длин последовательностей нулей → дельта-декодирование). Можно реализовать либо только работу с массивами символов (строками) либо только работу с потоками ввода-вывода.

Тестирование: исходная и декодированная строки должны совпадать, кодированная строка не должна совпадать с исходной, последовательность из n повторяющихся символов превращается в один символ, затем нуль и значение (n–1).

Дополнительный критерий полноты: функция main должна принимать произвольное число строк и для каждой введённой строки выводить результат кодирования и декодирования.

Дельта-кодирование нередко используется как составной элемент алгоритмов сжатия данных (как с потерями, так и без потерь). Например, последовательность повторяющихся значений представляется последовательностью нулей, амплитуда слабо изменяющегося сигнала значительно понижается.

Собственно RLE в чистом виде обычно не так полезно (размер представления, скорее, вырастает, а не снижается). Однако при комбинировании дельта-кодирования и RLE можно сделать важную поправку: указывать число повторений только для нулей. Т.е. если при кодировании на вход пришёл не нуль, пропускаем его “как есть”, а если нуль, то записываем нуль и дальше считаем входящие нули и при поступлении не нуля или завершении входного потока или достижении счётчиком нулей максимального допустимого значения записываем значение счётчика.

Общее оглавление

Кувшинов Д.Р. © 2015