Ю4.32

Постановка задачи

Суммы по косой. Просуммировать элементы матрицы A(n,n) по каждой из линий, параллельных главной диагонали. Напечатать полученные суммы.

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

n — размерность матрицы (n\geq 1).
A — квадратная матрица.

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

Суммы элементов матрицы A по каждой из линий, параллельной главной диагонали.

Тесты

Входные данные Выходные данные
Размерность матрицы (n) Матрица A Суммы
1 2 \begin{pmatrix}  3 & 6\\  -7 & -5  \end{pmatrix} -7  -2  6
2 3 \begin{pmatrix}  1 & 2 & 3\\  4 & 5 & 6\\  7 & 8 & 9  \end{pmatrix} 7  12  15  8  3
3 4 \begin{pmatrix}  4 & 1 & -6 & 3\\  2 & 8 & 19 & 7\\  -8 & -11 & 3 & -13\\  0 & 2 & 16 & -9  \end{pmatrix} 0  -6  7  6  7  1  3

Посмотреть работу программы на примере третьего теста можно на сайте ideone.

Решение

Описание решения

Сначала объявляем переменную n — размерность матрицы A — и присваиваем ей значение, которое вводит пользователь. Если (n\geq 1) — продолжаем работу, иначе выводим сообщение об ошибке и завершаем работу программы.

Теперь, зная размерность матрицы, можем инициализировать 2 массива:

  1. Двумерный массив double[][] matrix = new double[n][n]; размерностью (n\times n), который будет содержать в себе значения элементов матрицы A;
  2. Массив double[] sum = new double [2*n - 1]; размерностью (2*n-1) для хранения сумм диагоналей. Такая размерность обусловлена следующей логикой: главная диагональ матрицы размерностью (n\times n) содержит n элементов. Побочная диагональ, находящаяся выше, содержит в себе уже (n-1) элементов и т.д., пока элементов в диагонали больше нуля. Становится ясно, что выше главной диагонали находится (n-1) побочных диагоналей, еще столько же ниже. Прибавляем еще главную диагональ к этому числу и выводим формулу количества диагоналей у матрицы, параллельных главной: 2(n-1)+1=2n-1.

Заполняем с помощью двух циклов for массив matrix из потока ввода, а затем в таких же циклах находим суммы элементов требуемых диагоналей ( sum[(j-i) + (n-1)] += matrix[i][j];).

Известно, что индексы i,j элементов главной диагонали матрицы всегда одинаковы. Аналогично можно заметить, что на побочных диагоналях индекс j отличается от индекса i на число — «расстояние» между главной диагональю и рассматриваемой побочной. К примеру, если рассматривать побочную диагональ, находящуюся выше через одну от главной («расстояние» между ними равно 2), то в таком случае j-i=2.

И если на главной диагонали разность индексов будет равна 0, на диагоналях выше эта разность будет числом положительным, а на диагоналях ниже — отрицательным, то при попытке обращения к элементу массива sum[j-i] мы неизбежно столкнемся с ошибкой, так как индекс массива не может быть числом отрицательным. Значит, чтобы избежать этого, нам надо прибавить к этому индексу некую константу, чтобы самая нижняя диагональ n-1 обладала индексом 0 в массиве sum. Отсюда и формула (j-i+n-1).

Ю 4.9

Задача

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

Тесты

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

А694а. Многомерные массивы

Условие
Получить квадратную матрицу порядка \begin{pmatrix}1 &0 &\cdots & 0 \\ 0 & 1 &\cdots &0 \\ \cdots &\cdots &\cdots \cdots & \cdots \\ 0 & 0 & \cdots & 1\end{pmatrix}

Тесты

n Матрица
3 1 0 0
0 1 0
0 0 1
4 1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
6 1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
Решение

  1. С помощью цикла заполняем главную диагональ единицами.
  2. Приравниваем элементы не равные единице к нулю.
  3. Вывод массива.

Iseone.com

А702а

Дана квадратная матрица порядка n.
Получить вектор Ab, где b-вектор, элементы которого вычисляются по формуле: {b}_{i}={\frac{1}{{i}^{2}+2}}, где i=1,2,\dots,n.

2
1 2
3 4
0.666667 1.66667
Пройдено
2
5 6
7 8
2.66667 3.66667
Пройдено

Исходный код:

Ссылка на Ideone

http://ideone.com/UAvHF4

e-olymp 974. Флойд-1

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

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

В первой строке записано количество вершин графа n (1n100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

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

Выведите n строк по n чисел — матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.

Алгоритм

(взято с Википедии)

Пусть вершины графа {\displaystyle G=(V,\;E),\;|V|=n} пронумерованы от 1 до  {\displaystyle n} и введено обозначение {\displaystyle d_{ij}^{k}} для длины кратчайшего пути от  {\displaystyle i} до {\displaystyle j}, который кроме самих вершин  {\displaystyle i,\;j} проходит только через вершины {\displaystyle 1\ldots k} . Очевидно, что {\displaystyle d_{ij}^{0}} — длина (вес) ребра {\displaystyle (i,\;j)}, если таковое существует (в противном случае его длина может быть обозначена как {\displaystyle \infty } ).

Существует два варианта значения  {\displaystyle d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n)} d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n):

Кратчайший путь между {\displaystyle i,\;j} не проходит через вершину  {\displaystyle k}, тогда {\displaystyle d_{ij}^{k}=d_{ij}^{k-1}} Существует более короткий путь между {\displaystyle i,\;j}, проходящий через {\displaystyle k}, тогда он сначала идёт от {\displaystyle i} до  {\displaystyle k} , а потом от  {\displaystyle k} до  {\displaystyle j} . В этом случае, очевидно, {\displaystyle d_{ij}^{k}=d_{ik}^{k-1}+d_{kj}^{k-1}}

Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.

Тогда рекуррентная формула для {\displaystyle d_{ij}^{k}} имеет вид:

{\displaystyle d_{ij}^{0}} — длина ребра  {\displaystyle (i,\;j);} (i,\;j); {\displaystyle d_{ij}^{k}=\min(d_{ij}^{k-1},\;d_{ik}^{k-1}+d_{kj}^{k-1}).}

Алгоритм Флойда-Уоршелла последовательно вычисляет все значения {\displaystyle d_{ij}^{k},} , {\displaystyle \forall i,\;j} для  {\displaystyle k} от 1 до  {\displaystyle n} . Полученные значения  {\displaystyle d_{ij}^{n}} являются длинами кратчайших путей между вершинами . {\displaystyle i,\;j.} .

Код

Условие на e-olymp.com
Решение на e-olymp.com
Код на ideone.com

A410e

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

\underset{1\leq j\leq n}{\max a_{ij}}\ * \underset{1\leq j\leq n}{\min a_{ji}}

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

 

Тесты

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

Решение

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

http://ideone.com

A704

Задача: Даны квадратные матрицы AB и C порядка n. Получить матрицу (A+B)C.

Тесты:

n A B C Output
3 1 2 3
4 5 6
7 8 9
0 1 0
0 0 0
0 0 0
1 0 0
0 1 0
0 0 1
1 3 3
4 5 6
7 8 9
2 4 6
12 7
3 2
1 1
7 3
2 8
65 85
107 103
3 3 4 1
1 2 1
5 6 7
1 3 1
2 4 5
6 5 1
1 1 0
5 8 1
2 3 2
43 66 11
45 69 18
82 123 27

Код:

Решение:
В первом цикле читаем матрицу A. Во втором цикле читаем матрицу B и сразу прибавляем ее к матрице A, получаем сумму матриц. В третьем цикле умножаем сумму матриц A и B на матрицу C и выводим результат.

Код на Ideone

A406

Задача

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

Тест

n Матрица x_{ij}, i=1,2. Длина наибольшего отрезка  Комментарий
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. Находим длину наибольшего отрезка.
    С помощью вложенных циклов мы находим длины всех отрезков по формуле
     AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}).
  3. По алгоритму нахождения максимума находим длину наибольшего отрезка.
  4. Выводим матрицу.
  5. Выводим длину наибольшего отрезка.
    Ссылка на код

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

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

Дана действительная квадратная матрица порядка 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

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

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

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

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

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

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

Тесты

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. В вложенном цикле вводим значения матрицы. Вводим номера столбцов, которые мы хотим переставить. В цикле переставляем местами элементы указанных столбцов. Затем выводим матрицу.