fork download
copy 
  1. /* ============================================================
  2.    Подключаем стандартные типы:
  3.    size_t — беззнаковый тип для индексов и размеров
  4.    bool   — логический тип true / false
  5.    ============================================================ */
  6. #include <stddef.h>
  7. #include <stdbool.h>
  8.  
  9. /* ============================================================
  10.    СТРУКТУРА MATRIX
  11.    ============================================================
  12.  
  13.    Описывает матрицу объектов произвольного типа.
  14.  
  15.    data  — трёхуровневый указатель:
  16.            data[i][j] — указатель на объект в ячейке
  17.  
  18.    rows  — количество строк матрицы (m)
  19.    cols  — количество столбцов матрицы (n)
  20.    ============================================================ */
  21. typedef struct {
  22.     void*** data;   /* Двумерный массив указателей на объекты */
  23.     size_t rows;    /* Число строк */
  24.     size_t cols;    /* Число столбцов */
  25. } Matrix;
  26.  
  27. /* ============================================================
  28.    ТИП ФУНКЦИИ СРАВНЕНИЯ
  29.    ============================================================
  30.  
  31.    Так как элементы имеют тип void*,
  32.    мы не знаем их реальный тип.
  33.  
  34.    Поэтому пользователь ОБЯЗАН передать
  35.    функцию сравнения элементов.
  36.  
  37.    Функция должна вернуть:
  38.    true  — если элементы равны
  39.    false — если элементы различны
  40.    ============================================================ */
  41. typedef bool (*CompareFunc)(const void* a, const void* b);
  42.  
  43. /* ============================================================
  44.    ПРОВЕРКА ТЕПЛИЦЕВОЙ МАТРИЦЫ
  45.    ============================================================
  46.  
  47.    Матрица теплицева, если:
  48.    все элементы на диагоналях,
  49.    идущих из левого верхнего угла
  50.    в правый нижний, одинаковы.
  51.  
  52.    Формально:
  53.    matrix[i][j] == matrix[i-1][j-1]
  54.    ============================================================ */
  55. bool is_toeplitz(const Matrix* matrix, CompareFunc cmp) {
  56.  
  57.     /* Начинаем со второй строки,
  58.        потому что первой не с чем сравнивать */
  59.     for (size_t i = 1; i < matrix->rows; ++i) {
  60.  
  61.         /* Начинаем со второго столбца
  62.            по той же причине */
  63.         for (size_t j = 1; j < matrix->cols; ++j) {
  64.  
  65.             /* Сравниваем текущий элемент
  66.                с элементом на диагонали выше */
  67.             if (!cmp(
  68.                 matrix->data[i][j],           /* текущий элемент */
  69.                 matrix->data[i - 1][j - 1]    /* диагональный элемент */
  70.             )) {
  71.                 /* Если хотя бы одна диагональ
  72.                    нарушена — матрица НЕ теплицева */
  73.                 return false;
  74.             }
  75.         }
  76.     }
  77.  
  78.     /* Если все диагонали корректны */
  79.     return true;
  80. }
  81.  
  82. /* ============================================================
  83.    ПРОВЕРКА ЦИКЛИЧЕСКОГО СДВИГА СТРОК
  84.    ============================================================
  85.  
  86.    Проверяет, что строка current_row
  87.    получена циклическим сдвигом строки
  88.    previous_row вправо на 1 позицию.
  89.  
  90.    Пример:
  91.    [1 2 3 4]
  92.    [4 1 2 3]
  93.  
  94.    Формула:
  95.    current[j] == previous[(j - 1 + cols) % cols]
  96.    ============================================================ */
  97. bool is_cyclic_shift_row(
  98.     const Matrix* matrix,     /* указатель на матрицу */
  99.     size_t previous_row,      /* индекс предыдущей строки */
  100.     size_t current_row,       /* индекс текущей строки */
  101.     CompareFunc cmp           /* функция сравнения */
  102. ) {
  103.     /* Запоминаем количество столбцов */
  104.     size_t cols = matrix->cols;
  105.  
  106.     /* Проходим по всем столбцам строки */
  107.     for (size_t j = 0; j < cols; ++j) {
  108.  
  109.         /* Вычисляем индекс элемента
  110.            в предыдущей строке с учётом
  111.            циклического перехода */
  112.         size_t prev_index = (j + cols - 1) % cols;
  113.  
  114.         /* Сравниваем элементы */
  115.         if (!cmp(
  116.             matrix->data[current_row][j],          /* текущий элемент */
  117.             matrix->data[previous_row][prev_index]/* ожидаемый элемент */
  118.         )) {
  119.             /* Если хотя бы один элемент
  120.                не совпал — сдвиг неверен */
  121.             return false;
  122.         }
  123.     }
  124.  
  125.     /* Все элементы совпали */
  126.     return true;
  127. }
  128.  
  129. /* ============================================================
  130.    ПРОВЕРКА ЦИКЛИЧЕСКОГО СДВИГА СТОЛБЦОВ
  131.    ============================================================
  132.  
  133.    Проверяет, что столбец current_col
  134.    получен циклическим сдвигом столбца
  135.    previous_col вниз на 1 позицию.
  136.  
  137.    Формула:
  138.    current[i] == previous[(i - 1 + rows) % rows]
  139.    ============================================================ */
  140. bool is_cyclic_shift_col(
  141.     const Matrix* matrix,     /* указатель на матрицу */
  142.     size_t previous_col,      /* индекс предыдущего столбца */
  143.     size_t current_col,       /* индекс текущего столбца */
  144.     CompareFunc cmp           /* функция сравнения */
  145. ) {
  146.     /* Количество строк */
  147.     size_t rows = matrix->rows;
  148.  
  149.     /* Проходим по всем строкам */
  150.     for (size_t i = 0; i < rows; ++i) {
  151.  
  152.         /* Индекс элемента с циклическим сдвигом */
  153.         size_t prev_index = (i + rows - 1) % rows;
  154.  
  155.         /* Сравнение элементов */
  156.         if (!cmp(
  157.             matrix->data[i][current_col],          /* текущий элемент */
  158.             matrix->data[prev_index][previous_col]/* ожидаемый элемент */
  159.         )) {
  160.             return false;
  161.         }
  162.     }
  163.  
  164.     return true;
  165. }
  166.  
  167. /* ============================================================
  168.    ГЛАВНАЯ ПРОВЕРКА ЦИРКУЛЯНТНОЙ МАТРИЦЫ
  169.    ============================================================
  170.  
  171.    Матрица считается циркулянтной, если:
  172.    1. Она теплицева
  173.    2. Каждая строка — циклический сдвиг предыдущей
  174.    3. Каждый столбец — циклический сдвиг предыдущего
  175.    ============================================================ */
  176. bool is_circulant(const Matrix* matrix, CompareFunc cmp) {
  177.  
  178.     /* Матрица 1×N или M×1 считается циркулянтной */
  179.     if (matrix->rows < 2 && matrix->cols < 2) {
  180.         return true;
  181.     }
  182.  
  183.     /* Проверяем теплицевость */
  184.     if (!is_toeplitz(matrix, cmp)) {
  185.         return false;
  186.     }
  187.  
  188.     /* Проверяем циклический сдвиг строк */
  189.     for (size_t i = 1; i < matrix->rows; ++i) {
  190.         if (!is_cyclic_shift_row(matrix, i - 1, i, cmp)) {
  191.             return false;
  192.         }
  193.     }
  194.  
  195.     /* Проверяем циклический сдвиг столбцов */
  196.     for (size_t j = 1; j < matrix->cols; ++j) {
  197.         if (!is_cyclic_shift_col(matrix, j - 1, j, cmp)) {
  198.             return false;
  199.         }
  200.     }
  201.  
  202.     /* Все условия выполнены */
  203.     return true;
  204. }
  205.  
  206. /* ============================================================
  207.    ТОЧКА ВХОДА В ПРОГРАММУ
  208.    ============================================================
  209.  
  210.    Нужна только для корректной линковки.
  211.    В учебной задаче логика находится выше.
  212.    ============================================================ */
  213. int main(void) {
  214.     return 0;
  215. }
  216.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
3
4
1 2 3 4
4 1 2 3
3 4 1 2
stdout
copy 
Standard output is empty
https://ideone.com/jcw70W
language:
C (gcc 8.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!