A713

Задача

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

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

Задача:

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

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.