Мехмат, 1 курс
Работа на ЭВМ и программирование
Пробный автоматизированный тест по матрицам, 2026 г.
Для получения условия задачи с номером N надо выполнить команду
tasktest matrix4 N -text
(например, для задачи 101 команда "tasktest matrix4 101 -text"),
текст задания будет записан в файл "TheTask.txt". Для прохождения
пробного теста надо выполнить команду
tasktest matrix4 N file.cpp
где file.cpp — имя файла с программой.
Задача пробного автоматизированного теста состоит в том,
что надо ввести параметры задачи и
прямоугольную марицу из файла "data.txt", рассмотреть минор X матрицы,
образованный пересечением заданного множества строк и заданного
множества столбцов, и заменить элементы этого минора на
другие элементы в соответствии с условием задачи. При этом
элементы исходной матрицы, не входящие в минор X, изменять
не нужно. Параметры задачи и измененную матрицу надо записать
в файл "res.txt".
Задача 101 теста
Условие задачи
Зададим множество X как подмножество элементов двумерного массива,
лежащих на пересечении множества строк, каждая из которых содержит
элемент, остаток от деления которого на M равен N, и множества столбцов,
каждый из которых также содержит элемент, остаток от деления которого
на M равен N.
Для каждого элемента матрицы aij
из множества X заменить данный
элемент на 1, если он встречается в строке с номером i до данного
элемента (не включая данный элемент) в рамках описанного множества
столбцов исходного массива, иначе заменить элемент на 0.
Элементы не из пересечения данных множеств строк и столбцов
не должны измениться.
В файле data.txt через пробел записаны натуральны числа M, N, L, K
и далее элементы двумерного целочисленного массива,состоящего из L строк
и K столбцов, по одной строке массива в строке файла.
На количество элементов нет никаких ограничений.
Ввести из файла числа M, N, l, k в отдельные переменные и последующие
числа в двумерный массив, отведя соответствующим образом память.
Решить поставленную задачу.
В случае невозможности решения задачи (если нет файла data.txt, если из
файла data.txt невозможно ввести все требуемые числа, если невозможно
записать данные в файл res.txt) в файл res.txt по возможности должно
быть записано слово ERROR и функция main() должна вернуть значение -1,
иначе функция main() должна вернуть 0.
Параметры M, N, L, K и полученный массив элементов следует вывести
в файл res.txt в том же формате, что и исходные данные.
Планирование решения
Чтобы не запутаться, будем использовать переменные с теми же именами,
как и в условии задачи. Параметрами задания строк и столбцов минора X
матрицы будут целочисленные перменные M, N, размеры исходной матрицы
будут в переменных l, k (l строк и k столбцов). Номера строк у нас будут
начинаться с буквы i, номера столбцов с буквы j. Просто переменная i
будет обозначать номер строки в исходной матрице, переменная ix будет
обозначать номер строки внутри минора X; аналогично переменные
j и jx будут обозначать номер столбца в исходной матрице и внутри
минора X.
Для простоты мы будем хранить исходную и результирующую
матрицы в разных массивах: в массиве a0 исходная матрица,
в массиве a1 результирующая. Матрица хранится в линейном массиве
по строкам, таком образом, элемент
aij матрицы читается и записывается как
a[i*k + j]
И — принципиально для этой задачи! — мы будем хранить
номера строк минора X в массиве xRows[] размера numRows;
номера столбцов минора X будем хранить в массиве xColumns размера
numColumns. Таким образом, начало программы будет следующим:
#include <stdio.h>
#include <assert.h>
bool rowInX(int M, int N, int l, int k, const int *a, int row);
bool columnInX(int M, int N, int l, int k, const int *a, int column);
int main() {
int M, N, l, k; // Task parameters
int *a0 = nullptr; // Initial matrix
int *a1 = nullptr; // Resulting matrix
int *xRows = nullptr; // Indices of X-minor rows
int numRows = 0; // Number of rows in the X-minor
int *xColumns = nullptr; // Indices of X-minor columns
int numColumns = 0; // Number of columns in the X-minor
. . .
Функция rowInX(M, N, l, k, a, row) возвращает true тогда и только тогда,
когда строка с индексом row матрицы a принадлежит минору X в соответствии
с условием задачи. В начале файла, как обычно, мы описываем
только прототип функции, ее реализация будет приведена ниже по тексту:
bool rowInX(int M, int N, int l, int k, const int *a, int row) {
assert(0 <= row && row < l);
for (int j = 0; j < k; ++j) {
if (a[row*k + j]%M == N) {
return true;
}
}
return false;
}
Аналогично функция columnInX(M, N, l, k, a, column)
возвращает true тогда и только тогда,
когда столбец с индексом column матрицы a принадлежит минору X.
Ее реализация также будет приведена ниже:
bool columnInX(int M, int N, int l, int k, const int *a, int column) {
assert(0 <= column && column < k);
for (int i = 0; i < l; ++i) {
if (a[i*k + column]%M == N) {
return true;
}
}
return false;
}
Итак, начало функции main() следующее:
int main() {
int M, N, l, k; // Task parameters
int *a0 = nullptr; // Initial matrix
int *a1 = nullptr; // Resulting matrix
int *xRows = nullptr; // Indices of X-minor rows
int numRows = 0; // Number of rows in the X-minor
int *xColumns = nullptr; // Indices of X-minor columns
int numColumns = 0; // Number of columns in the X-minor
FILE *fin = fopen("data.txt", "r");
FILE *fout = fopen("res.txt", "w");
if (fin == NULL) {
if (fout != NULL) {
fprintf(fout, "ERROR\n");
fclose(fout);
}
return (-1);
}
if (fout == NULL) {
fclose(fout);
return (-1);
}
// Read the task parameters
if (fscanf(fin, "%d%d%d%d", &M, &N, &l, &k) < 4) {
fprintf(fout, "ERROR\n");
fclose(fin);
fclose(fout);
return (-1);
}
a0 = new int[l*k]; // Allocate a memory for the initial matrix and
a1 = new int[l*k]; // for the resulting matrix
for (int i = 0; i < l; ++i) {
for (int j = 0; j < k; ++j) {
// Read the matrix element
if (fscanf(fin, "%d", a0 + i*k + j) < 1) {
fprintf(fout, "ERROR\n");
fclose(fin);
fclose(fout);
delete[] a0;
delete[] a1;
return (-1);
}
// Copy the element from the initial matrix to the resulting
a1[i*k + j] = a0[i*k + j];
}
}
fclose(fin);
// Compute the set of rows of X-minor
xRows = new int[l];
numRows = 0;
for (int i = 0; i < l; ++i) {
if (rowInX(M, N, l, k, a0, i)) {
xRows[numRows] = i;
++numRows;
}
}
// Compute the set of columns of X-minor
xColumns = new int[k];
numColumns = 0;
for (int j = 0; j < k; ++j) {
if (columnInX(M, N, l, k, a0, j)) {
xColumns[numColumns] = j;
++numColumns;
}
}
. . .
Здесь мы сначала считываем параметры задачи, затем захватываем
память под исходную и результирующую матрицы, считываем данные
из файла, копируя элементы как в исходную, так и в результирующую
матрицы (вначале они будут одинаковыми). И в конце этого фрагмента программы
захватываем память (возможно, с избытком) под массивы индексов
строк и столбов минора X, а затем вычисляем эти индексы, подсчитывая
по ходу дела и размеры минора X.
И дальше идет основная часть программы — вычисление результирующей
матрицы a1 и запись результатов в выходной файл:
// Replace elements of the X-minor in the resulting matrix a1
for (int ix = 0; ix < numRows; ++ix) {
int i = xRows[ix];
assert(0 < = i && i < l);
for (int jx = 0; jx < numColumns; ++jx) {
int j = xColumns[jx];
assert(0 <= j && j < k);
int elem = a0[i*k + j];
// Check whether it is the first such element in i-th row
bool found = false;
for (int jx1 = 0; jx1 < jx; ++jx1) {
int j1 = xColumns[jx1];
if (a0[i*k + j1] == elem) {
found = true;
break;
}
}
if (found) {
a1[i*k + j] = 1; // It is NOT the first such element
} else {
a1[i*k + j] = 0; // It is the first such element
}
}
}
// Write the results
fprintf(fout, "%d %d %d %d\n", M, N, l, k);
for (int i = 0; i < l; ++i) {
for (int j = 0; j < k; ++j) {
if (j > 0)
fprintf(fout, " "); // Write the delimiter
fprintf(fout, "%d", a1[i*k + j]);
}
fprintf(fout, "\n");
}
fclose(fout);
delete[] a0;
delete[] a1;
delete[] xRows;
delete[] xColumns;
return 0;
}
Полный текст программы для варианта 101
Ниже приведен полный текст программы. Скачать его можно
также по ссылке "task101.cpp".
#include <stdio.h>
#include <assert.h>
bool rowInX(int M, int N, int l, int k, const int *a, int row);
bool columnInX(int M, int N, int l, int k, const int *a, int column);
int main() {
int M, N, l, k; // Task parameters
int *a0 = nullptr; // Initial matrix
int *a1 = nullptr; // Resulting matrix
int *xRows = nullptr; // Indices of X-minor rows
int numRows = 0; // Number of rows in the X-minor
int *xColumns = nullptr; // Indices of X-minor columns
int numColumns = 0; // Number of columns in the X-minor
FILE *fin = fopen("data.txt", "r");
FILE *fout = fopen("res.txt", "w");
if (fin == NULL) {
if (fout != NULL) {
fprintf(fout, "ERROR\n");
fclose(fout);
}
return (-1);
}
if (fout == NULL) {
fclose(fout);
return (-1);
}
// Read the task parameters
if (fscanf(fin, "%d%d%d%d", &M, &N, &l, &k) < 4) {
fprintf(fout, "ERROR\n");
fclose(fin);
fclose(fout);
return (-1);
}
a0 = new int[l*k]; // Allocate a memory for the initial matrix and
a1 = new int[l*k]; // for the resulting matrix
for (int i = 0; i < l; ++i) {
for (int j = 0; j < k; ++j) {
// Read the matrix element
if (fscanf(fin, "%d", a0 + i*k + j) < 1) {
fprintf(fout, "ERROR\n");
fclose(fin);
fclose(fout);
delete[] a0;
delete[] a1;
return (-1);
}
// Copy the element from the initial matrix to the resulting
a1[i*k + j] = a0[i*k + j];
}
}
fclose(fin);
// Compute the set of rows of X-minor
xRows = new int[l];
numRows = 0;
for (int i = 0; i < l; ++i) {
if (rowInX(M, N, l, k, a0, i)) {
xRows[numRows] = i;
++numRows;
}
}
// Compute the set of columns of X-minor
xColumns = new int[k];
numColumns = 0;
for (int j = 0; j < k; ++j) {
if (columnInX(M, N, l, k, a0, j)) {
xColumns[numColumns] = j;
++numColumns;
}
}
// Replace elements of the X-minor in the resulting matrix a1
for (int ix = 0; ix < numRows; ++ix) {
int i = xRows[ix];
assert(0 <= i && i < l);
for (int jx = 0; jx < numColumns; ++jx) {
int j = xColumns[jx];
assert(0 <= j && j < k);
int elem = a0[i*k + j];
// Check whether it is the first such element in i-th row
bool found = false;
for (int jx1 = 0; jx1 < jx; ++jx1) {
int j1 = xColumns[jx1];
if (a0[i*k + j1] == elem) {
found = true;
break;
}
}
if (found) {
a1[i*k + j] = 1; // It is NOT the first such element
} else {
a1[i*k + j] = 0; // It is the first such element
}
}
}
// Write the results
fprintf(fout, "%d %d %d %d\n", M, N, l, k);
for (int i = 0; i < l; ++i) {
for (int j = 0; j < k; ++j) {
if (j > 0)
fprintf(fout, " "); // Write the delimiter
fprintf(fout, "%d", a1[i*k + j]);
}
fprintf(fout, "\n");
}
fclose(fout);
delete[] a0;
delete[] a1;
delete[] xRows;
delete[] xColumns;
return 0;
}
bool rowInX(int M, int N, int l, int k, const int *a, int row) {
assert(0 <= row && row < l);
for (int j = 0; j < k; ++j) {
if (a[row*k + j]%M == N) {
return true;
}
}
return false;
}
bool columnInX(int M, int N, int l, int k, const int *a, int column) {
assert(0 <= column && column < k);
for (int i = 0; i < l; ++i) {
if (a[i*k + column]%M == N) {
return true;
}
}
return false;
}
Задача 102 пробного теста
Задача 102 очень похожа на задачу 101. Потребовалось не больше 5-ти минут,
чтобы переделать текст программы для задачи 101 в программу для задачи 102.
Вот условие задачи 102: "TheTask102.txt".
И вот программа для решения задачи 102:
"task102.cpp".
|