serg.tk

Задача для автоматизированого зачета

Рассмотрим матрицу A размера n на m (n строк, m столбцов), элементами которой являются формальные слова. Слово является произвольной последовательностью символов, которая может включать пробелы. Слово может быть пустым, то есть не содержать ни одного символа. Каждой строке матрицы можно сопоставить слово, полученное последовательным выписыванием элементов этой строки матрицы. Например, нулевой строке матрицы 

        abb  xa
        x    abd
будет сопоставлено слово abbxa. Обозначим такое слово для строки с номером k через W(A, k) или просто W(k), так матрица A фиксирована. Таким образом, W(0)=abbxa. Обращением слова X назовем слово R(X), полученное выписыванием букв слова X справа-налево. В нашем примере получим, что R(W(1)) = dbax.

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

Варианты заданий. Номер задачи получается приписыванием номера варианта для выбора строки (select) к номеру варианта для "сложения" строк (add), то есть task = 10*select + add.

Условие выбора строки матрицы
  1. Слово W(k) является палиндромом, то есть W(k) = R(W(k)).
  2. Слово W(k) является минимальным в лексикографическом порядке среди всех слов W(i), i = 0,...,n-1.
  3. Обращенное слово R(W(k)) содержит некоторое из слов A_kq в качестве подслова (=подстроки).
  4. Обращенное слово R(W(k)) совпадает с некоторым из слов W(i), i=0,...,n-1.
  5. Слово W(k) содержит в качестве подслова (=подстроки) обращение R(A_kq) некоторого элемента A_kq.
"Сложение" найденной строки k и строки p (поэлементное преобразование для каждого q = 0, ..., m-1)
  1. Вычеркивание из слова A_pq букв слова A_kq (с сохранением порядка оставшихся букв).
  2. Приписывание слова A_kq слева от A_pq.
  3. Приписывание слова A_kq справа от A_pq.
  4. Замена слова A_pq на слово, которое получается вычеркиванием из A_kq букв слова A_pq (с сохранением порядка оставшихся букв).
  5. Вычеркивание из слова A_pq букв, которые не встречаются в слове A_kq (с сохранением порядка оставшихся букв).
Если сумма цифр номера задачи чётна, то матрица A представляется двумерным массивом, если нечётна — одномерным. Но это пожелание, вам было обещано, что выбор за вами.

Номера заданий указаны в столбце "Зачёт 1". Номера получены построением случайной перестановки в Wolfram Mathematica: SeedRandom[123]; tasks = Flatten[Table[10*s + a, {s, 1, 5}, {a, 1, 5}]]; RandomSample[tasks, Length[tasks]]. Претензии по поводу субъективности выбора номеров задач несостоятельны.

Требования к решению: ввод-вывод матрицы должен быть отделён от её обработки, преобразование матрицы должно быть реализовано в виде отдельной функции; функция преобразования матрицы должна модифицировать матрицу, а не создавать новую; функции должны быть снабжены документацией; запрещается выделять память (malloc/realloc и т.п.) для хранения строчек W(i), включая W(k), и их обращения; память для хранения матрицы A должна выделяться в минимально необходимом объёме; не должно быть утечек памяти и других ошибок valgrind; программа должна обрабатывать возможные ошибки (отсутствие файла, ошибки чтения, несоответствия формату и т.п.); при считывании матрицы из файла можно использовать функцию getline.

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

        2 2
        a_00
        second item of the first row

        yyy
Элементом матрицы является строчка исходного текстового файла. A_01 = "second item of the first row". Символ перевода строки не включается. Заметим, что A_10 является пустой строкой.

Технические требования:

Процедура сдачи.