A713

Недомовний Владислав
Недомовний Владислав

Latest posts by Недомовний Владислав (see all)

Задача

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

Даны квадратная матрица порядка m, натуральное число n. Вычислить следы матриц [latex]A, A^{2}, … , A^{n}[/latex].

Тесты

[latex]m[/latex] [latex]n[/latex] [latex]A[/latex] следы [latex]A, A^{2}, … , A^{n}[/latex] Комментарий
3 4  [latex]\begin{pmatrix} 1 & 2 & 3\\ 1 & 2& 3 \\ 1 & 2 & 3 \end{pmatrix}[/latex] 6 36 216 1296 Пройден
 2  5  [latex]\begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}[/latex]  5 29 155 833 4475  Пройден
Код
C++
Java
Решение

 Находим след исходной матрицы вне цикла. После, в цикле перемножаем матрицы и находим следы уже полученных матриц.

Решение на ideone: (C++) (Java).

A711б

Сорокина Полина
Сорокина Полина

Latest posts by Сорокина Полина (see all)

Задача:

Дана матрица [latex]A[/latex] размера [latex]m\times n[/latex]. Найти матрицу [latex]AA^{*}[/latex] (её размер [latex]m\times m[/latex]).

[latex]m[/latex] [latex]n[/latex] [latex]A[/latex] [latex]AA^{*}[/latex]
3 5 1 2 3 4 5
0 0 0 78 92
6 7 8 9 110
55 772 630
772 14548 10822
630 10822 12330
Тест пройден
2 4 11 22 33 44
76 0 1 0
3630 869
869 5777
Тест пройден

C++:

Java:

[latex]A^{*}[/latex] — транспонированная матрица [latex]A[/latex]. Её строки — это столбцы [latex]A[/latex], а столбцы — строки [latex]A[/latex].

Задача на Ideone:
C++
Java

A699

Григорян Артак
Григорян Артак

Latest posts by Григорян Артак (see all)

A699. Даны квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex].Получить матрицу [latex]AB-BA[/latex].
Размер матрицы Матрица А Матрица В Результат
3 1 2 3
4 5 6
7 8 9
9 8 7
6 5 4
3 2 1
-60 -90 -120
30     0   -30
120   90  60
2 3  13
21 8
7 9
2 4
-163 -84
73   163
Создаем матрицы [latex]A, B, C, D, E,[/latex] где [latex]A[/latex]-первая матрица, [latex]B[/latex]- вторая матрица, [latex]C[/latex]-матрица [latex]AB[/latex], [latex]B[/latex]- матрица [latex]BA[/latex], а [latex]E[/latex]- матрица [latex]AB-BA[/latex]. Вводим с клавиатуры матрица [latex]A[/latex] и [latex]B[/latex], а остальные заполняем нулями. Находим матрицу [latex]C[/latex] и [latex]D[/latex], после чего находим матрицу [latex]E[/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.