Задача
Даны квадратная матрица [latex]A[/latex] порядка [latex]m[/latex], натуральное число [latex]n[/latex]. Получить матрицу [latex]E+A+A^2+A^3+\dots+A^n,[/latex] где [latex]E[/latex] — единичная матрица порядка [latex]m[/latex].
Тесты
| m, n | матрица А | результат |
| 3 3 | 3 2 1
5 7 3 9 7 3 |
359 358 158
1028 1047 460 1156 1162 513 |
| 2 2 | 6 7
12 54 |
127 427
732 3055 |
Код на языке С++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> using namespace std; int main() { int n, m; cin >> m >> n; double a[m][m]; //Исходная матрица double b[m][m]; //Вспомогательная матрица double c[m][m]; //Матрица в степени n double ans[m][m];//Результирующая матрица for(int i = 0; i < m; i++){ for(int j = 0; j < m; j++){ a[i][j] = b[i][j] = c[i][j] = ans[i][j] = 0; //Очистка памяти } } for(int i = 0; i < m; i++){ for(int j = 0; j < m; j++){ cin >> a[i][j]; c[i][j] = b[i][j] = ans[i][j] = a[i][j]; } } for(int it = 1; it < n; it++){ //Возводим матрицу в след. степень for(int i = 0; i < m; i++){ for(int j = 0; j < m; j++){ c[i][j] = 0; for(int k = 0; k < m; k++){ c[i][j] += a[i][k]*b[k][j]; } } } for(int i = 0; i < m; i++){ for(int j = 0; j < m; j++){ ans[i][j] += c[i][j]; //Добавляем к ответу b[i][j] = c[i][j]; //Заменяем вспомогательную матрицу } } } //Добавляем единичную матрицу for(int i = 0; i < m; i++){ ans[i][i]++; } //Вывод результата for(int i = 0; i < m; i++){ for(int j = 0; j < m; j++){ cout << ans[i][j] << ' '; } cout << endl; } return 0; } |
Ссылка на программу:http://ideone.com/3B9ti7
Код на языке Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main (String[] args) { Scanner sc = new Scanner (System.in); int n, m; m = sc.nextInt(); n = sc.nextInt(); double [][] a = new double [m][m]; double [][] b = new double [m][m]; double [][] c = new double [m][m]; double [][] ans = new double [m][m]; for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { a[i][j] = sc.nextDouble(); c[i][j] = b[i][j] = ans[i][j] = a[i][j]; } } for (int it = 1; it < n; it++) { for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { c[i][j] = 0; for (int k = 0; k < m; k++) { c[i][j] += a[i][k] * b[k][j]; } } } for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { ans[i][j] += c[i][j]; b[i][j] = c[i][j]; } } } for (int i = 0; i < m; i++) { ans[i][i]++; } for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { System.out.print(ans[i][j] + " "); } System.out.println(); } } } |
Ссылка на программу: http://ideone.com/hOFldD
Решение:
Заводим четыре матрицы: исходную, вспомогательную, матрицу в степени [latex]n[/latex] и результирующую; обнуляем все матрицы, тем самым очищаем память. Дальше возводим матрицу в степень [latex]n[/latex], добавляем к результирующей и заменяем вспомогательную матрицу. В завершении мы прибавим единичную матрицу к ответы и выведем его.
Зачтено, но…
В тестах для матриц указано на одно число меньше, чем следует. Возможно пропущен перевод строки.