A393a

Задача:

Даны натуральное число [latex]n[/latex], целочисленная квадратная матрица порядка [latex]n[/latex]. Получить [latex]{b}_{1}[/latex],…,[latex]{b}_{n},[/latex] где [latex]{b}_{i}[/latex] — это наименьшее из значений, элементов находящихся в начале [latex]i[/latex]-й строки матрицы до элемента, принадлежащего главной диагонали, включительно.

Тесты:

 
Вводимые данные Предполагаемый вывод Комментарий
4 4 3 2 1 4 3 2 1 Тест пройден
4 3 2 1
4 3 2 1
4 3 2 1
1 2 3 4 1 1 1 1 Тест пройден
1 2 3 4
1 2 3 4
1 2 3 4

Решение:

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

Код:

 

Версия программы на Ideone.com

Ссылка на источник

Ю4.32

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

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

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

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

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

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

Тесты

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

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

Решение

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

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

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

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

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

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

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

Ю 4.9

Задача

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

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

Условие
Получить квадратную матрицу порядка $latex \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 (1 ≤ [latex]n[/latex] ≤ 100). В следующих n строках записано по [latex]n[/latex] чисел — матрица смежности графа ([latex]j[/latex]-ое число в [latex]i[/latex]-ой строке соответствует весу ребра из вершины [latex]i[/latex] в вершину [latex]j[/latex]). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

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

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

Алгоритм

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

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

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

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

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

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

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

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

Код

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

A410e

Дана целочисленная матрица [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

A704

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

Тесты:

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

Код:

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

Код на 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