Tag Archives: матрицы

e-olymp 8950. Шаблон 5

by

3

Условие

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

* *
* * * *
* * * * *
* * * *
* *

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

Одно нечетное натуральное число [latex] n  (n>1)[/latex] .

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

Вывести изображение  [latex] n × n [/latex].

Тесты

Входные данные Выходные данные
3
* *
* * *
* *
5
* *
* * * *
* * * * *
* * * *
* *
7
* *
* * * *
* * * * * *
* * * * * * *
* * * * * *
* * * *
* *

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

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

Считываем значение [latex]n[/latex]. Создаём двумерный массив [latex] n * n [/latex] все элементы которого равны единице. Далее в цикле заполняем пространство между [latex] * [/latex] нулями. Так как позиции [latex] (i,0)[/latex] и [latex] (i,n) [/latex] всегда [latex] * [/latex], ко второму счётчику [latex]  j  [/latex] прибавляем единицу . На    середине   [latex] m = ( n — 1 ) / 2  [/latex] цикл прекращает заполнение нулями, потому в следующем цикле верхняя часть отображается в нижнюю. После чего происходит вывод двумерного массива заменяя [latex]  0=« » [/latex]  и [latex] 1=«*» [/latex].

Задача на ideone
Засчитанное решение на e-olymp
Код вe-olymp

eolymp-103. Симуляция процесса

by

1

Условие

Вам задан некоторый дискретный эволюционный процесс. В каждый момент времени состояние процесса описывается параметрами $x_{1},\dotsc, x_{n}$. В каждый момент времени эволюция описывается следующей системой линейных уравнений:

$
\begin{cases}
x^{i+1}_1 = a_{11}x^i_1 + \dotsc + a_{1n}x^i_n \\
\text{ }\\
\dotsc \\
\text{ } \\
x^{i+1}_n = a_{n1}x^i_1 + \dotsc + a_{nn}x^i_n
\end{cases}
$

Найдите состояние процесса в момент времени $M$. Каждый параметр должен быть посчитан по модулю 100007.

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

Первая строка ввода содержит количество тестов $T$ $(1 \le T \le 10)$. Первая строка каждого теста содержит $2$ числа: $N$ $(1 \le N \le 100)$ — количество параметров и $M$ $(0 \le M \le 10^9)$ момент времени. Далее следуют $N$ строк, каждая из которых содержит $N$ целых чисел, разделённых пробелами. $j$-е число в $i$-й строке — $a_{ij}$ $(0 \le a_{ij} \le 10^9)$. Далее следует одна строка, содержащая $N$ целых чисел. $j$-е число в этой строке — $x_j^0$ $(0 \le x_j^0 \le 10^9)$ .

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

Выведите $T$ строк вида «Case #$A$: $x^M_1, \dotsc, x^M_n$», где $A$ — номер теста (начиная с 1), $x^M_1, \dotsc, x^M_n$ – искомые параметры для данного теста.

Тесты

Входные данные Выходные данные
2
1 5
2
1
2 7
14 26
32 45
534 623 		Case #1: 32
Case #2: 62813 87846
2
2 39
1 1
1 0
1 0
2 24
3 1
1 0
1 0 		Case #1: 26994 41562
Case #2: 6860 73223

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

Решение

Пусть $V^M = [x^M_1, x^M_2, \dotsc, x^M_n]^T$, $V^0$ — исходное состояние процесса и $A = \| a_{ij} \|$, где $i = \overline{1,n}$, $j = \overline{1,n}$.

Можно заметить, что $\forall k:\text{ }V^{k+1} = AV^k$. Отсюда, в силу ассоциативности умножения матриц, заключаем, что $V^k = A^kV^0$.

Для возведения матрицы $A$ в степень $M$ воспользуемся алгоритмом быстрого возведения в степень, работающим по следующей схеме:
$x^n =\begin{cases}
1\text{, если $n$ = 0} \\
(x^2)^\frac{n}{2}\text{, если $n$ чётно} \\
x\cdot(x^2)^\frac{n-1}{2}\text{, если $n$ нечётно}
\end{cases}
$

Ссылки

Условие задачи на eolymp.com
Решение задачи на ideone.com

e-olymp 488. Обход матрицы змейкой

by

2

Задача

По данному числу [latex]n[/latex] заполните квадратную матрицу размером [latex]n*n[/latex] целыми числами от [latex]1[/latex] до [latex]n^{2}[/latex] следующим образом:

  • в левом верхнем углу находится число [latex]1[/latex];
  • далее числа располaгаются «змейкой», т.е. по возрастанию слева направо в нечётных строках, и справа налево — в чётных;

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

    Одно целое число [latex]n[/latex] [latex](1 \leqslant n \leqslant 100)[/latex].

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

    Вывести заполненную матрицу в виде [latex]n[/latex] строк по [latex]n[/latex] целых чисел в каждой.

    Тесты

    № Входные данные Выходные данные
    1 1 1
    2 3 1 2 3
    6 5 4
    7 8 9
    3 5

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

    1 2 3 4 5 6 7 8 9 10
    20 19 18 17 16 15 14 13 12 11
    21 22 23 24 25 26 27 28 29 30
    40 39 38 37 36 35 34 33 32 31
    41 42 43 44 45 46 47 48 49 50
    60 59 58 57 56 55 54 53 52 51
    61 62 63 64 65 66 67 68 69 70
    80 79 78 77 76 75 74 73 72 71
    81 82 83 84 85 86 87 88 89 90
    100 99 98 97 96 95 94 93 92 91

    Код

    Решение

    Создаем переменные flag_even для четных строк и flag_odd для нечетных. Они будут содержать значение элемента матрицы на каждом шаге алгоритма в соответствующих строках.
    Следует обратить внимание, что в условии указано, что числа идут слева направо в нечётных строках, и справа налево — в чётных, но в массивах нумерация идет с [latex]0[/latex] (четное число), поэтому в коде условие обратное.
    В циклах выполняем операции и сразу же печатаем элементы матрицы.

    Ссылки

  • Условие задачи на eolymp.com
  • Решение задачи на ideone.com
  • Засчитанное решение на eolymp.com

    • e-olimp 9536. Сумма матриц

    by

    0

    Задача

    Заданы две матрицы $A$ и $B$. Найдите их сумму $C$ = $A$ + $B$.

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

    Первая строка содержит размеры матриц $n$ и $m$ $(1 \leqslant n, m \leqslant 100)$. Следующие $n$ строк содержат по $m$ целых чисел и описывают матрицу $A$. Далее следует пустая строка, после чего в таком же формате задается матрица $B$.

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

    Выведите матрицу $С$: $n$ строк по $m$ целых чисел.

    Тесты

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

    3

    		 5
    1 5
    4 3 7 2 1

    3 2 2 1 6

    		 7 5 9 3 7
    2 2
    0 4
    2 3

    5 4
    1 6

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

    0 0 -3 -2
    -1 3 4 5
    5 6 1 2

    		 3 4 2 4
    0 5 7 9
    12 12 6 6
    3 3
    2 -128 47
    -365 5 56
    243 42 12

    678 43 76
    4 345 -23
    97 -453 18

    		 680 -85 123
    -361 350 33
    340 -411 30

    Код

    Решение

    Чтобы найти сумму двух матриц, необходимо сложить их соответствующие элементы.

    Ссылки

    Условие задачи на E-Olymp
    Код задачи на Ideone

    e-olymp 236. Триомино

    by

    0

    Триомино

    Сколькими способами можно замостить прямоугольник $2 × n$ триоминошками? Триомино — это геометрическая фигура, составленная из трех квадратов, соединяющихся между собой вдоль полного ребра. Есть только две возможных триоминошки:

    Например, замостить прямоугольник $2 × 3$ можно только тремя различными способами. Поскольку ответ может быть достаточно большим, искомое количество способов следует вычислять по модулю $10^6$.

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

    Первая строка содержит количество тестов $t$ ($1 \leqslant  t \leqslant  100$). Каждая из следующих $t$ строк содержит значение $n$ ($0 < n < 10^9$).

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

    Для каждого теста в отдельной строке выведите количество способов, которыми можно замостить прямоугольник $2 × n$. Результат следует выводить по модулю $10^6$.

    Тесты

    №

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

    Выходные данные
    1 3
    3
    4
    6    		 3
    0
    11
    2 4
    12
    15
    21
    9    		 153
    571
    7953
    41

    Код

    Решение

    Если n нацело не делится на $3$, то выводится ноль,в ином случае данная задача решается через рекуррентную формулу $a_n=4*a_{n-1}-a_{n-2}$. Но из-за слишком больших чисел мы не можем использовать данную формулу просто так, поэтому мы воспользуемся быстрым вычислением членов рекуррентной последовательности через матрицы. Надо умножать матрицу

    $\begin{pmatrix}
    4&-1 \\
    1&0 \\
    \end{pmatrix}$ в степени $p$(где $p$ равна двойке в степени номера единицы в двоичной записи числа ${{n}\over{3}}$) на матрицу $\begin{pmatrix}
    1\\
    1\\
    \end{pmatrix}$ каждый раз, когда встречается единица в двоичной записи числа ${{n}\over{3}}$. На выход подается первое число вектора $2 × 1$.

    Ссылки

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

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

    e-olymp 8651. Браслети (Bangles)

    by

    4

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

    Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з’єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. Знайшлося $N$ різних типів замків (позначимо їх номерами від $1$ до $N$) і $М$ типів деталей, які визначаються парою номерів замків (порядок несуттєвий). Напишіть програму, яка б підраховувала скільки існує різних наборів з чотирьох деталей для виготовлення браслетів фірмою «Magic & Stupidity».

    Вхідні дані

    Програма читає з першого рядка числа $N$ (кількість типів замків) та $M$ (кількість типів деталей). ($4 \leqslant N \leqslant 300$). У $M$ наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

    Вихідні дані

    Програма визначає кількість варіантів браслетів.

    Тести

    №
    		 Inputs Outputs
    1
    		 5 7
    1 3
    1 4
    2 4
    2 5
    3 4
    3 5
    4 5    		 2
    2
    		 4 4
    1 2
    2 3
    3 4
    1 4    		 1
    3
    		 5 5
    1 2
    2 3
    3 5
    1 4
    1 5    		 1

    Код

     

    Рішення

    Зробимо ізоморфний перехід в графи, а саме можна помітити, що визначивши типи запків як вершини матимемо зв’язки між типами, як існуючий елемент браслета, тобто пара $(1, 2)$ насправді задає зв’язок між першим і другим типом. Маэмо граф, залишилось знайти кількість простих циклів завдовшки у чотири ребра (чотири вершини).
    Построївши матрицю суміжності ми на справді побудували матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за один хід.
    Нехай за х ходів ми потрапили з вершини $i$ у вершину $k$ рівно $a$ способами, а з вершини $k$ у вершину $j$ рівно $b$ способами. Тоді за $2x$ ходів ми можемо потрапити з вершини $i$ у вершину $j$ через вершину $k$ рівно $ab$ способами, що насправді еквівалентно возведенню матриці суміжності у степінь, яка дорівнює кількості ходів
    Тепер за два перемноження отримаємо матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за 4 ходи. Сумма елементів на головній діагоналі майже дає нам потрібний результат. Нам треба відняти ходи такого типу 1-2-1-2-1 та 1-2-3-2-1. Щоб відняти ходи першого типу після першого перемноження поставимо на головній діагоналі нулі, що означатиме що ми не можемо у другому ході повернутися у ту вершину з якої прибули. Для другого типу треба помітити, що ми йдемо по тому шляху, по якому вже йшли тобто якщо мі за два ходи дійшли до певної вершини $a$ способами, то повертаючись назад отримаємо $2a$ способів, але з них рівно $a$ нам не підходять, тому після другого перемноження с діагоналі видаляємо сумму на ряді на моменті коли було зроблено усього $2$ ходи, звісно не враховуючи елементи на головній діагоналі. Ми будували неорієнтований граф тому сумму на діагоналі треба поділити на $2,$ а ще в наших циклах по $4$ вершини, тому треба ще поділити на 4.

    Посилання

    ideone
    e-olymp

    e-olymp 8525. Четные отрицательные в матрице

    by

    0

    Задача. Четные отрицательные в матрице

    Задана матрица размера $n \times n$. Найдите количество и сумму ее четных отрицательных элементов.

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

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

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

    Выведите в одной строке количество и сумму четных отрицательных чисел в матрице.

    Тесты

    № Ввод Вывод
    1 3
    4 -2 5
    1 -4 -12
    0 1 -3    		 3 -18
    2 5
    -100 -100 -100 -100 -100
    -100 -100 -100 -100 -100
    -100 -100 -100 -100 -100
    -100 -100 -100 -100 -100
    -100 -100 -100 -100 -100    		 25 -2500
    3 2
    0 0
    0 0    		 0 0
    4 3
    -2 -1 -1
    -1 -2 -1
    -1 -1 -2    		 3 -6
    5 2
    6 8
    12 100    		 0 0
    6 4
    -25 0 12 5
    -29 47 23 15
    11 100 -89 20
    55 25 42 -12    		 1 -12
    7 2
    -12 -12
    -12 -12    		 4 -48

    Решение

    При обработке двумерного массива я использовал один цикл длиной в $n^2$ витков.
    В нём я обращался к элементам с помощью целого и остатка от деления на $n$, то есть изменял второй индекс заново через каждые $n$ элементов, увеличивая, при таком переходе, первый индекс на единицу.
    Используя этот приём я избежал вложенных циклов и просматривал элементы в том же порядке, как если бы их использовал.

    Код

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

    by

    4

    Задача взята с сайта 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. Умножение матриц

    by

    0

    Задача

    Пусть даны две прямоугольные матрицы $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. Седловые точки

    by

    7

    Задача

    Задана матрица [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. Объём параллелепипеда

    by

    2

    Задача. Найти объём параллелепипеда три стороны которого образованы векторами [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. Объём тетраэдра

    by

    6

    Задача

    Найти объём тетраэдра три стороны которого образованы векторами [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

    by

    8

    Задача

    С помощью [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

    by

    1

    Задача: Все ненулевые элементы матрицы [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

    by

    2

    Задача:
    Даны квадратные матрицы [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в

    by

    1

    Задача. Дана квадратная матрица А порядка 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б

    by

    3

    Условие

    Симметричные квадратные матрицы [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б

    by

    3

    Условие

    Две правые треугольные матрицы [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

    by

    2

    Задача: Дана матрица [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

    by

    2

    Задача

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

     

     

    Решение