e-olymp 8524. Сумма положительных в матрице

Задача взята с сайта e-olymp

Условие

Задана матрица размера [latex]n\times n[/latex]. Найдите сумму ее положительных элементов.

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

Первая строка содержит число [latex]n[/latex] [latex]\left(1 \leq n \leq 100 \right)[/latex]. Следующие строки содержат матрицу [latex]n\times n[/latex]. Элементы матрицы по модулю не больше [latex]100[/latex].

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

Выведите сумму положительных элементов матрицы.

Тесты

Inputs Outputs
1 3
4 -2 5
1 -4 -12
0 1 -3
11
2 4
-4 -2 -5 -7
-1-14 -4 -12
-12 -1 -3 -53
0
3 3
0 0 0
0 1 0
0 0 0
1
4 0 0
5 5
89 76 54 32 33
46 57 89 40 32
12 45 63 78 65
13 76 54 89 67
13 67 89 90 43
1412

Код

Решение

В условии сказано, что задана матрица размера [latex]n\times n[/latex], тогда вводов тоже будет, соответственно, [latex]n\cdot n[/latex]. В цикле ввода используется условный оператор для проверки на то, положительно число или нет.

Ссылки

e-olymp 1482. Умножение матриц

Задача

Пусть даны две прямоугольные матрицы $A$ и $B$ размерности $m \times n$ и $n \times q$ соответственно:
$$A = \begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{bmatrix} \; , \; B = \begin{bmatrix} b_{11} & b_{12} & \ldots & b_{1q} \\ b_{21} & b_{22} & \ldots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \ldots & b_{nq} \end{bmatrix} .$$
Тогда матрица $C$ размерностью $m \times q$ называется их произведением:
$$C = \begin{bmatrix} c_{11} & c_{12} & \ldots & c_{1q} \\ c_{21} & c_{22} & \ldots & c_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \ldots & c_{mq} \end{bmatrix} ,$$
где: $$c_{i,j} = \sum_{r=1}^{n} a_{i,r}b_{r,j} \; \left(i = 1, 2, \ldots m; j = 1, 2, \ldots q\right).$$
Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована.

Задано две матрицы $A$ и $B$. Найти их произведение.

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

В первой строке задано $2$ натуральных числа $n_a$ и $m_a$ – размерность матрицы $A$. В последующих $n_a$ строках задано по $m_a$ чисел – элементы $a_{ij}$ матрицы $A$. В $\left(n_a + 2\right)$-й строке задано $2$ натуральных числа $n_b$ и $m_b$ – размерность матрицы $B$. В последующих $n_b$ строках задано по $m_b$ чисел – элементы $b_{ij}$ матрицы $B$. Размерность матриц не превышает $100 \times 100$, все элементы матриц целые числа, не превышающие по модулю $100$.

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

В первой строке вывести размерность итоговой матрицы $C$: $n_с$ и $m_c$. В последующих $n_с$ строках вывести через пробел по $m_c$ чисел – соответствующие элементы $c_{ij}$ матрицы $C$. Если умножать матрицы нельзя — в первой и единственной строке вывести число $\; -1$.

Тесты

Входные данные Выходные данные
2 3
1 3 4
5 -2 3
3 3
1 3 2
2 1 3
0 -1 1
2 3
7 2 15
1 10 7
3 3
1 5 3
2 6 1
7 -1 -3
3 2
3 6
-1 1
3 1
3 2
7 14
3 19
13 38
4 4
4 8 -18 16
3 7 14 -42
2 1 1 7
4 9 5 -2
4 4
1 0 0 0
0 1 0 0
0 0 1 0
4 4
4 8 -18 16
3 7 14 -42
2 1 1 7
4 9 5 -2
3 3
5 7 -1
8 9 3
0 -6 17
2 3
7 -15 1
8 8 2
-1
2 3
57 -49 31
89 11 -37
3 1
19
-19
0
2 1
2014
1482

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

 

Решение

Для начала, считываем данные матрицы $A$ из входного потока и записываем их в двумерный динамический массив. Далее, получив данные о размерности второй матрицы, мы можем определить, выполнима ли операция умножения, и если нет, то прервать выполнение программы. Если операция умножения данных матриц выполнима, то считываем и записываем данные второй матрицы, после чего, по приведённой выше формуле вычисляем произведение матриц $C = A \times B.$ Наконец, выводим полученную матрицу $C.$

Ссылки

Условие задачи на e-olymp
Код задачи на ideone
Умножение матриц на Wikipedia

e-olymp 5282. Седловые точки

Задача

Задана матрица [latex]K[/latex], содержащая [latex]n[/latex] строк и [latex]m[/latex] столбцов. Седловой точкой этой матрицы назовём элемент, который одновременно является минимумом в своей строке и максимумом в своём столбце.
Найдите количество седловых точек заданной матрицы.
Saddle point

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

Первая строка содержит целые числа [latex]n[/latex] и [latex]m[/latex]. [latex](1 ≤ n, m ≤ 750)[/latex]. Далее следуют [latex]n[/latex] строк по [latex]m[/latex] чисел в каждой. [latex]j[/latex]-ое число [latex]i[/latex]-ой строки равно [latex]k_{ij}[/latex]. Все [latex]k_{ij}[/latex] по модулю не превосходят [latex]1000[/latex].

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

Выведите количество седловых точек.

Тесты

# Входные данные Выходные данные
1 2 2
0 0
0 0
4
2 3 3
1 2 3
4 3 6
9 5 3
0
3 4 4
1 2 0 0
2 2 4 4
0 0 1 1
3 4 2 1
0
4 2 2
3 2
1 1
1

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

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

Для каждой строки, будем осуществлять два прохода. В первом найдем минимальное число, а во втором, если значение очередного элемента будет являться в ней минимумом, то проверим будет ли оно максимумом в своем столбце таким образом, что если элемент заранее созданного массива [latex]([/latex] в котором изначально лежат все [latex]Unknown ([/latex] заранее созданная константа равная [latex]1001[/latex][latex] ([/latex] так как по условию, числа которые мы вводим не больше чем [latex]1000 ) ) )[/latex] не равен [latex]Unknown[/latex], то просто сравним элемент массива с минимумом, иначе найдем максимум для данного столбца и положим его в массив, о котором шла речь ранее и сравним уже это число с минимумом строки. Если они совпадают, то это и есть седловая точка!

Ссылки

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

Код решения на ideone.com.

ML30. Объём параллелепипеда

Задача. Найти объём параллелепипеда три стороны которого образованы векторами [latex] \overrightarrow{a}=(a_x,a_y,a_z),[/latex] [latex]\overrightarrow{b}=(b_x,b_y,b_z)[/latex] и [latex]\overrightarrow{c}=(c_x,c_y,c_z).[/latex]

Входные данные: Координаты векторов [latex]\overrightarrow{a},[/latex] [latex] \overrightarrow{b},[/latex] [latex]\overrightarrow{c}. [/latex]

Выходные данные: Объём параллелепипеда.

Тесты

Входные данные Выходные  данные
0 0 1 0 1 0 1 0 0  1
0 0 0 1 0 0 0 0 1  0
1 0 0 0 0 1 0 0 1  0
2 5 3 4 1 0 -2 7 6  18
3 5 1 0 -7 2 6 -4 5  21

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

Решение

Для решения данной задачи можно составить матрицу и вывести из неё формулу для нахождения определителя:
[latex]\triangle = \begin{vmatrix}a_x & a_y & a_z \\ b_x & b_y & b_z \\ c_x & c_y & c_z\end{vmatrix} =[/latex] [latex] a_x \left(b_y c_z+c_y b_z\right)[/latex] [latex]-a_y \left(b_x c_z+c_x b_z\right)+[/latex] [latex]a_z\left(b_x c_y+c_x b_y\right).[/latex]

Модуль определителя матрицы равен объёму параллелепипеда.

Решение на ideone.

ML28. Объём тетраэдра

Задача

Найти объём тетраэдра три стороны которого образованы векторами [latex]\vec {a} = \left( x_a, y_a, z_a \right)[/latex], [latex]\vec {b} = \left( x_b, y_b, z_x \right)[/latex], [latex]\vec {c} = \left( x_c, y_c, z_c \right)[/latex].

Пояснительный рисунок

Пояснительный рисунок к ML28

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

Координаты векторов [latex]\vec {a}[/latex], [latex]\vec {b}[/latex], [latex]\vec {c}[/latex].

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

Объём тетраэдра.

Тесты

Входные данные Выходные данные
[latex]x_a[/latex] [latex]y_a[/latex] [latex]z_a[/latex] [latex]x_b[/latex] [latex]y_b[/latex] [latex]z_b[/latex] [latex]x_c[/latex] [latex]y_c[/latex] [latex]z_c[/latex] [latex]V[/latex]
0 0 1 0 1 0 1 0 0 0.166667
3 6 3 1 3 -2 2 2 2 3
0 0 0 1 3 -2 2 2 2 0

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

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

Так как тетраэдр построен на векторах [latex]\vec {a} = \left( x_a, y_a, z_a \right)[/latex], [latex]\vec {b} = \left( x_b, y_b, z_x \right)[/latex], [latex]\vec {c} = \left( x_c, y_c, z_c \right)[/latex], для данной задачи оптимальным решением будет использовать следующие формулы:

  1. [latex]V = \frac {|\Delta|} {6}[/latex], где [latex]V[/latex] — объём тетраэдра, а [latex]\Delta[/latex] — определитель матрицы.
  2. [latex]
    \Delta =
    \begin{vmatrix}
    x_a & y_a & z_a \\
    x_b & y_b & z_b \\
    x_c & y_c & z_c
    \end{vmatrix}
    = x_a \left(y_b z_c-z_b y_c \right)-x_b \left( y_a z_c-z_a y_c \right)+x_c \left( y_a z_b-z_a y_b \right)
    [/latex].

Итоги:

  • если значение определителя матрицы равно нулю, то либо некоторые из заданных векторов коллинеарны, либо нулевые, либо все они лежат в одной плоскости. Во всех этих случаях тетраэдр не может существовать, и программа выведет [latex]0[/latex];
  • если значение определителя не равно нулю, то программа вычислит объём тетраэдра. В случае, если определитель примет отрицательное значение, программа домножит значение объёма на [latex]-1[/latex], в результате чего оно станет положительным.

Ссылки

А406

Задача

С помощью [latex]x_{ij}, i=1,2; j=1,\ldots,n.[/latex] — действительной матрицы на плоскости задано n точек так, что [latex]x_{1j}, x_{2j}[/latex] — координаты [latex]j[/latex] — точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.

Тест

n Матрица [latex]x_{ij}, i=1,2.[/latex] Длина наибольшего отрезка  Комментарий
3  

2 8 4

9 1 5

10 Пройдено
4  

6 14 2 1

9 3 8 0

13.3417 Пройдено
5  

1 8 4 3 7

2 9 5 0 11

11.7047 Пройдено

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

Ход решения:

  1. Вводим матрицу построчно (не очень удобно).
  2. Находим длину наибольшего отрезка.
    С помощью вложенных циклов мы находим длины всех отрезков по формуле
    [latex] AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}). [/latex]
  3. По алгоритму нахождения максимума находим длину наибольшего отрезка.
  4. Выводим матрицу.
  5. Выводим длину наибольшего отрезка.
    Ссылка на код

Ю4.12

Задача: Все ненулевые элементы матрицы [latex]D(k,l)[/latex] расположить в начале массива [latex]E(k \times l)[/latex] и подсчитать их количество.

K L Матрица D Ненулевые элементы матрицы E Количество ненулевых элементов
2 3 2 7 0
1 4 9
 2 7 1 4 9  5
3 4 6 7 4 2
9 0 1 3
0 8 0 19
 6 7 4 2 9 1 3 8 19  9
4 2  8 9
0 1
5 2
7 26
 8 9 1 5 2 7 26 8

Заполняем матрицу с клавиатуры посредством циклов.
Выводим ненулевые элементы.
Выводим их количество.
Выводим матрицу D.

Ссылка на код

А705

Задача:
Даны квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex]. Получить матрицу [latex]A(B-E)+C[/latex], где [latex]E[/latex] — единичная матрица порядка [latex]n[/latex], а элементы матрицы [latex]C[/latex] вычисляются по формуле:[latex]C_{ij}=\frac{1}{i+j}\;\;\;\;(i,j=1,2,\ldots,n)[/latex].

Тесты
К сожалению я не разместила здесь тесты к задаче.

Решение
Реализуем хранение матрицы в виде двумерного массива. Операции сложения и вычитания матриц выполняются поэлементно. Умножение требует наличия у левого сомножителя такого же числа столбцов, как и число строк у правого сомножителя. Поэлементно умножаем каждую строку первой матрицы на каждый столбец второй накапливая сумму значений в элементах результирующей матрицы.

Код C++

Код C++ на Ideone: A705

Код Java

Код Java на Ideone: A705

Тесты:

№ теста Размерность матрицы n Матрица A Матрица В Ответ
1 2 3 4
2 1
2 1
9 0
  39.50  -0.67

11.33  1.25

2 4 5 5 5 5
0 0 8 7
2 3 4 7
8 6 1 2
5 7 3 4
9 8 3 4
2 3 4 5
6 6 6 6
  105.50  115.33  75.25  90.20

58.33  66.25  66.20  75.17

85.25  89.20  69.17  75.14

100.20  113.17  57.14  71.12

3 3 0 0 0

0 0 0

0 0 0

1 0 0

0 1 0

0 0 1

 0.5 0.33 0.25

0.33 0.25 0.20

0.25 0.20 0.17

 

А700в

Задача. Дана квадратная матрица А порядка n. Получить матрицу AB; элементы матрицы B вычисляются по формуле:

[latex]b_{ij}=\left\{\begin{matrix}\frac{1}{i+j-1}&,if\: i<j\\ 0&,if\: i=j\\-\frac{1}{i+j-1}&other\: case\end{matrix}\right.[/latex]

 

[latex](i,j=1,\cdots, n)[/latex]

 

Тесты:

Размер матрицы Входные данные Результат Комментарий
n=2 [latex]\begin{pmatrix}1&7\\3&2\end{pmatrix}[/latex] [latex]\begin{pmatrix}-3,5&0,5\\-1&1,5\end{pmatrix}[/latex] Пройден
n=3 [latex]\begin{pmatrix}1&2&3\\7&6&5\\4&8&9\end{pmatrix}[/latex] [latex]\begin{pmatrix}-2&-0,25&0,83333\\-4,66667&2,25&3,83333\\-7&-0,25&3,333\end{pmatrix}[/latex] Пройден

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

После ввода матрицы A, мы должны найти элементы матрицы B. Из условия задачи:  [latex]b_{ij}=\left\{\begin{matrix}\frac{1}{i+j-1}&,if\: i<j\\ 0&,if\: i=j\\-\frac{1}{i+j-1}&other\: case\end{matrix}\right.[/latex] , при [latex](i,j=1,\cdots, n)[/latex].

Для нахождения [latex]b_{ij}[/latex] используется условный оператор if в цикле for. Матрица C — результат умножения матрицы A на матрицу B, которое также производим в цикле for.

Код программы можно посмотреть здесь.

Решение на Java:

Ссылка на решение.

А719б

Условие

Симметричные квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex] заданы последовательностями из [latex]\frac{n(n+1)}{2}[/latex] чисел аналогично правым треугольным матрицам. Получить в аналогичном виде матрицу [latex]A^{2}-B^{2}[/latex].


Решение

Безусловно, по входным данным можно восстановить матрицы, тривиальным образом их перемножить и вывести результат в заданном виде. Как пример плохого стиля программирования: наивный алгоритм приводит к почти двукратному перерасходу потребляемой памяти и существенно уступает в производительности. Существует другое решение, прийти к которому можно путем последовательного приспособления стандартных матричных операций к формату входных данных.

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


Замечание 1

Подпространство симметричных матриц незамкнуто относительно умножения: произведением двух симметричных матриц может быть несимметричная матрица.

Пример

[latex] \left(\begin{array}{ccc} 1 & 1 & 3 \\ 1 & 4 & 5 \\ 3 & 5 & 0\end{array} \right) \cdot \left( \begin{array}{ccc} 4 & 0 & 0 \\ 0 & 4 & 3 \\ 0 & 3 & 2 \end{array} \right) = \left( \begin{array}{ccc} 4 & 13 & 9 \\ 4 & 31 & 22 \\ 12 & 20 & 15 \end{array} \right)[/latex]


Замечание 2

Степень симметрической матрицы также является симметрической матрицей. Доказательство основано на представлении матрицы как представления линейного оператора и на свойствах эрмитовых операторов.


Во всех дальнейших выкладках подразумевается, что матрица представлена линейным массивом из [latex]\frac{n(n+1)}{2}[/latex] элементов.

Для начала, заметим, что элемент [latex]c_{i,j}[/latex] матрицы [latex]C=A^{2}[/latex], равен скалярному произведению (как векторов в стандартном базисе) [latex]i[/latex]-ой строки матрицы [latex]A[/latex] на [latex]j[/latex]-ую её строку (в силу того, что в симметричной матрице [latex]j[/latex]-ая строка совпадает с [latex]j[/latex]-м столбцом). Следовательно, для возведения в степень симметричной матрицы необходимо и достаточно реализовать операцию скалярного перемножения двух её строк.

Тогда следует понять, как по данному представлению матрицы получить её [latex]i[/latex]-ую строку. Для удобства, выпишем имеющиеся элементы в виде полной матрицы. Заметим, что первым элементом [latex]i[/latex]-ой строки будет [latex]i[/latex]-ый элемент первой строки, и обобщим это наблюдение. Обозначим позицию текущего интересующего нас элемента [latex]i[/latex]-ой строки как [latex]j[/latex]. Если [latex]j < i[/latex], то следует выбрать [latex]i[/latex]-ый элемент [latex]j[/latex]-ой строки, иначе следует выбрать все элементы [latex]j[/latex]-ой строки, лежащие правее данного. Графически можно интерпретировать алгоритм таким образом: начиная с [latex]i[/latex]-го элемента первой строки, спускаться вертикально вниз по матрице до тех пор, пока не будет достигнута [latex]i[/latex]-ая строка, далее — двигаться вправо до конца строки. Наглядность алгоритма позволяет легко воплотить его программно.
Следует только пронаблюдать, как изменяются расстояния между элементами, лежащими один под другим, при движении вниз по строкам матрицы, что позволит легко перенести алгоритм на линейное представление верхней треугольной матрицы. Предлагаем читателю самому проделать это несложное, но наглядное упражнение, для лучшего понимания алгоритма.

Теперь можно перейти непосредственно к реализации.


Тесты

[latex]n[/latex] [latex]A[/latex] [latex]B[/latex] [latex]A^{2}-B^{2}[/latex]
2 1 2 5 7 4 8 -60 -48 -51
4 1 7 3 -2 3 1 9 2 8 11 4 5 11 -3 4 -7 22 1 4 0 -108 116 -8 -79 -434 -10 75 -109 290 -239

Реализация

ideone: http://ideone.com/Dyte8l


Тесты

Детали реализации

Задачи раздела носят обучающий характер, так что при реализации были произведены определенные обобщения, что делает решение более универсальным.

  • Формулировка задачи не оговаривает тип элементов матрицы, так что класс [latex]symmetric\_matrix[/latex] является шаблоном, пригодным для типов данных, поддерживающих операции сложения, вычитания и умножения (соответствующие операторы определены внутри класса).
  • Алгоритм бинарного возведения матрицы в степень полезен при решении более широкого круга задач, в связи с чем также реализован. При необходимости, программа легко обобщается на большие степени матрицы.
  • Предусмотрены три типа конструкторов: конструктор по умолчанию и два параметрических конструктора, один из которых позволяет заполнить матрицу некоторым наперед заданным значением.
  • Для удобства работы с заданным представлением данных, добавлен синтаксический сахар: перегружен оператор [latex][][/latex], осуществляющий доступ к заданному элементу матрицы в линейном её представлении.

А717б

Условие

Две правые треугольные матрицы [latex] A [/latex] и [latex] B [/latex] порядка [latex] n [/latex] заданы в виде последовательности [latex] \frac{\left( n + 1 \right) n}{2}[/latex] чисел: сначала идёт [latex] n [/latex] элементов первой строки, затем [latex] n-1 [/latex] элемент второй строки, и т.д. (из последней, [latex] n [/latex] -ой строки берётся только [latex] n [/latex] -ый элемент). Нужно получить в аналогичном виде матрицу

б) [latex] A \left( I + B^{2} \right) [/latex], где [latex] I [/latex] — единичная матрица порядка [latex] n [/latex]

Тест

[latex] \begin{bmatrix} 2 & 2 & 2 \\ 0 & 0 & 3 \\ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix} = \begin{bmatrix} 4 & 54 & 236 \\
0 & 0 & 111 \\
0 & 0 & 37 \end{bmatrix} [/latex]

Решение

Создадим класс для работы с треугольными матрицами указанного вида и снабдим его основными методами, необходимыми для решения задачи.

У нас будут конструктор матрицы из стандартного потока ввода, конструктор скалярной матрицы, а также будут перегружены операторы сложения, умножения и присваивания.

Код на С++

Ideone (C++)

 

Код на Java

Ideone (Java)

A711a

Задача: Дана матрица [latex]A [/latex] размера [latex]m\times m [/latex]. Получить матрицу  [latex]AA^{*} [/latex] (ее размер [latex]m\times m [/latex]).

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

4
1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6

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

30 70 20 50
70 174 68 122
20 68 86 44
50 122 44 86

Решение:

Ссылка на ideone С++: http://ideone.com/iXjoLZ

Ссылка на ideone Java: http://ideone.com/u96MDY

 

Вводим матрицу [latex]A[i][j] [/latex] и матрицу [latex]B[j][i] [/latex] в цикле по [latex] i,j[/latex] от одного до [latex] n[/latex]. Умножаем матрицу  [latex] A[/latex] на [latex]A^{*} [/latex].

 

А714

Задача

Комплексная матрица [latex]Z[/latex] представляется парой [latex]X[/latex], [latex]Y[/latex] действительных матриц так, что [latex]Z=X+iY[/latex]. Даны действительные квадратные матрицы [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] и [latex]D[/latex] порядка [latex]m[/latex]. Найти произведение двух комплексных матриц [latex]A+iB[/latex] и [latex]C+iD[/latex], т. е. найти действительные квадратные матрицы [latex]X[/latex] и [latex]Y[/latex] порядка [latex]m[/latex] такие, что [latex]X+iY=(A+iB)(C+iD)[/latex].

Пример

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

9 5 4 8 5 2 6 1 3

1 4 6 5 3 1 9 8 7

4 2 8 3 9 5 1 2 7

5 6 7 4 1 9 3 8 2

X:

16 13 70

9 24 39

-68 -91 -75

 

Y:

99 141 186

96 108 167

110 165 218

 

 

Решение

 

 

 

 

[latex]X+iY=(A+iB)(C+iD)=(AC-BD)+i(AD+BC)[/latex], т. е. [latex]X=AC-BD[/latex], [latex]Y=AD+BC[/latex].

Код на ideone.

A708

Задача

Даны квадратная матрица [latex]A[/latex] порядка [latex]m[/latex], натуральное число [latex]n[/latex]. Получить матрицу [latex]E+A+A^2+A^3+\dots+A^n,[/latex] где [latex]E[/latex] — единичная матрица порядка [latex]m[/latex].

Тесты

m, n матрица А результат
3 3 3 2 1

5 7 3

9 7 3

359 358 158

1028 1047 460

1156 1162 513

2 2 6 7

12 54

127 427

732 3055

Код на языке С++:

Ссылка на программу:http://ideone.com/3B9ti7

Код на языке Java:

Ссылка на программу: http://ideone.com/hOFldD

Решение:

Заводим четыре матрицы: исходную, вспомогательную, матрицу в степени [latex]n[/latex] и результирующую;  обнуляем все матрицы, тем самым очищаем память. Дальше возводим матрицу в степень [latex]n[/latex],  добавляем к результирующей и заменяем вспомогательную матрицу. В завершении мы прибавим единичную матрицу к ответы и выведем его.

А706 Алгоритм быстрого возведения в степень

Степень Входная матрица Результирующая матрица
2
0 1
2 3
2 3
6 11
3
0 1
2 3
6 11
22 39

Пусть даны квадратная матрица [latex]A[/latex] порядка [latex]m[/latex] и натуральное число [latex]n[/latex]; требуется найти [latex]A^{n}[/latex]. Алгоритм, основанный на непосредственной применении формулы [latex]A^{n} = A*A*A…*A [/latex]([latex]n[/latex] сомножителей), слишком разорителен. Например, [latex]A^{4}[/latex] экономичнее вычислять как [latex]A^{2^{2}}[/latex]. Идея одного достаточно экономичного алгоритма вычисления [latex]A^{n}[/latex] заключается в следующем: если  [latex]n = 2k[/latex], то [latex]A^{n} = (A^{2})^{k}[/latex]; если же [latex]n = 2k + 1[/latex], то [latex]A^{n} = (A^{2})^{k} * A[/latex]. Степень с показателем [latex]k[/latex] вычисляется с учетом этих же соображений. Итак, надо разделить [latex]n[/latex] на [latex]2[/latex] с остатком:[latex] n = 2k + l [/latex] [latex](0\le l\le 1[/latex]), потом это же проделать с [latex]k[/latex] и т.д. Эти действия приводят, как известно, к построению двоичной записи [latex]n[/latex]. Алгоритм, основанный на этой идее, состоит в том, что последовательно вычисляются [latex]A^{a_{0}}, A^{a_{1}*a_{0}}, …,A^{a_{l}*…*a_{0}}, a_{l}*…*a_{0}[/latex] — двоичная запись числа [latex]n[/latex]. Для этого вычисляется, цифра за цифрой, двоичная запись [latex]n[/latex] и, параллельно, степень за степенью,[latex]A^{(2^{0})}, A^{(2^{1})}, …[/latex] — каждая следующая степень получается из предыдущей возведением в квадрат. Подсчитывается произведение тех из вычисленных степеней, для которых соответствующая цифра двоичного представления равна 1. Например, запись [latex]9[/latex] в двоичной системе есть [latex]1001[/latex][latex](9 = 1*8 + 0*4 + 0*2 + 1)[/latex]; для вычисления [latex]A^{9}[/latex] достаточно найти [latex]A^{2},A^{4},A^{8},[/latex]([latex]3[/latex] умножения), а затем определить [latex]A*A^{8},[/latex] ([latex]1[/latex] умножение).

Преимущество этого алгоритма в сравнении с простейшим состоит в том, что простейший алгоритм требует числа умножений, растущего как линейная функция от [latex]n[/latex], а здесь число умножений грубо говоря, пропорционально количеству цифр числа [latex]n[/latex] или двоичному логарифму [latex]n[/latex]. Это преимущество весьма ощутимо при работе с матрицами (из-за трудоемкости каждого умножения), хотя, разумеется, этот алгоритм может быть использован и для вычисления степени любого числа.

Написать программу, реализующую предположенный алгоритм.

Суть алгоритма была описана в задании. Реализация была через свою структуру данных, такую как матрица. В ней мы определили умножение и присваивание, для удобства. Есть несколько конструкторов, но нужен по сути только самый первый, остальные для разыгравшейся фантазии. Инициализация при создании матрицы обязательна, поскольку может выдавать неправильный ответ в связи с забытым  в памяти мусором. Как перемножать матрицы можно узнать здесь. Нам понадобятся три матрицы, исходная, временная и матрица для ответа. Само двоичное представление удобно хранить в строке, поскольку идя по ней и находя [latex]1[/latex] мы можем домножить на  временную  матрицу матрицу ответ.

 

link.

e-olimp 4000. Обход в глубину

Задача e-olimp 4000

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

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

В первой строке содержится два целых числа [latex]n[/latex] и [latex]s[/latex]  [latex](1\leq s\leq n\leq 100)[/latex], где [latex]n[/latex] — количество вершин графа, а [latex]s[/latex] — выделенная вершина. В следующих [latex]n[/latex] строках записано по [latex]n[/latex] чисел — матрица смежности графа, в которой цифра «0» означает отсутствие ребра между вершинами, а цифра «1» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

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

Выведите одно число — искомое количество вершин.

Пример:

Входные данные Выходные данные
5 1 3
0 1 1 0 0
1 0 1 0 0
1 1 0 0 0
0 0 0 0 1
0 0 0 1 0

Решение

 

 

Вводим данные, затем в первом цикле проверяем строку [latex]s[/latex]и записываем в стек все вершины инцидентные данной. Так как в условии гарантируется наличие на главной диагонали нулей, то будем помечать проверенные вершины с помощью элемента расположенного на главной диагонали (то есть будем присваивать ему значение отличное от 0, к примеру 1). После будем проверять все строки в стеке до его опустошения, и увеличивать счётчик на единицу после удаления из стека не помеченной вершины.

Код на ideone.

Засчитанное решение.

 

 

А402б

Задача

Даны натуральное число  [latex] n \geq 2 [/latex], действительная квадратная матрица порядка  [latex] n [/latex]. Построить последовательность  [latex] b_{1}, \ldots, b_{n} [/latex]  из нулей и единиц, в которой  [latex] b_{i} = 1 [/latex]  тогда и только тогда, когда элементы  [latex] i [/latex]  строки образуют возрастающую или убывающую последовательность.

Тесты

Ввод Вывод
[latex] \begin{pmatrix} 1 & 2.5 & 3 & -5 & 2 \\ -7 & -4.5 & -2.8 & 0 & 1 \\ 8 & 3 & 0 & -2.9 & -4.62 \\ 8 & 3 & 3 & -2.9 & -4.62 \\ 1 & 2 & 3 & 3 & 4 \end{pmatrix} [/latex]  [latex] \begin{matrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \end{matrix}[/latex]

 

Код на С++

Ideone (C++)

Код на Java

Ideone (Java)

Решение

1) Считываем матрицу

2) Просматриваем по очереди строки матрицы. Фиксируем знак разности первых двух элементов строки и пробегаем строку, сравнивая знак соседних элементов со знаком первых двух. Если последовательность убывает/возрастает, знаки всех пар должны совпадать со знаком первой и никакие два подряд идущих элемента не должны совпадать.

 

А407

Задача:
Даны натуральные числа n и m, действительное число r, действительная матрица размера nxm. Получить значение [latex]{b}_{1}{r}^{n-1}+{b}_{2}{r}^{n-2}+\dots+{b}_{n}[/latex], где [latex]{b}_{k}[/latex] — первый по порядку положительный элемент в k-й строке матрицы [latex](k=1,\dots,n)[/latex]; если в k-строке нет положительных элементов, то [latex]{b}_{k}=0.5[/latex].

Тесты:

nxm r Матрица Результат Комментарий
2х2 2.5 [latex]\begin{pmatrix} -1 & 1 \\ 1 & 0 \end{pmatrix}[/latex]  3.5 Пройдено
 3×4  3.14 [latex]\begin{pmatrix}5.7 & 6.7 & -7.7 & 0.9\\-3.0 & 2.3 & -5.0 & -2.4\\6.7 & 3.5 & 0.0 & 4.4\end{pmatrix}[/latex]  70.1 Пройдено
 2×4  2.71 [latex]\begin{pmatrix}-9.0 &-8.8 &-7.3 & 7.5\\-6.3 &-9.7 & 6.8 &-0.5\end{pmatrix}[/latex]  27.1 Пройдено

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

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

Идея решения:
Считать n, m как целочисленные переменные. После этого считать r как переменную типа double. Следующим считать массив nxm созданный благодаря генератору матриц из случайных чисел заданного размера. Завести переменную [latex]sum = 0[/latex] для хранения результата. Проверять построчно каждый столбик на наличие положительного числа и прибавить первое положительное число в строке, умноженное на [latex]{r}^{n-i-1}[/latex], к результаты. В случает отсутствия положительного элемента в строке,  брать 0.5. В конце вывести результат.

A403a

Задача

Дана целочисленная квадратная матрица порядка [latex]15[/latex]. Выяснить, имеются ли в матрице ненулевые элементы, и если имеются, указать индекс одного из ненулевых элементов.

Тест

i, j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Результат
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 Index: 0 3
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 9 0 0 0 0 0 0 8 0 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7
12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
14 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 

i,j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Результат
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0    Ненулевых элементов нет
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Код на языке С++ :

 

Ссылка на программу: http://ideone.com/72Gn1G

Решение:

Задача довольно простая.Вводим квадратную матрицу [latex]z(n,n)[/latex] порядка 15. Далее в цикле описываем условие, что если:

то выводим индекс только одного такого элемента.То есть как только найдется ненулевой элемент, программа  выведет его индекс и прекратит работу. Если же такого элемента не найдется, то в ответе мы увидим, что ненулевых элементов нет.

Код на языке Java:

 

Ссылка на программу:http://ideone.com/SiTKYZ

А400

Задача: Дана действительная квадратная матрица порядка [latex]n[/latex]. Получить [latex]{ x }_{ 1 }{ x }_{ n }+{ x }_{ 2 }{ x }_{ n-1 }+ \dots +{x }_{ n }{ x }_{ 1 }[/latex] , где [latex]{x }_{ k }[/latex]  — наибольшее значение элементов [latex]k[/latex]-й строки данной матрицы.

n Числа Результат n Числа Результат
4 1 1 1 15 5 5 56 6 6 6

2 2 2 3

66 3  1.25 99 45 4.2 5.20.3 0 0.2 86.44
5  1 2 3 4 19 8 4 3 10 50 9 2 1

1 2 1 1 1

3 1 2 0 5

2576 5  0 0 0 0 05 9 10008 72 1777799 98 100 10 100

0 0 0 0 0

9.842 8 7 66 54

1000

Код программы на С++