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

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

Цели: закрепление навыков алгоритмизации и программирования.

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

1. Реализована отдельная функция (или набор функций), решающая поставленную задачу. Допускается использовать любые компоненты Стандартной библиотеки.
2. В виде отдельной функции (не в main) реализованы тесты, выполняющие автоматическое тестирование функций из п.1.

Примеры

Наиболее длинная подстрока-палиндром

Задача

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

Пример: “abcdcba” — палиндром длины 7.

Для простоты будем считать палиндромом строку, которую не изменяет обращение порядка байт. Т.е. будем просто сравнивать байты на равенство: кодировки, пробелы, знаки препинания, большие и маленькие буквы — влияют на результат.

Решение: квадратичный алгоритм

1. Не составит особого труда проверить, является ли определённый символ в строке центром подстроки-палиндрома.
   • Если ищем палиндром нечётной длины, то сравниваем подряд символы строки по обе стороны от символа до тех пор, пока не упрёмся в границы строки или не найдём пару несовпадающих символов. Таким образом, получим “размах” наиболее длинной подстроки-палиндрома нечётной длины с центром в выбранном символе.
   • Если ищем палиндром чётной длины, то убедимся, что символ, следующий за заданным, существует (т.е. мы не выходим за пределы строки) и равен заданному, далее проверяем совпадение символов по обе стороны от центральной пары аналогично предыдущему случаю.
2. Для каждого символа строки (первый и последний можно не рассматривать) выполним поиск наиболее длинного палиндрома с центром в данном символе, выбрав из наиболее длинных палиндромов нечётной и чётной длин. При прохождении символов строки будем запоминать текущий максимум длины и позицию начала самого длинного палиндрома, обнаруженного к данному моменту.

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

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

/// Определить максимальную длину совпадающих суффикса массива [begin, left)
/// и префикса массива [right, end)
std::size_t max_common_prefix_suffix
  (
    const char *begin, const char *left,
    const char *right, const char *end
  )
{
  std::size_t steps = 0;
  while (begin != left && right != end && *--left == *right++)
    ++steps;
  return steps;
}

Случаи нечётной и чётной длин.

/// Определить радиус палиндрома нечётной длины с центром center.
inline std::size_t longest_odd_palindrome_radius_from
  (
    const char *begin, const char *end,
    const char *center
  )
{
  assert(begin <= center && center < end);
  return max_common_prefix_suffix(begin, center, center + 1, end);
}

/// Определить радиус палиндрома чётной длины с центром (левым символом пары) в center.
inline std::size_t longest_even_palindrome_radius_from
  (
    const char *begin, const char *end,
    const char *center
  )
{
  assert(begin <= center && center + 1 < end);
  return max_common_prefix_suffix(begin, center, center + 2, end);
}

Наконец, собственно перебор позиций предполагаемых центров палиндромов в исходной строке.

/// Найти самую длинную подстроку-палиндром в диапазоне строки.
/// Возвращает длину найденной подстроки.
/// По указателю found записывает указатель на начало найденной подстроки.
std::size_t longest_palindrome(const char *begin, const char *end, const char **found)
{
  std::size_t cur_max = 0;
  for (auto pos = begin + 1; pos + 1 < end; ++pos)
  {
    const auto odd_len = 2 * longest_odd_palindrome_radius_from(begin, end, pos) + 1;
    if (cur_max < odd_len)
    {
      cur_max = odd_len;
      *found = pos - odd_len / 2;
    }

    if (*pos == *(pos + 1))
    {
      const auto even_len = 2 * longest_even_palindrome_radius_from(begin, end, pos) + 2;
      if (cur_max < even_len)
      {
        cur_max = even_len;
        *found = (pos + 1) - even_len / 2;
      }
    }
  }

  return cur_max > 1 ? cur_max : 0;
}

Тестирование полученного решения будем выполнять с помощью заранее подготовленных строк с известными решениями. Для удобства определим функцию-обёртку, возвращающую для заданной строки подстроку-палиндром наибольшей длины в виде объекта std::string, для которого определены удобные в использовании операции сравнения.

/// В заданном объекте std::string найти самую длинную подстроку-палиндром
/// и вернуть её в виде нового объекта std::string.
string longest_palindrome(const string &text)
{
  const char *pos = nullptr;
  const auto len = longest_palindrome(text.data(), text.data() + text.size(), &pos);
  return string(pos, pos + len);
}

Собственно функция-тест выглядит следующим образом:

int test_longest_palindrome()
{
  if (longest_palindrome("this isn't a text with no palindromic substrings") != "t a t")
    return 1;
  if (longest_palindrome("there is no word redivider in English") != " redivider ")
    return 2;
  if (longest_palindrome("who knows what \"detartrated\" means?") != " \"detartrated\" ")
    return 3;
  if (longest_palindrome("saippuakalasalakauppias is longer than"
                         "saippuakivikauppias but what about"
                         "kuulilennuteetunneliluuk?") != "kuulilennuteetunneliluuk")
    return 4;
  if (longest_palindrome("blast") != "")
    return 5;
  return 0;
}

C++, HTML

Выпуклая оболочка множества точек на плоскости

Задача

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

Этот пример несколько сложнее (в первую очередь, объёмнее) вариантов заданий для данной самостоятельной работы.

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

Выпуклая оболочка convex hull множества M — наименьшее по включению выпуклое множество, содержащее M.

Если M — выпуклое множество, то его выпуклая оболочка совпадает с ним самим.

Многоугольник polygon — замкнутая ломаная с конечным количеством вершин.

Простой многоугольник — многоугольник без самопересечений.

Простой многоугольник разбивает плоскость на две области: внутреннюю и внешнюю. Обычно, когда говорят о “многоугольнике” имеют в виду внутреннюю область простого многоугольника, взятую вместе с границей (самой ломаной, задающей многоугольник).

Выпуклый многоугольник — простой многоугольник, внутренняя область которого — выпуклое множество.

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

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

Строго выпуклый многоугольник — выпуклый многоугольник, не содержащий развёрнутых углов при вершинах.

Далее для краткости под “выпуклой оболочкой” (конечного множества точек) будем понимать упорядоченный против часовой стрелки набор её вершин (т.е. выпуклый многоугольник).

Решение

Предлагаемый алгоритм “заворачивания подарка” (также известный как алгоритм Джарвиса) является весьма простым способом построения выпуклой оболочки конечного множества точек. Его можно определить для евклидова пространства произвольной размерности, но мы ограничимся случаем плоскости.

Словесно алгоритм можно описать следующим образом.

1. Из всех точек исходного множества найти точку с максимальным значением координаты x (если их несколько, то взять из них ту, что имеет максимальное значение координаты y). Эта точка является вершиной выпуклой оболочки.
2. У нас уже есть, по крайней мере, одна вершина v выпуклой оболочки. Чтобы найти следующую вершину, из всех точек исходного множества (из них можно сразу исключить те точки, что уже идентифицированы как вершины выпуклой оболочки, а можно и не исключать) выбрать точку, для которой отрезок, соединяющий её с v даёт наибольший поворот по часовой стрелке (наименьший угол со знаком относительно оси абсцисс). Если таких точек много, то взять из них наиболее удалённую от v.
3. Повторять п.2 до тех пор, пока в качестве следующей вершины не будет выбрана та, что была найдена в п.1.

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

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

1. Каждая точка результата не содержится строго внутри контура из прочих точек.
2. Все исходные точки находятся внутри оболочки.
3. Все точки оболочки принадлежат исходному набору точек.

Метод тестирования: создавать случайный набор точек и проверять результирующую выпуклую оболочку.

Указанные три проверки можно несколько упростить. Проверка 3 не нужна, так как несложно показать, что функция, строящая выпуклую оболочку не порождает новых точек, а берёт в качестве вершин результата только точки из исходного набора. Проверку 1 можно заменить проверкой направления поворота при обходе вершин выпуклой оболочки против часовой стрелки: поворот всегда должен происходить строго налево (против ЧС). Проверка №2 является относительно сложной, но мы её реализуем.

ageo2d.hpp

Итак, вначале определим вспомогательные типы: точка на плоскости и двумерный вектор. Простейший набор геометрических определений вынесен в заголовочный файл ageo2d.hpp (при копировании файла префикс названия 0900- надо убрать, HTML-версия).

Например, вектор:

/// Двумерный вектор.
struct Vector_2
{
  double x, y;
  /// Конструктор по умолчанию -- нулевой вектор.
  Vector_2()
    : x(0.), y(0.) {}
  /// Создать вектор с заданными координатами.
  Vector_2(double x, double y)
    : x(x), y(y) {}

  /// Добавить другой вектор "на месте".
  Vector_2& operator+=(const Vector_2 &other)
  {
    x += other.x;
    y += other.y;
    return *this;
  }

  /// Вычесть другой вектор "на месте".
  Vector_2& operator-=(const Vector_2 &other)
  {
    x -= other.x;
    y -= other.y;
    return *this;
  }

  /// Домножить на скаляр "на месте".
  Vector_2& operator*=(double factor)
  {
    x *= factor;
    y *= factor;
    return *this;
  }
};

Можно заметить два конструктора: конструктор “по умолчанию” создаёт нулевой вектор, конструктор из двух чисел использует эти числа как значения координат нового вектора. Далее определены операторы +=, -= и *=, которые действуют в соответствии с определением операций суммы и разности векторов и произведения вектора на число. Естественно, требуется как минимум определить аналоги этих операций без присваивания:

// Сумма векторов: операция "+".
inline Vector_2 operator+(const Vector_2 &a, const Vector_2 &b)
{
  return Vector_2(a.x + b.x, a.y + b.y);
}

/// Разность векторов: операция "-".
inline Vector_2 operator-(const Vector_2 &a, const Vector_2 &b)
{
  return Vector_2(a.x - b.x, a.y - b.y);
}

/// Унарный минус.
inline Vector_2 operator-(const Vector_2 &a)
{
  return Vector_2(-a.x, -a.y);
}

/// Умножение вектора на скаляр слева: операция "*".
inline Vector_2 operator*(double factor, const Vector_2 &vec)
{
  return Vector_2(factor * vec.x, factor * vec.y);
}

/// Умножение вектора на скаляр справа: операция "*".
inline Vector_2 operator*(const Vector_2 &vec, double factor)
{
  return factor * vec; // то же, что и слева
}

Так как “по умолчанию” умножение (да и другие операции) в C++ не является коммутативным, надо определить два варианта: когда число слева от вектора и когда число справа от вектора.

Кроме арифметических операций необходимы сравнения, хотя бы на равенство и неравенство:

/// Проверка пары векторов на равенство.
inline bool operator==(const Vector_2 &a, const Vector_2 &b)
{
  return a.x == b.x && a.y == b.y;
}

/// Проверка пары векторов на неравенство.
inline bool operator!=(const Vector_2 &a, const Vector_2 &b)
{
  return !(a == b);
}

Наконец, далее нам понадобятся скалярное и псевдоскалярное произведения векторов.

/// Скалярное произведение векторов.
inline double dotp(const Vector_2 &a, const Vector_2 &b)
{
  return a.x * b.x + a.y * b.y;
}

/// Псевдоскалярное произведение векторов.
/// Равно произведению длин векторов на синус угла между ними.
inline double crossp(const Vector_2 &a, const Vector_2 &b)
{
  return a.x * b.y - a.y * b.x;
}

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

/// Точка на плоскости.
struct Point_2
{
  double x, y;
  /// Конструктор по умолчанию -- начало координат.
  Point_2()
    : x(0.), y(0.) {}
  /// Создать точку с заданными координатами.
  Point_2(double x, double y)
    : x(x), y(y) {}

  /// Радиус-вектор точки.
  Vector_2 radius() const
  {
    return Vector_2(x, y);
  }

  /// Сместить эту точку на заданный вектор.
  Point_2& operator+=(const Vector_2 &delta)
  {
    x += delta.x;
    y += delta.y;
    return *this;
  }

  /// Сместить эту точку на -delta.
  Point_2& operator-=(const Vector_2 &delta)
  {
    x -= delta.x;
    y -= delta.y;
    return *this;
  }
};

/// Проверка пары точек на равенство.
inline bool operator==(const Point_2 &a, const Point_2 &b)
{
  return a.x == b.x && a.y == b.y;
}

/// Проверка пары точек на неравенство.
inline bool operator!=(const Point_2 &a, const Point_2 &b)
{
  return !(a == b);
}

/// Разность двух точек даёт вектор.
inline Vector_2 operator-(const Point_2 &a, const Point_2 &b)
{
  return Vector_2(a.x - b.x, a.y - b.y);
}

/// К точке можно добавить вектор, чтобы получить смещённую точку.
inline Point_2 operator+(const Point_2 &a, const Vector_2 &delta)
{
  return Point_2(a.x + delta.x, a.y + delta.y);
}

/// К точке можно добавить вектор, чтобы получить смещённую точку.
inline Point_2 operator+(const Vector_2 &delta, const Point_2 &a)
{
  return a + delta;
}

/// Из точки можно вычесть вектор, чтобы получить смещённую точку.
inline Point_2 operator-(const Point_2 &a, const Vector_2 &delta)
{
  return Point_2(a.x - delta.x, a.y - delta.y);
}

C++, HTML

jarvis.cpp

Теперь оформим в виде C++-кода сам алгоритм заворачивания подарка и напишем тесты.

Пункт 1: поиск первой вершины выпуклой оболочки:

/// В диапазоне точек найти самую верхнюю из самых правых.
Point_2* find_highest_rightmost(Point_2 *begin, Point_2 *end)
{
  assert(begin < end);
  double x_max = begin->x, y_max = begin->y;
  auto cur_max = begin;
  while (++begin != end)
  {
    if (x_max < begin->x
     || begin->x == x_max && y_max < begin->y)
    {
      x_max = begin->x;
      y_max = begin->y;
      cur_max = begin;
    }
  }

  return cur_max;
}

Пункт 2: поиск следующей вершины выпуклой оболочки:

/// В диапазоне точек найти самый дальний поворот по часовой стрелке от точки v.
Point_2* max_cw_turn(Point_2 *begin, Point_2 *end, Point_2 v)
{
  assert(begin < end);
  auto cur_max = begin;
  auto vector = *begin - v; // воспользуемся оператором минус, определённым для точек выше
  while (++begin != end)
  {
    const auto new_vector = *begin - v;
    const auto cp = crossp(vector, new_vector);
    if (cp < 0.   // поворот от vector к new_vector по ЧС?
     || cp == 0.  // коллинеарны, но сонаправленны и new_vector длиннее, чем vector?
     && dotp(vector, vector) < dotp(vector, new_vector))
    {
      cur_max = begin;
      vector = new_vector;
    }
  }

  return cur_max;
}

Две вышеприведённые функции могли бы принимать и возвращать const Point_2*, но автором было принято решение строить выпуклую оболочку, не копируя её вершины в дополнительный массив, а просто переставляя точки в исходном массиве так, чтобы вершины выпуклой оболочки шли в правильном порядке в начале исходного массива, а прочие точки располагались за ними. Чтобы не выполнять явное преобразование типов с отбрасыванием константности, данные вспомогательные определения используют указатели без const.

Итак, сам алгоритм реализован в виде следующей функции:

/// Алгоритм заворачивания подарка.
/// Переставляет элементы исходного диапазона точек так,
/// чтобы вершины выпуклой оболочки в порядке обхода против часовой стрелки
/// встали в начале диапазона, возвращает указатель на следующую за последней
/// вершиной построенной выпуклой оболочки вершину.
Point_2* convex_hull_jarvis(Point_2 *begin, Point_2 *end)
{
  using std::swap;
  if (begin == end)
    return end;

  // Найти позицию самой верхней из самых правых точек.
  // Это -- последняя вершина выпуклой оболочки.
  auto cur = find_highest_rightmost(begin, end);
  // Потенциальная ошибка: если есть более одной точки, равной *cur,
  // то алгоритм может выдать некорректный результат.
  // Как можно исправить эту ситуацию?
  
  // Поставить её в конец последовательности для того,
  // чтобы корректно выйти из цикла, когда следующая вершина совпадёт с ней.
  const auto last_pos = end - 1;
  swap(*cur, *last_pos);
  cur = last_pos;

  // Цикл по вершинам выпуклой оболочки.
  while (true)
  {
    const auto next = max_cw_turn(begin, end, *cur);
    // Поставить следующую вершину.
    swap(*begin, *next);
    cur = begin++;

    if (next == last_pos) // Выпуклая оболочка построена.
      return begin;
  }
}

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

/// Тест на основе заранее известной оболочки.
int test_chj_0()
{
  Point_2 points[]
  {
    {  0,  0 },
    { 10,  0 },
    {  0, 10 },
    { 10, 10 },
    {  0,  1 },
    {  0,  0 },
    {  5,  0 },
    {  5,  5 },
    {  2,  7 }
  };
  const auto points_sz = sizeof(points) / sizeof(Point_2);

  const Point_2 ch[]
  {
    {  0, 10 },
    {  0,  0 },
    { 10,  0 },
    { 10, 10 },
  };
  const auto ch_sz = sizeof(ch) / sizeof(Point_2);

  if (convex_hull_jarvis(points, points + points_sz)
    - points != ch_sz) // в оболочке должно быть ch_sz вершин
    return 1;
  
  for (int i = 0; i < ch_sz; ++i)
    if (points[i] != ch[i])
      return 2;
  return 0;
}

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

Во-первых, это проверка многоугольника на строгую выпуклость, т.е. проверка того, что при обходе его вершин в прямом порядке мы всегда поворачиваем налево. Результат работы функции convex_hull_jarvis должен быть строго выпуклым многоугольником.

/// Проверка многоугольника на строгую выпуклость.
bool is_strictly_convex(const Point_2 *begin, const Point_2 *end)
{
  if (end - begin < 2)
    return true; // одна точка

  if (end - begin < 3)
    return begin[0] != begin[1]; // отрезок

  // Проходя по всем углам (парам смежных рёбер) многоугольника,
  // проверять, что поворот происходит строго против ЧС.
  auto a = *(end - 2), b = *(end - 1);
  do
  {
    const auto c = *begin++;
    const auto // рёбра
      ba = b - a,
      cb = c - b;

    // Проверить поворот от ba к cb.
    if (crossp(ba, cb) <= 0.)
      return false;

    a = b;
    b = c;
  } while (begin != end);

  return true;
}

Значительно сложнее выполнить проверку принадлежности всех точек исходного множества, которые не были выбраны в качестве вершин выпуклой оболочки, внутренности этой выпуклой оболочки.

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

/// Положение точки относительно множества.
enum Point_location
{
  point_location_inside,   // внутри
  point_location_boundary, // на границе
  point_location_outside   // снаружи
};

/// Определить положение точки p относительно многоугольника [begin, end),
/// в котором вершины перечислены в порядке обхода против часовой стрелки.
/// Осторожно: на результат может влиять погрешность вычислений.
/// Используется правило витков (== ненулевого индекса).
Point_location locate_point
  (
    const Point_2 *begin, const Point_2 *end, // многоугольник
    Point_2 p,                                // точка
    double tolerance = 0.                     // условный допуск на границе
  )
{
  using std::abs;
  if (begin == end)
    return point_location_outside;

  int wn = 0; // количество витков
  // Проходя по всем рёбрам многоугольника, считать количество витков.
  auto prev = *(end - 1);
  do
  {
    const auto next = *begin++;
    const auto
      edge = next - prev,
      prad = p - prev;

    const auto cp = crossp(prad, edge);
    // Ребро пересекает луч снизу-вверх справа от точки p.
    if (prev.y <= p.y && p.y < next.y && 0. < cp)
      ++wn;
    // Ребро пересекает луч сверху-вниз справа от точки p.
    else if (next.y <= p.y && p.y < prev.y && cp < 0.)
      --wn;
    // Дополнительная проверка: точка лежит на ребре
    else if (abs(cp) <= tolerance
          && dotp(prad, prad) <= dotp(prad, edge))
      return point_location_boundary;

    prev = next;
  } while (begin != end);

  return wn == 0 ? point_location_outside : point_location_inside;
}

Теперь, если дано множество точек, можно выполнить на нём функцию convex_hull_jarvis и затем проверить результат на корректность.

/// Проверить алгоритм выпуклой оболочки на заданном наборе точек.
int test_cvj_on(Point_2 *begin, Point_2 *end)
{
  const auto ch_end = convex_hull_jarvis(begin, end);
  if (!is_strictly_convex(begin, ch_end))
    return 1;

  for (auto p = ch_end; p != end; ++p)
    if (locate_point(begin, ch_end, *p) != point_location_inside)
      return 2;

  return 0;
}

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

/// Заполнить диапазон случайными точками с нормальным распределением по каждой координате.
/// Центр в нуле, среднеквадратичное отклонение единица.
void fill_random_normal(Point_2 *begin, Point_2 *end)
{
  using namespace std;
  random_device seed_gen;      // генератор случайного зерна
  mt19937_64 rng(seed_gen());  // генератор псевдослучайных последовательностей бит
  normal_distribution<> distr; // нормальное распределение
  while (begin != end)
    *begin++ = Point_2(distr(rng), distr(rng));
}

/// Сгенерировать случайный набор точек и проверить на нём алгоритм выпуклой оболочки.
int test_cvj_1()
{
  using namespace std;
  random_device seed_gen;      // генератор случайного зерна
  mt19937_64 rng(seed_gen());  // генератор псевдослучайных последовательностей бит
  uniform_int_distribution<> distr(3, 2000); // равномерное распределение на целых из [3, 2000]

  // Случайное количество точек.
  const auto sz = distr(rng);
  cout << sz << '\t';
  auto points = new Point_2[sz];
  // Сгенерировать случайные точки.
  fill_random_normal(points, points + sz);
  // Проверить работу алгоритма на этом наборе точек.
  const auto result = test_cvj_on(points, points + sz);
  cout << result << endl;
  delete[] points;
  return result;
}

C++, HTML

Варианты

1

Найти наиболее длинную общую подстроку двух произвольных строк. Если “самых” длинных несколько, то вернуть любую из них.

Пример

Даны строки “this is a description of another situation” и “that situation has been described already”. Самая длинная общая подстрока " situation" (с пробелом), находится на позиции 32 в первой строке и позиции 4 во второй строке.

2

Матричная игра с нулевой суммой. Пусть дана N×M-матрица (a_ij). Рассмотрим ситуацию, в которой два игрока независимо друг от друга выбирают числа:

• первый игрок — число i от 1 до N,
• второй игрок — число j от 1 до M.

После того, как игроки выбрали свои числа, они получают следующий выигрыш:

• первый игрок — a_ij,
• второй игрок — –a_ij.

Вычислить гарантии игроков (найти соответствующие координаты — числа, которые могут выбрать игроки, и гарантированные таким выбором значения выигрышей игроков):

• первый игрок — max_i min_j a_ij,
• второй игрок — –min_j max_i a_ij.

3

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

Пример

В 10×8 массиве найти строку “railgun”:

abcdefgh
backstar
contenta
dreameri
edgecurl
factormg
gammatru
hazelinn
imaginer
railgate

Результат: вертикальное расположение с позиции (1, 7).

4

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

Пример

Дана матрица:

1 2 0 3
0 4 5 1
0 4 1 2
9 0 4 8

Результат:

0 3 1 2
1 0 4 5
1 2 0 4
4 8 9 0

5

Даны две строки, которые назовём текст и слово, а также символ c. Требуется найти первое с начала текста вхождение слова в текст (или убедиться в его отсутствии). При этом “вхождением” считается совпадение символов в тексте и слове в соответствующих позициях кроме случая, когда в слове стоит символ c. Считается, что этот символ совпадает с любым символом текста.

Пример

Дано: текст = “somewhere out there”, слово = “?here”, c = ‘?’. Первое вхождение на позиции 4 “where” (следующее вхождение — 14 “there”).

6

Даны две строки, которые назовём текст и слово, а также количество допустимых несовпадений d. Требуется найти первое с начала текста вхождение слова в текст (или убедиться в его отсутствии). При этом “вхождением” считается совпадение символов в тексте и слове в соответствующих позициях за исключением не более чем d из них.

Пример

Дано: текст = “ATTACAUATTAUGGA”, слово = “AATTAGG”, d = 2. Первое вхождение на позиции 6 “UATTAUG”.

7

Дан текст и массив строк. Построить новую строку как результат замены в тексте подстрок вида %% на %, а подстрок вида %i% на строку из массива с номером i, если i — допустимый индекс (в противном случае не выполнять подстановку, оставляя соответствующий фрагмент %i% “как есть”).

Пример

Дано: текст: “There are %2% %3% in %0% %1% of %5% with %4%%% acidity.”, массив строк:

{
    "tank",
    "B",
    "250",
    "litres",
    "1.5",
    "water"
}

Результирующая строка: “There are 250 litres in tank B of water with 1.5% acidity.”

8

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

Пример

Дано: “alpha (beta (gamma (delta 3) 2) 1) 0” и уровень вложенности 2. Результат — “alpha (beta 1) 0”.

Если для той же строки задать уровень вложенности 3, то в результате получим “alpha (beta (gamma 2) 1) 0”.

9

Рассмотрим следующую ситуацию. Пусть есть “ключ”, состоящий из цифр и заглавных латинских букв, который был в спешке записан от руки. В нём есть символы, напоминающие 1 и I, 0 и O. Требуется написать программу, которая, получив строку, выводит все варианты комбинаций 1/I и 0/O (остальные символы остаются неизменными).

Пример

Пусть дана строка "0AB-3YZ-V18". Тогда программа должна вывести (в произвольном порядке) все следующие строки:

0AB-3YZ-V18
0AB-3YZ-VI8
OAB-3YZ-V18
OAB-3YZ-VI8

Рекомендуется использовать рекурсию.

10

Написать функцию, приближённо вычисляющую минимакс (или максимин; его значения и значения аргументов, в которых он достигается) произвольной заданной функции двух аргументов на заданной прямоугольной области (числа a, b, c, d) в предположении, что эта функция удовлетворяет теореме о минимаксе.

В качестве модельных (тестовых) функций попробовать следующий набор:

1. f(x, y) = xy.
2. f(x, y) = x² – y² (случай эквивалентен 1).
3. f(x, y) = exp(x) – exp(y).
4. f(x, y) = arctg(x) arctg(y) (условие теоремы не выполняется).

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

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

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