Мехмат, 1 курс
Работа на ЭВМ и программирование
Автоматизированный тест по матрицам

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

В некоторых вариантах критерий сравнения стобцов матрицы выражался через веса столбцов (столбец с индексом $j_1$ меньше столбца с индексом $j_2$, если $w_1 < w_2$, где $w_1$, $w_2$ — веса этих столбцов); веса столбцов определяются по-разному в разных вариантах. В других вариантах вместо столбцов матрицы надо упорядочивать ее строки. В каких-то вариантах сортировать столбцы или строки надо по возрастанию, в каких-то — по убыванию.

Исходная матрица записана в файле "input.txt" в следующем формате: сначала два целых числа $n$ и $m$, где $n$ — число строк, $m$ — число столбцов матрицы, затем сами элементы матрицы по строкам (сначала первая строка, затем вторая и т.д.). Элементы в файле разделяются пробельными символами (white space) или переводами строк. Пример матрицы размера 3x4: 

3 4
 1 -3.5  17  8
 0  2.6  -7  9
10    4 3.5 -4

В выходной файл "output.txt" записывается измененная матрица (с отсортированными по возрастанию столбцами) в том же формате, затем пустая строка, и затем вычисленный вектор. Пример выходного файла: 

3 4
-3.500000 1.000000 8.000000 17.000000 
2.600000 0.000000 9.000000 -7.000000 
4.000000 10.000000 -4.000000 3.500000 

23.500000 -50.100000 144.250000

Рассмотрим сначала вариант 101, вот его задание: "TheTask101.txt". В данном варианте используется следующий критерий сравнения столбцов матрицы $a$: столбец с индексом $j_2$ больше столбца с индексом $j_1$, если $$ \sum_{i=0}^{n-1} (a_{i,j_2} - a_{i,j_1}) > 0. $$ Измененная матрица умножается на ее транспонированную последнюю строку (см. задание в файле "TheTask101.txt").

Ниже будут рассмотрены также другие варианты:

  • задание 102 ("TheTask102.txt"), здесь критерий сравнения столбцов матрицы основан на сравнении весов столбцов, причем в этом варианте столбцы надо упорядочить по убыванию весов;
  • задание 104 ("TheTask104.txt"), здесь также критерий сравнения столбцов матрицы основан на сравнении весов столбцов, но используется другое определение веса столбца, столбцы также надо упорядочить по убыванию весов;
  • задание 114 ("TheTask114.txt"), в нем надо сортировать не столбцы, а строки матрицы, в качестве критерия сравнения строк используются нормы строк матрицы (в данном варианте норма строки — сумма квадратов ее элементов). Строки упорядочиваются по возрастанию.

Отметим, что программа должна корректно обрабатывать все ситуации, связанные с неправильными исходными данными. В частности, программа должна возвращать код завершения -1 операционной системе, если данные некорректны (нет исходного файла "input.txt", или этот фал пустой, или не удалось прочитать размеры матрицы $n$, $m$, или $n\le 0$ либо $m\le 0$, или не удалось прочитать все $n\cdot m$ элементов матрицы). Если данные корректны, то программа должна завершиться правильно и вернуть код 0 операционной системе (путем исполнения "return 0;" в функции main или "exit(0);" где угодно). Причем в любом случае утечка памяти (memory leak) не допускается.

Как решить эту задачу (т.е. быстро написать программу, которая пройдет автоматический тест, и при этом не запутаться)? Предлагается разбивать задачу на элементарные шаги и каждый шаг по возможности оформлять в виде отдельной функции. Каждая функция получается максимально простой, что сводит к минимуму вероятность ошибок.

Вариант 101

Вот задание этого варианта: "TheTask101.txt"). Здесь критерий сравнения столбцов матрицы $a$ следующий: столбец с индексом $j_2$ больше столбца с индексом $j_1$, если $$ \sum_{i=0}^{n-1} (a_{i,j_2} - a_{i,j_1}) > 0. $$ Измененная матрица умножается на свою последнюю транспонированную строку, представляющую собой вектор-столбец.

Вот ссылка на программу, которая решает эту задачу: "task101.cpp".

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

bool readMatrix(double **a, int *n, int *m);
double compareCols(const double *a, int n, int m, int j1, int j2);
void sortCols(double *a, int n, int m);
void swapCols(double *a, int n, int m, int j1, int j2);

Функция readMatrix читает матрицу из файла "input.txt". Ей передаются выходные аргументы, являющиеся указателями на переменные, в которые записываются адрес массива в динамической памяти, содержащего элементы матрицы, а также число строк $n$ и столбцов $m$ матрицы. Функция возвращает true в случае успеха и false в противном случае. Вот как ее можно использовать: 

    double *a;
    int n, m;
    if (!readMatrix(&a, &n, &m))
        return (-1);    // Ошибка ввода матрицы

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

bool readMatrix(double **a, int *n, int *m) {
    FILE *in = fopen("input.txt", "rt");
    if (in == NULL) {
        perror("Cannot open the input file");
        return false;
    }

    int rows, cols;
    if (
        fscanf(in, "%d%d", &rows, &cols) < 2 ||
        rows <= 0 || cols <= 0
    ) {
        fprintf(stderr, "Incorrect input file.\n");
        fclose(in);
        return false;
    }

    double *matr = new double[rows*cols];
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (fscanf(in, "%lf", &(matr[i*cols + j])) < 1) {
                fprintf(stderr, "Incorrect input file.\n");
                delete[] matr;
                return false;
            }
        }
    }
    fclose(in);
    *a = matr;
    *n = rows;
    *m = cols;
    return true;
}

В отличие от функции чтения матрицы, функция сравнения столбцов матрицы специфична для каждой задачи, ее требуется менять (заметим, изменять только тело функции, но не ее прототип!). Функции передается константный указатель на массив элементов матрицы (константный, потому что функция не изменяет матрицу), размеры $n$ и $m$ матрицы (размеры матрицы передаются обязательно во все функции, работающие с матрицей!), а также индексы $j_1$ и $j_2$ сравниваемых столбцов. Функция возвращает отрицательное число, если столбец с индексом $j_1$ меньше столбца с индексом $j_2$, 0 если они равны, и положительное число, если стобец $j_1$ больше столбца $j_2$. Вот реализация этой функции для данной конкретной задачи "TheTask101.txt": 

double compareCols(const double *a, int n, int m,  int j1, int j2) {
    double s = 0.;
    for (int i = 0; i < n; ++i) {
        s += a[i*m + j1] - a[i*m + j2];
    }
    return s;
}

Эта функция сравнения столбцов матрицы compareCols используется в функции сортировки столбцов матрицы sortCols. Мы используем алгоритм сортировки вставками Insertion Sort (самый лучший из числа простейших алгоритмов сортировки). Вот реализация этой функции: 

void sortCols(double *a, int n, int m) {
    // Using the Insertion Sort algorithm
    int k = 0;          // Number of already sorted columns
    while (k < m) {
        int col = k;    // The first unsorted column
        while (col > 0) {
            if (compareCols(a, n, m, col-1, col) <= 0.)
                break;  // Ok!
            swapCols(a, n, m, col-1, col);
            --col;
        }
        ++k;
    }
}

Так же, как и функция readMatrix, эта функция одинакова во всех заданиях и не требует никаких изменений в тексте программы. Аналогично, изменений не требует и функция обмена двух столбцов матрицы с индексами $j_1$ и $j_2$: 

void swapCols(double *a, int n, int m, int j1, int j2) {
    for (int k = 0; k < n; ++k) {
        double tmp = a[k*m + j1];
        a[k*m + j1] = a[k*m + j2];
        a[k*m + j2] = tmp;
    }
}

Наконец, вот реализация функции main программы, соответствующей заданию "TheTask101.txt": 

int main() {
    double *a;  // Matrix array
    int n, m;   // rows, columns
    if (!readMatrix(&a, &n, &m))
        return (-1);
    sortCols(a, n, m);

    // Multiply the changed matrix to its transposed last row
    double *c = new double[n];      // Output vector
    const double *b = a + (n-1)*m;  // The last row of matrix a
    for (int i = 0; i < n; ++i) {
        c[i] = 0.;
        for (int k = 0; k < m; ++k) {
            c[i] += a[i*m + k]*b[k];
        }
    }

    // Write the results in the file "output.txt"
    FILE *out = fopen("output.txt", "wt");
    if (out == NULL) {
        perror("Cannot open the output file");
        delete[] a;
        delete[] c;
        return (-1);
    }
    fprintf(out, "%d %d\n", n, m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            fprintf(out, "%f ", a[i*m + j]);
        }
        fprintf(out, "\n");
    }

    fprintf(out, "\n");
    for (int j = 0; j < n; ++j) {
        fprintf(out, "%f ", c[j]);
    }
    fprintf(out, "\n");

    fclose(out);
    delete[] a;
    delete[] c;
    return 0;
}

Приведем полный текст программы, файл "task101.cpp": 

#include <stdio.h>
#include <math.h>

bool readMatrix(double **a, int *n, int *m);
double compareCols(const double *a, int n, int m, int j1, int j2);
void sortCols(double *a, int n, int m);
void swapCols(double *a, int n, int m, int j1, int j2);

int main() {
    double *a;  // Matrix array
    int n, m;   // rows, columns
    if (!readMatrix(&a, &n, &m))
        return (-1);
    sortCols(a, n, m);

    // Multiply the changed matrix to its transposed last row
    double *c = new double[n];      // Output vector
    const double *b = a + (n-1)*m;  // The last row of matrix a
    for (int i = 0; i < n; ++i) {
        c[i] = 0.;
        for (int k = 0; k < m; ++k) {
            c[i] += a[i*m + k]*b[k];
        }
    }

    // Write the results in the file "output.txt"
    FILE *out = fopen("output.txt", "wt");
    if (out == NULL) {
        perror("Cannot open the output file");
        delete[] a;
        delete[] c;
        return (-1);
    }
    fprintf(out, "%d %d\n", n, m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            fprintf(out, "%f ", a[i*m + j]);
        }
        fprintf(out, "\n");
    }

    fprintf(out, "\n");
    for (int j = 0; j < n; ++j) {
        fprintf(out, "%f ", c[j]);
    }
    fprintf(out, "\n");

    fclose(out);
    delete[] a;
    delete[] c;
    return 0;
}

bool readMatrix(double **a, int *n, int *m) {
    FILE *in = fopen("input.txt", "rt");
    if (in == NULL) {
        perror("Cannot open the input file");
        return false;
    }

    int rows, cols;
    if (
        fscanf(in, "%d%d", &rows, &cols) < 2 ||
        rows <= 0 || cols <= 0
    ) {
        fprintf(stderr, "Incorrect input file.\n");
        fclose(in);
        return false;
    }

    double *matr = new double[rows*cols];
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (fscanf(in, "%lf", &(matr[i*cols + j])) < 1) {
                fprintf(stderr, "Incorrect input file.\n");
                delete[] matr;
                return false;
            }
        }
    }
    fclose(in);
    *a = matr;
    *n = rows;
    *m = cols;
    return true;
}

double compareCols(const double *a, int n, int m,  int j1, int j2) {
    double s = 0.;
    for (int i = 0; i < n; ++i) {
        s += a[i*m + j1] - a[i*m + j2];
    }
    return s;
}

void sortCols(double *a, int n, int m) {
    // Using the Insertion Sort algorithm
    int k = 0;          // Number of already sorted columns
    while (k < m) {
        int col = k;    // The first unsorted column
        while (col > 0) {
            if (compareCols(a, n, m, col-1, col) <= 0.)
                break;  // Ok!
            swapCols(a, n, m, col-1, col);
            --col;
        }
        ++k;
    }
}

void swapCols(double *a, int n, int m, int j1, int j2) {
    for (int i = 0; i < n; ++i) {
        double tmp = a[i*m + j1];
        a[i*m + j1] = a[i*m + j2];
        a[i*m + j2] = tmp;
    }
}

Вариант 102

Вот задание этого варианта: "TheTask102.txt". Здесь критерий сравнения столбцов матрицы $a$ основан на сравнении весов столбцов, причем в этом варианте столбцы надо упорядочить по убыванию весов. Вес $w_j$ столбца с индексом $j$ определяется как сумма модулей разностей его соседних элементов: $$ w_j = \sum_{i=0}^{n-2} |a_{i,j} - a_{i+1,j}| $$

Вот ссылка на программу, решающую данную задачу: "task102.cpp".

В программе используются следующие вспомогательные функции: 

bool readMatrix(double **a, int *n, int *m);
double compareCols(const double *a, int n, int m, int j1, int j2);
double columnWeight(const double *a, int n, int m, int j);
void sortCols(double *a, int n, int m);
void swapCols(double *a, int n, int m, int j1, int j2);

По сравнению с разобранным вариантом 101, здесь изменены только две функции:
1) функция 

double columnWeight(const double *a, int n, int m, int j);
вычисляет вес j-го столбца матрицы, вот ее реализация: 
double columnWeight(const double *a, int n, int m, int j) {
    double w = 0.;
    for (int i = 0; i < n-1; ++i) {
        w += fabs(a[i*m + j] - a[(i+1)*m + j]);
    }
    return w;
}
2) функция 
double compareCols(const double *a, int n, int m, int j1, int j2);
сравнения двух столбцов основана на сравнении весов столбцов, вот ее реализация: 
double compareCols(const double *a, int n, int m,  int j1, int j2) {
    double w1 = columnWeight(a, n, m, j1);
    double w2 = columnWeight(a, n, m, j2);
    return (w2 - w1);   // Sic! Sorting in descending order
}
Важно!!! Поскольку в задании надо упорядочить столбцы матрицы по убыванию, а не по возрастанию, как в задании 101, то здесь мы возвращаем положительное число, если первый столбец $j_1$ меньше второго $j_2$ (как бы вычитаем из второго столбца первый, а не наоборот, как в задании 101).

Все остальные функции в этом задании такие же, как и в задании 101.

Вариант 104

Вот задание этого варианта: "TheTask104.txt". Здесь критерий сравнения столбцов матрицы $a$ также основан на сравнении весов столбцов, причем в этом варианте столбцы тоже надо упорядочивать по убыванию весов. Вес $w_j$ столбца с индексом $j$ определяется как сумма только положительных разностей его соседних элементов: $$ w_j = \sum_{i:\;a_{i+1,j}>a_{i,j}} (a_{i+1,j} - a_{i,j}) $$

Вот ссылка на программу, решающую данную задачу: "task104.cpp".

По сравнению с вариантом 102 изменена только функция,
вычисляющая вес j-го столбца: 

double columnWeight(const double *a, int n, int m, int j) {
    double w = 0.;
    for (int i = 0; i < n-1; ++i) {
        double d = a[(i+1)*m + j] - a[i*m + j];
        if (d > 0.)
            w += d;
    }
    return w;
}

Вариант 114

Вот задание этого варианта: "TheTask114.txt".

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

Вот ссылка на программу, решающую данную задачу: "task114.cpp".

В программе используются следующие вспомогательные функции: 

bool readMatrix(double **a, int *n, int *m);
double compareRows(const double *a, int n, int m, int i1, int i2);
double rowNorm(const double *a, int n, int m, int i);
void sortRows(double *a, int n, int m);
void swapRows(double *a, int n, int m, int i1, int i2);
Здесь синим цветом выделены прототипы функций, отличающиеся от соответствующих функций в задании 101. Приведем их реализации.

Функция rowNorm(a, n, m, i) вычисляет норму i-й строки матрицы a размера n на m: 

double rowNorm(const double *a, int n, int m, int i) {
    assert(0 <= i && i < n);
    double s = 0.;
    for (int j = 0; j < m; ++j) {
        double d = a[i*m + j];
        s += d*d;
    }
    return s;
}

Обратите внимание! Строка 

    assert(0 <= i && i < n);
используется не только для проверки корректности индекса i строки матрицы. Если опустить эту проверку, то компилятор выдаст предупреждение о неиспользуемой переменной n, а применяемый при тестировании C/C++ компилятор воспринимает все предупреждения как ошибки.

Функция compareRows(a, n, m, i1, i2) сравнивает строки $i_1$, $i_2$ матрицы на основе сравнения их норм по возрастанию: 

double compareRows(const double *a, int n, int m,  int i1, int i2) {
    double s1 = rowNorm(a, n, m, i1);
    double s2 = rowNorm(a, n, m, i2);
    return (s1 - s2);
}

Функция sortRows(a, n, m) сортирует строки матрицы на основе критерия сравнения строк (функции compareRows): 

void sortRows(double *a, int n, int m) {
    // Using the Insertion Sort algorithm
    int k = 0;          // Number of already sorted rows
    while (k < n) {
        int row = k;    // The first unsorted row
        while (row > 0) {
            if (compareRows(a, n, m, row-1, row) <= 0.)
                break;  // Ok!
            swapRows(a, n, m, row-1, row);
            --row;
        }
        ++k;
    }
}

Функция swapRows(a, n, m, i1, i2) меняет местами строки $i_1$, $i_2$ матрицы: 

void swapRows(double *a, int n, int m, int i1, int i2) {
    assert(0 <= i1 && i1 < n);
    assert(0 <= i2 && i2 < n);

    for (int j = 0; j < m; ++j) {
        double tmp = a[i1*m + j];
        a[i1*m + j] = a[i2*m + j];
        a[i2*m + j] = tmp;
    }
}
Выделенные синим цветом предложения assert нужны не только для проверки корректности индексов строк матрицы, но и для того, чтобы не выдавалось предупреждение о неиспользуемой переменной n.

Приведем полный текст программы для варианта 114, (задание "TheTask114.txt"). 

#include <stdio.h>
#include <math.h>
#include <assert.h>

bool readMatrix(double **a, int *n, int *m);
double compareRows(const double *a, int n, int m, int i1, int i2);
double rowNorm(const double *a, int n, int m, int i);
void sortRows(double *a, int n, int m);
void swapRows(double *a, int n, int m, int i1, int i2);

int main() {
    double *a;  // Matrix array
    int n, m;   // rows, columns
    if (!readMatrix(&a, &n, &m))
        return (-1);
    sortRows(a, n, m);

    // Multiply the changed matrix to its transposed last row
    double *c = new double[n];      // Output vector
    const double *b = a + (n-1)*m;  // The last row of matrix a
    for (int i = 0; i < n; ++i) {
        c[i] = 0.;
        for (int k = 0; k < m; ++k) {
            c[i] += a[i*m + k]*b[k];
        }
    }

    // Write the results in the file "output.txt"
    FILE *out = fopen("output.txt", "wt");
    if (out == NULL) {
        perror("Cannot open the output file");
        delete[] a;
        delete[] c;
        return (-1);
    }
    fprintf(out, "%d %d\n", n, m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            fprintf(out, "%f ", a[i*m + j]);
        }
        fprintf(out, "\n");
    }

    fprintf(out, "\n");
    for (int j = 0; j < n; ++j) {
        fprintf(out, "%f ", c[j]);
    }
    fprintf(out, "\n");

    fclose(out);
    delete[] a;
    delete[] c;
    return 0;
}

bool readMatrix(double **a, int *n, int *m) {
    FILE *in = fopen("input.txt", "rt");
    if (in == NULL) {
        perror("Cannot open the input file");
        return false;
    }

    int rows, cols;
    if (
        fscanf(in, "%d%d", &rows, &cols) < 2 ||
        rows <= 0 || cols <= 0
    ) {
        fprintf(stderr, "Incorrect input file.\n");
        fclose(in);
        return false;
    }

    double *matr = new double[rows*cols];
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (fscanf(in, "%lf", &(matr[i*cols + j])) < 1) {
                fprintf(stderr, "Incorrect input file.\n");
                delete[] matr;
                return false;
            }
        }
    }
    fclose(in);
    *a = matr;
    *n = rows;
    *m = cols;
    return true;
}

double compareRows(const double *a, int n, int m,  int i1, int i2) {
    double s1 = rowNorm(a, n, m, i1);
    double s2 = rowNorm(a, n, m, i2);
    return (s1 - s2);
}

double rowNorm(const double *a, int n, int m, int i) {
    assert(0 <= i && i < n);
    double s = 0.;
    for (int j = 0; j < m; ++j) {
        double d = a[i*m + j];
        s += d*d;
    }
    return s;
}

void sortRows(double *a, int n, int m) {
    // Using the Insertion Sort algorithm
    int k = 0;          // Number of already sorted rows
    while (k < n) {
        int row = k;    // The first unsorted row
        while (row > 0) {
            if (compareRows(a, n, m, row-1, row) <= 0.)
                break;  // Ok!
            swapRows(a, n, m, row-1, row);
            --row;
        }
        ++k;
    }
}

void swapRows(double *a, int n, int m, int i1, int i2) {
    assert(0 <= i1 && i1 < n);
    assert(0 <= i2 && i2 < n);

    for (int j = 0; j < m; ++j) {
        double tmp = a[i1*m + j];
        a[i1*m + j] = a[i2*m + j];
        a[i2*m + j] = tmp;
    }
}