Tag Archives: матрица

e-olymp 5071. Проверка на неориенитрованность

by

0

Задача. Проверка на неориенитрованность

Условие задачи
По заданной квадратной матрице $n\times n$ из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

Входные данные

Входной файл содержит число $n(1\leq n\leq 100)$ — размер матрицы, и затем $n$ строк по $n$ чисел, каждое из которых равно $0$ или $1$ — саму матрицу.

Выходные данные

Выведите в выходной файл YES если приведенная матрица может быть матрицей смежности простого неориентированного графа и NO в противном случае.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
3
0 1 1
1 0 1
1 1 0		 YES
3
0 1 0
1 0 1
1 1 0		 NO
3
0 1 0
1 1 1
0 1 0		 NO
4
0 1 0 0
1 0 1 1
1 1 0 1
0 1 1 1		 NO

Код программы

Решение задачи

Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: $a[i] = a[j]$. Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия.
Создаём переменную f типа bool. Изначально f=true. Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, флаг устанавливается в «ложь» и происходит выход из цикла проверки. Это означает соответственно, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится «NO». Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим «YES».

А410е

by

0

Задача

Дана целочисленная матрица $ [a_{ij}], ij=1,\ldots,n.$ Получить $b_{1} \dots b_{n},$ где $b_{i}$ — это $\underset{1\leq j\leq n}{\max a_{ij}}\cdot \underset{1\leq j\leq n}{\min a_{ji}}$

Входные данные

Первая строка содержит число $n.$ Следующие строки содержат матрицу $n\times n.$

Выходные данные

Вывести $b_i \; i=1\dots n.$

Тесты

Входные данные Выходные данные
2
1 2
4 1		 2 4
3
1 2 3
4 1 -6
1 -2 -1		 3 -8 -6

Код программы

Решение

Очевидно, что из заданной матрицы нужно взять максимальный элемент $i$-й строки и умножить его на минимальный элемент $i$-го столбца. Для нахождения максимума [latex]a_{ij}[/latex], введем переменную и будем присваивать ей начальное значение первого элемента $i$-й строки. Чтобы при расчете максимума проходя по элементам строки мы не сравнивали каждый $i$-й элемент с первым, присваивать начальное значение максимуму будем в цикле по $i$. Аналогично с минимумом, но начальное значение минимума будет равно первому элементу $i$-го столбца.

Ссылки

Условие задачи
Код решения

e-olymp 2470. Проверка на неориентированность

by

0

Задача

По заданной квадратной матрице [latex]n×n[/latex] из нулей и единиц определить, может ли она быть матрицей смежности простого неориентированного графа. Напомним, что простой граф не содержит петли и мультиребра.

Входные данные

В первой строке задано число [latex](1 \leqslant n \leqslant 100).[/latex] Затем идут [latex]n[/latex] строк по [latex]n[/latex] элементов в каждой — описание матрицы смежности.

Выходные данные

Вывести [latex]YES,[/latex] если граф простой неориентированный, и [latex]NO[/latex] в противном случае.

Тесты

# Входные данные Выходные данные
1 3
0 1 1
1 0 1
1 1 0		 YES
2 3
0 1 1
1 0 1
0 1 0		 NO
3 3
0 1 0
1 1 1
0 1 0		 NO
4 4
1 1 1 1
1 0 1 1
1 1 0 1		 NO
5 4
0 0 1 1
0 0 0 1
1 0 0 0
1 1 0 0		 YES

Код программы

Решение задачи

Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: [latex]a[i][j] = a[j][i].[/latex] Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия. Для этого воспользуемся обычными двумерными массивами. Затем проверим является ли граф простым. Если [latex]a[i][j] = 1,[/latex] то граф содержит петлю, следовательно простым не является. Затем проверим матрицу на симметричность, т. е. выполняется ли условие [latex]a[i][j] = a[j][i].[/latex] Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, то это означает, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится [latex]«NO».[/latex] Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим [latex]«YES».[/latex]

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 2667. Змейка

by

0

Задача

Напишите программу, которая выводит элемент из строки $x$ и столбца $y$ матрицы размера $n \times m$, которая заполнена змейкой:

Входные данные

Даны натуральные числа $n$, $m$, $x$, $y$ $ \left ( 1 \leq x \leq n \leq 50, 1 \leq y \leq m \leq 50 \right )$. Здесь $n$ — количество строк матрицы, $m$ — количество столбцов матрицы, $x$ и $y$ — номера строки и столбца искомого элемента.

Выходные данные

Вывести элемент из строки $x$ и столбца $y.$

Тесты

Входные данные Выходные данные
$5 \ 2 \ 3 \ 1$ $4$
$6 \ 3 \ 4 \ 3$ $9$
$10 \ 5 \ 10 \ 2$ $48$

Код программы

Решение

Читаем входные данные и объявляем массив $n$ на $m$, $num = 0$ — число элемента в этом массиве, далее будем заполнять его в цикле. Делаем перебор строк, для каждой строки есть число $j$ — номер элемента (в текущей строке), с которого мы записываем числа и число $dir$ — направление, в которое мы эти числа записываем (оно у нас 1 или -1). Если строка четная, то начинаем движение слева направо, если нечетная, то справа налево. Далее перебираем каждый элемент строки и записываем ему свой номер. В ответе выводим выбранный элемент.

Ссылки

Условие задачи на e-olymp

Код решения задачи ideone

e-olymp 8530. Печать матрицы

by

0

Задача

Задана матрица $n \times n$ — назовем ее $[1 \ldots n] \times [1 \ldots n]$ массивом. Для заданных $r$ и $c$ следует вывести $[1 \ldots r] \times [1 \ldots c]$ массив ($r$ строк и $c$ столбцов исходного массива).

Входные данные

Первая строка содержит число $n \space (1 \leq n \leq 100)$. Следующие строки содержат матрицу $n \times n$. Последняя строка содержит два числа $r$ и $c \space (1 \leq r, c \leq n)$. Все числа в матрице не превышают по модулю $100$.

Выходные данные

Выведите матрицу $r \times c$.

Тесты

Входные данные Выходные данные
4
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7
3 2 		1 2
5 6
9 1
5
18 25 34 44 -43
54 65 75 85 -32
95 15 25 35 -3
-4 15 -6 37 0
44 43 23 3 -12
4 3 		18 25 34
54 65 75
95 15 25
-4 15 -6
6
30 -10 30 -69 -84 75
-3 -39 60 15 75 -74
36 68 35 23 25 -44
16 42 83 15 59 -18
71 43 35 -81 -38 51
37 -49 55 26 6 33
4 5		 30 -10 30 -69 -84
-3 -39 60 15 75
36 68 35 23 25
16 42 83 15 59

Код программы

Решение

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

  • первый цикл ($17$ строка кода) будет отвечать за количество выводимых строк матрицы — по условию, нужно вывести первые $r$ строк;
  • второй цикл ($18$ строка кода) будет отвечать за количество выводимых столбцов матрицы — по условию, нужно вывести первые $c$ столбцов.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone
Решение этой же задачи на C++

Класс для хранения матриц

by

2

Задача

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

Тесты

№ Операция Входная матрица А Входная   матрица В Результат
 1 Транспони-рования 33 34 12
33 19 10
12 14 17
84 24 51
43 71 21		 — 33 33 12 84 43
34 19 14 24 71
12 10 17 51 21
 2 Сложения -1   1   -1
1   -1   1
-1   1   -1		 1   -1   1
-1    1  -1
1   -1   1		 0   0   0
0   0   0
0   0   0
 3 Вычитания -1   1   -1
1   -1   1
-1   1   -1		 1   -1   1
-1    1  -1
1   -1   1		 -2   2   -2
2   -2   2
-2   2   -2
 4 Умножения 33  34  12
33  19  10
12  14  17
84  24  51
43  71  21		 10  11  34  55
33  45  17  81
45  63  12  16		 1992 2649 1844 4761
1407 1848 1565 3514
1347  1833 850 2066
3927 5217 3876 7380
3718 4991 2921 8452

Решение

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Класс  Matrix  имеет следующие поля:  n, m  — размеры основной матрицы, и сама матрица  mainMatrix , представлена в виде двумерного массива целочисленного типа. Также данный класс имеет два конструктора: первый из которых принимает как параметры размеры создаваемой матрицы public Matrix(int n, int m) , второй же принимает как параметр двумерный массив(матрицу)  public Matrix(int [][] paramMatrix) .

Данный класс имеет следующие методы:

  1. public int getElement(int n, int m)  — метод для получения элемента матрицы по индексам;
  2. public void setElement(int n, int m, int value)  — метод задания элемента по индексам;
  3. public int getVerticalLength() — метод получения количества строк в матрице;
  4. public int getHorizontalLength()  — метод получения количества столбцов в матрице;
  5. public void fillRandomValues()  — метод заполнения матрицы рандомными значениями;
  6. public void displayMatrix()  — метод вывода матрицы;
  7. public static int[][] transpone(int[][] paramMatrix)  — метод транспонирования матрицы, с двумерным массивом как параметр;
  8. public static Matrix transpone(Matrix paramMatrix)  — метод транспонирования матрицы, с объектом класса  Matrix , как параметр;
  9. public static Matrix add(Matrix first, Matrix second)  — метод нахождения суммы двух матриц;
  10. public static Matrix subtract (Matrix first, Matrix second)  — метод вычитания одной матрицы из другой;
  11. public static Matrix multiply (Matrix first, Matrix second)  — метод произведения двух матриц.

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

Ю 4.9

by

0

Задача

В матрице [latex]A(n, m) [/latex] все ненулевые элементы заменить обратными по величине и противоположными по знаку.

Тесты

№       n        m  Входная матрица              Выходная матрица
     1                     3                         3           6   -2    -1                     0    0     4                    11   2    -3         -0.167     0.500      1.000                  0.000     0.000     -0.250                 -0.091    -0.500      0.333
     2                     3                         4       -3    -9    15   12        -31   -8     2     8           -1     2    -6    -8      0.333   0.111    -0.067   -0.083      0.032   0.125    -0.500   -0.125      1.000  -0.500     0.167    0.125
     3                    4                         3             1   1   1                       1   1   1                       1   1   1                       1   1   1            -1.000  -1.000   -1.000                    -1.000  -1.000   -1.000                    -1.000  -1.000   -1.000                    -1.000  -1.000   -1.000

Решение

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Объявляем и инициализируем переменные n  и m , которые являются размерами нашей матрицы [latex]A[/latex]. Объявляем нашу матрицу и создаем экземпляр с размерами [latex]n[/latex] x [latex]m[/latex]. Далее создаем цикл по i  от 0 до [latex]n-1[/latex] в котором создаем вложенный цикл по  j  от 0 до [latex]m-1[/latex], и в нем поэлементно вводим значения матрицы. В следующем цикле снова создаем вложенный, в котором мы проходим по каждому элементу матрицы и проверяем не равен ли он нулю  if(A[i][j] != 0) . Если условие выполняется, то мы заменяем элемент на обратный и меняем знак. В последнем цикле выводим полученную матрицу, элементы которой будут выводится с точностью до трех символов после запятой.

A410e

by

0

Дана целочисленная матрица [latex]\begin{bmatrix}a_{i,j}\end{bmatrix},i,j=1,..,n[/latex].Получить [latex]b_{1},..,b_{n}[/latex],где [latex]b_{i}[/latex] — это:

[latex]\underset{1\leq j\leq n}{\max a_{ij}}\ * \underset{1\leq j\leq n}{\min a_{ji}}[/latex]

Исходя из задачи ясно, что из данной матрицы надо взять максимальный элемент [latex]i[/latex]-й строки и умножить его на минимальный элемент [latex]i[/latex] -го столбца. Так например, если нам дана матрица 2-го порядка [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] то [latex]b_{1} = 2[/latex], [latex]b_{2} = 4[/latex].

 

Тесты

Матрица порядка [latex]n[/latex], где [latex]n[/latex]: [latex]a[i][j][/latex] Результат
2 [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] 2 4
3 [latex]\begin{Vmatrix}1&2&3\\4&1&-6\\1&-2&-1\end{Vmatrix}[/latex] 3 -8 -6

Решение

Для нахождения максимума  [latex]a_{ij}[/latex], введем переменную и будем придавать ей начальное значение 1-го элемента [latex]i[/latex]-й строки. Дабы при расчете максимума проходя по элементам строки мы не сравнивали каждый [latex]i[/latex]-й элемент с 1-м, придавать начальное значение максимуму мы будем в цикле по [latex]i[/latex]. Аналогично с минимумом [latex]a_{ij}[/latex], одно единственное но, начальное значение минимума будет равно первому элементу [latex]i[/latex]-го столбца.

http://ideone.com

A401. Удаление строки и столбца из матрицы

by

1

Условие задачи:

Дана действительная квадратная матрица порядка n, натуральные числа  i, j \left(1\leq i\leq n, 1\leq j\leq n \right). Из матрицы удалить  i-строку и j-столбец.

Тесты:

n Матрица. i j Полученная Матрица
4 10 10 20 20
30 30 40 40
50 50 60 60
70 70 80 80		 1 1 30 40 40
50 60 60
70 80 80
5 1.1 1.1 1.1 1.1 1.1
2.2 2.2 2.2 2.2 2.2
3.3 3.3 3.3 3.3 3.3
4.4 4.4 4.4 4.4 4.4
5.5 5.5 5.5 5.5 5.5		 2 3 1.1 1.1 1.1 1.1
3.3 3.3 3.3 3.3
4.4 4.4 4.4 4.4
5.5 5.5 5.5 5.5
3 2 -2 2
3 -3 3
5 -5 5		 1 3 3 -3
4 -4

Код программы:

Алгоритм:

  1. Пользователь вводит  порядок матрицы n и её элементы.Затем он вводит  i-строку и j-столбец, которые он хочет удалить.
  2. В первом цикле создаем переменную — индекс строки нового массива со значением 0. Проверяем, если указанный нам номер строки совпадает с текущим, то мы переходим на следующую по номеру строку, так как эта строка нам больше не понадобится.
  3. Если не совпадает, во внутреннем цикле создаем переменную — номер столбца нового массива со значением 0. Проверяем или совпадает индекс текущего столбца с индексом указанным нам. Если да, то увеличиваем на 1 индекс нашего столбца ( этим мы «обращаем свое внимание» на следующий столбик, игнорируя этот ).
  4. После этого присваиваем значения текущего индекса строки и столбца, получившимся в ходе циклов,значениям индексов нового массива. С помощью внутреннего цикла заполняем данную строку до конца.
  5. После заполнения увеличиваем на 1 индексы данного и нового массива ( переходим на следующую строку матрицы ). Возвращаемся к условию внешнего цикла и продолжаем заполнять новый массив.
  6. Данному массиву присваиваем новый. В конце выводим полученный массив.

Работающая версия программы на ideone.com

А404

by

0

Условие задачи

Даны натуральные числа [latex]i[/latex], [latex]j[/latex], действительная матрица размера [latex]18 / 24[/latex], [latex]1\leq i\leq j\leq 24[/latex].
Поменять местами в матрице [latex]i[/latex]-й и [latex]j[/latex]-й столбцы.

Входные данные

Вводим матрицу [latex]M[/latex]– строк, [latex]N[/latex]– столбцов. В следующей строке вписываем номера столбцов которые хотим поменять.

Выходные данные

Матрица, в которой поменялись местами столбцы.

Тесты

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

3 6

0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Код программы

www.ideone.com

Решение

    Для задания размера матрицы объявлены константы M и N. В вложенном цикле вводим значения матрицы. Вводим номера столбцов, которые мы хотим переставить. В цикле переставляем местами элементы указанных столбцов. Затем выводим матрицу.