А705

29/06/2015 by Кібакова Надія Олександрівна

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

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;                                             //ввод из стандартного потока
    int A[n][n];                                        
    int B[n][n];
    int Z[n][n];
    int H[n][n];
    int E[n][n];
    float C[n][n];
    float Ans[n][n];
    
    for (int i = 0; i < n; i++){             //матрица А
        for (int j = 0 ; j < n ; j++){
            cin >> A[i][j];
        }
    }
    
    for (int i = 0; i < n; i++){                            //матрица В
        for (int j = 0 ; j < n ; j++){
            cin >> B[i][j];
        }
    }
    
    for (int i = 0; i < n; i++){                            //единичная матрица Е
        for (int j = 0 ; j < n ; j++){
            if (i == j) E[i][j] = 1;
            else E[i][j] = 0;
        }
    }
 
    for (int i = 0; i < n; i++){                 //разность матриц В и Е
        for (int j = 0; j < n; j++){
            Z[i][j] = 0;
            Z[i][j] = B[i][j] - E[i][j];
        }
    }
    
    for (int i = 0; i < n; i++){             //умножение матриц А и (В - Е)
        for (int j = 0; j < n; j++){
            H[i][j] = 0;
            for (int t = 0; t < n; t++){
                H[i][j] += A[i][t] * Z[t][j];
            }
        }
    }
    
    for (int i = 0; i < n; i++){             //матрица С
        for (int j = 0; j < n; j++){
            C[i][j] = 0;
            C[i][j] = 1.0/(i+1 + j+1);
        }
    }
    
    for (int i = 0; i < n; i++){                 //матрица A(B–E)+C
        for(int j = 0; j < n; j++){
            Ans[i][j] = H[i][j] + C[i][j];
            printf("%1.2f", Ans[i][j]); 
             cout << " " ;
        }
        cout << endl;
    }
    
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n; //ввод из стандартного потока

int A[n][n];

int B[n][n];

int Z[n][n];

int H[n][n];

int E[n][n];

float C[n][n];

float Ans[n][n];

for (int i = 0; i < n; i++){ //матрица А

for (int j = 0 ; j < n ; j++){

cin >> A[i][j];

}

for (int i = 0; i < n; i++){ //матрица В

for (int j = 0 ; j < n ; j++){

cin >> B[i][j];

}

for (int i = 0; i < n; i++){ //единичная матрица Е

for (int j = 0 ; j < n ; j++){

if (i == j) E[i][j] = 1;

else E[i][j] = 0;

}

for (int i = 0; i < n; i++){ //разность матриц В и Е

for (int j = 0; j < n; j++){

Z[i][j] = 0;

Z[i][j] = B[i][j] - E[i][j];

}

for (int i = 0; i < n; i++){ //умножение матриц А и (В - Е)

for (int j = 0; j < n; j++){

H[i][j] = 0;

for (int t = 0; t < n; t++){

H[i][j] += A[i][t] * Z[t][j];

}

for (int i = 0; i < n; i++){ //матрица С

for (int j = 0; j < n; j++){

C[i][j] = 0;

C[i][j] = 1.0/(i+1 + j+1);

}

for (int i = 0; i < n; i++){ //матрица A(B–E)+C

for(int j = 0; j < n; j++){

Ans[i][j] = H[i][j] + C[i][j];

printf("%1.2f", Ans[i][j]);

cout << " " ;

}

cout << endl;

}

return 0;

}

Код C++ на Ideone: A705

Код Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone {
    public static void main (String[] args) throws java.lang.Exception {
        Scanner read = new Scanner (System.in); 
        int n = read.nextInt();                                         //ввод из стандартного потока
        double A[][] = new double [n][n];                                       
        double B[][] = new double [n][n];
        double Z[][] = new double [n][n];
        double H[][] = new double [n][n];
        double E[][] = new double [n][n];
        double C[][] = new double [n][n];
        double Ans[][] = new double [n][n];
    
        for (int i = 0; i < n; i++){             //матрица А
            for (int j = 0 ; j < n ; j++){
                A[i][j] = read.nextDouble();
            }
        }
    
        for (int i = 0; i < n; i++){                            //матрица В
            for (int j = 0 ; j < n ; j++){
                B[i][j] =  read.nextDouble();
            }
        }
    
        for (int i = 0; i < n; i++){                            //единичная матрица Е
            for (int j = 0 ; j < n ; j++){
                if (i == j) E[i][j] = 1;
                else E[i][j] = 0;
            }
        }
     
        for (int i = 0; i < n; i++){                 //разность матриц В и Е
            for (int j = 0; j < n; j++){
                Z[i][j] = 0;
                Z[i][j] = B[i][j] - E[i][j];
            }
        }
        
        for (int i = 0; i < n; i++){             //умножение матриц А и (В - Е)
            for (int j = 0; j < n; j++){
                H[i][j] = 0;
                for (int t = 0; t < n; t++){
                    H[i][j] += A[i][t] * Z[t][j];
                }
            }
        }
        
        for (int i = 0; i < n; i++){             //матрица С
            for (int j = 0; j < n; j++){
                C[i][j] = 0;
                C[i][j] = 1.0/((i+1)+(j+1));
            }
        }
        
        for (int i = 0; i < n; i++){                 //матрица A(B–E)+C
            for(int j = 0; j < n; j++){
                Ans[i][j] = H[i][j] + C[i][j];
                System.out.print(Ans[i][j] + " "); 
            }
            System.out.println();
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) throws java.lang.Exception {

Scanner read = new Scanner (System.in);

int n = read.nextInt(); //ввод из стандартного потока

double A[][] = new double [n][n];

double B[][] = new double [n][n];

double Z[][] = new double [n][n];

double H[][] = new double [n][n];

double E[][] = new double [n][n];

double C[][] = new double [n][n];

double Ans[][] = new double [n][n];

for (int i = 0; i < n; i++){ //матрица А

for (int j = 0 ; j < n ; j++){

A[i][j] = read.nextDouble();

}

for (int i = 0; i < n; i++){ //матрица В

for (int j = 0 ; j < n ; j++){

B[i][j] = read.nextDouble();

}

for (int i = 0; i < n; i++){ //единичная матрица Е

for (int j = 0 ; j < n ; j++){

if (i == j) E[i][j] = 1;

else E[i][j] = 0;

}

for (int i = 0; i < n; i++){ //разность матриц В и Е

for (int j = 0; j < n; j++){

Z[i][j] = 0;

Z[i][j] = B[i][j] - E[i][j];

}

for (int i = 0; i < n; i++){ //умножение матриц А и (В - Е)

for (int j = 0; j < n; j++){

H[i][j] = 0;

for (int t = 0; t < n; t++){

H[i][j] += A[i][t] * Z[t][j];

}

for (int i = 0; i < n; i++){ //матрица С

for (int j = 0; j < n; j++){

C[i][j] = 0;

C[i][j] = 1.0/((i+1)+(j+1));

}

for (int i = 0; i < n; i++){ //матрица A(B–E)+C

for(int j = 0; j < n; j++){

Ans[i][j] = H[i][j] + C[i][j];

System.out.print(Ans[i][j] + " ");

}

System.out.println();

}

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

Related Images:

А700в

19/06/2015 by Янішевська Альона Русланівна

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

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

#include <iostream>
 
using namespace std;
 
int main() {
	int n;
	cin >> n;
	double A[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> A[i][j];
		}
	}
 
	double B[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			B[i][j] = 0;
			if (i < j){B[i][j] = 10 * 0.1 / ((i+1) + (j+1) -1);}
			else {
				if (i == j){B[i][j] = 0;}
				else {B[i][j] = -10 * 0.1 / ((i+1) + (j+1) -1);}
			}	
		}
	}
 
	double C[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			C[i][j] = 0;
			for(int k = 0; k < n; k++){
				C[i][j] += A[i][k] * B[k][j];
			}
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cout << C[i][j] << " ";
		}
		cout << endl;
	}
 
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

double A[n][n];

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

cin >> A[i][j];

}

double B[n][n];

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

B[i][j] = 0;

if (i < j){B[i][j] = 10 * 0.1 / ((i+1) + (j+1) -1);}

else {

if (i == j){B[i][j] = 0;}

else {B[i][j] = -10 * 0.1 / ((i+1) + (j+1) -1);}

}

double C[n][n];

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

C[i][j] = 0;

for(int k = 0; k < n; k++){

C[i][j] += A[i][k] * B[k][j];

}

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

cout << C[i][j] << " ";

}

cout << endl;

}

return 0;

}

После ввода матрицы 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:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner  in = new Scanner(System.in);
		int  n = in.nextInt();
		double A[][];
		A = new double [n][];
		for(int i=0; i<n; i++){
			A[i] = new double [n];   
			for(int j=0; j<n; j++){
				A[i][j] = in.nextDouble();
			}
		}
		double B[][];
		B = new double [n][];
		for(int i=0; i<n; i++){
			B[i] = new double [n];  
			for(int j=0; j<n; j++){
				B[i][j]=0;
				if (i<j){
					B[i][j]=10*0.1/((i+1)+(j+1)-1);
				}
				else{
					if (i==j){
						B[i][j]=0;
					}
					else {
							B[i][j]=-10*0.1/((i+1)+(j+1)-1);
					}
				}	
			}
		}
		double C[][];
    	C = new double [n][];
		for(int i=0; i<n; i++){
		 	C[i] = new double [n];  
			for(int j=0; j<n; j++){
				C[i][j]=0;
				for(int k=0; k<n; k++){
					C[i][j]+=A[i][k]*B[k][j];
				}
			}
		}
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				System.out.print(C[i][j]+" "); 
			}
		System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

double A[][];

A = new double [n][];

for(int i=0; i<n; i++){

A[i] = new double [n];

for(int j=0; j<n; j++){

A[i][j] = in.nextDouble();

}

double B[][];

B = new double [n][];

for(int i=0; i<n; i++){

B[i] = new double [n];

for(int j=0; j<n; j++){

B[i][j]=0;

if (i<j){

B[i][j]=10*0.1/((i+1)+(j+1)-1);

}

else{

if (i==j){

B[i][j]=0;

}

else {

B[i][j]=-10*0.1/((i+1)+(j+1)-1);

}

double C[][];

C = new double [n][];

for(int i=0; i<n; i++){

C[i] = new double [n];

for(int j=0; j<n; j++){

C[i][j]=0;

for(int k=0; k<n; k++){

C[i][j]+=A[i][k]*B[k][j];

}

for(int i=0; i<n; i++){

for(int j=0; j<n; j++){

System.out.print(C[i][j]+" ");

}

System.out.println();

}

Ссылка на решение.

Related Images:

А719б

17/06/2015 by Іванов Вячеслав Володимирович

Условие

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

#include <bits/stdc++.h>
using namespace std;

//Симметричная квадратная матрица порядка n задана линейным набором из
//n(n+1)/2 элементов. Все методы класса оперируют только с таким представлением.

template <typename T>
class symmetric_matrix{
private:
    T* data;
    int data_size;
   
public:
    //Конструкторы.
    symmetric_matrix(){}
    symmetric_matrix(int n){
        data = new T[(n*(n+1))/2];
        data_size = n;
    }
    symmetric_matrix(int n, int value){
        data = new T[(n*(n+1))/2];
        for(int i = 0; i < (n*(n+1))/2; i++)
            data[i] = value;
        data_size = n;
    }
    //Методы.
    int size(){ return data_size; }
    T get(int pos){ return data[pos]; }
    void set(int pos, T value){ data[pos] = value; }
    //Подпространство симметричных квадратные матриц заданного порядка
    //не замкнутно относительно операции матричного умножения.
    //Тем не менее, при возведение матрицы в степень замкнутость не
    //нарушается, в связи с чем операция умножения реализована для него.
    symmetric_matrix<T> operator *(symmetric_matrix<T> B){
        int n = data_size;
        symmetric_matrix<T> C(n);
        int curr = 0;
        for(int row = 0; row < n; row++){			//row
            for(int col = row; col < n; col++){		//col
                int rpos = row, cpos = col;	        //(row, col)
                int rstep = n-1, cstep = n-1;	    //row, col step
                for(int i = 0; i < n; i++){
                    C.set(curr, C[curr] + data[rpos]*B[cpos]);
                    rpos += (rstep >= n-row)*(rstep - 1) + 1;
                    cpos += (cstep >= n-col)*(cstep - 1) + 1;
                    rstep--, cstep--;
                }
                curr++;
            }
        }
        return C;
    }

    //Операторы.
    T operator [](int pos){return data[pos];}
    symmetric_matrix<T> operator +(symmetric_matrix<T> B){
        int n = B.size();
        symmetric_matrix<T> C(n);
        for(int i = 0; i < (n*(n+1))/2; i++)
            C.set(i, data[i] + B[i]);
        return C;
    };
    symmetric_matrix<T> operator -(symmetric_matrix<T> B){
        int n = B.size();
        symmetric_matrix<T> C(n);
        for(int i = 0; i < (n*(n+1))/2; i++)
            C.set(i, data[i] - B[i]);
        return C;
    };
};

//Бинарный алгоритм возведения матрицы в степень.
template <typename T>
symmetric_matrix<T> power(symmetric_matrix<T> A, int n){
    symmetric_matrix<T> result(A.size());
    //Изначально result - нейтральный элемент относительно умножения
    //т.е. единичная матрица.
    for(int i = 0, diag = 0; i < A.size(); i++){
        result.set(diag, 1);
        diag += A.size()-i;
    }
    while(n){
        if(n & 1)
            result = result * A;
        A = A * A;
        n >>= 1;
    }
    return result;
}


int main(){
	int n; cin >> n;
	symmetric_matrix<int> A(n), B(n), C(n);
	//Считывание данных
	for(int i = 0; i < (n*(n+1))/2; i++){
        int value; cin >> value;
        A.set(i, value);
    }
    for(int i = 0; i < (n*(n+1))/2; i++){
        int value; cin >> value;
        B.set(i, value);
    }

    C = power(A, 2) - power(B, 2);
    for(int i = 0; i < (n*(n+1))/2; i++){
        cout << C.get(i) << " ";
    }
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

#include <bits/stdc++.h>

using namespace std;

//Симметричная квадратная матрица порядка n задана линейным набором из

//n(n+1)/2 элементов. Все методы класса оперируют только с таким представлением.

template <typename T>

class symmetric_matrix{

private:

T* data;

int data_size;

public:

//Конструкторы.

symmetric_matrix(){}

symmetric_matrix(int n){

data = new T[(n*(n+1))/2];

data_size = n;

}

symmetric_matrix(int n, int value){

data = new T[(n*(n+1))/2];

for(int i = 0; i < (n*(n+1))/2; i++)

data[i] = value;

data_size = n;

}

//Методы.

int size(){ return data_size; }

T get(int pos){ return data[pos]; }

void set(int pos, T value){ data[pos] = value; }

//Подпространство симметричных квадратные матриц заданного порядка

//не замкнутно относительно операции матричного умножения.

//Тем не менее, при возведение матрицы в степень замкнутость не

//нарушается, в связи с чем операция умножения реализована для него.

symmetric_matrix<T> operator *(symmetric_matrix<T> B){

int n = data_size;

symmetric_matrix<T> C(n);

int curr = 0;

for(int row = 0; row < n; row++){ //row

for(int col = row; col < n; col++){ //col

int rpos = row, cpos = col; //(row, col)

int rstep = n-1, cstep = n-1; //row, col step

for(int i = 0; i < n; i++){

C.set(curr, C[curr] + data[rpos]*B[cpos]);

rpos += (rstep >= n-row)*(rstep - 1) + 1;

cpos += (cstep >= n-col)*(cstep - 1) + 1;

rstep--, cstep--;

}

curr++;

}

return C;

}

//Операторы.

T operator [](int pos){return data[pos];}

symmetric_matrix<T> operator +(symmetric_matrix<T> B){

int n = B.size();

symmetric_matrix<T> C(n);

for(int i = 0; i < (n*(n+1))/2; i++)

C.set(i, data[i] + B[i]);

return C;

};

symmetric_matrix<T> operator -(symmetric_matrix<T> B){

int n = B.size();

symmetric_matrix<T> C(n);

for(int i = 0; i < (n*(n+1))/2; i++)

C.set(i, data[i] - B[i]);

return C;

};

//Бинарный алгоритм возведения матрицы в степень.

template <typename T>

symmetric_matrix<T> power(symmetric_matrix<T> A, int n){

symmetric_matrix<T> result(A.size());

//Изначально result - нейтральный элемент относительно умножения

//т.е. единичная матрица.

for(int i = 0, diag = 0; i < A.size(); i++){

result.set(diag, 1);

diag += A.size()-i;

}

while(n){

if(n & 1)

result = result * A;

A = A * A;

n >>= 1;

}

return result;

}

int main(){

int n; cin >> n;

symmetric_matrix<int> A(n), B(n), C(n);

//Считывание данных

for(int i = 0; i < (n*(n+1))/2; i++){

int value; cin >> value;

A.set(i, value);

}

for(int i = 0; i < (n*(n+1))/2; i++){

int value; cin >> value;

B.set(i, value);

}

C = power(A, 2) - power(B, 2);

for(int i = 0; i < (n*(n+1))/2; i++){

cout << C.get(i) << " ";

}

return 0;

}

Тесты

Детали реализации

Задачи раздела носят обучающий характер, так что при реализации были произведены определенные обобщения, что делает решение более универсальным.

Формулировка задачи не оговаривает тип элементов матрицы, так что класс [latex]symmetric\_matrix[/latex] является шаблоном, пригодным для типов данных, поддерживающих операции сложения, вычитания и умножения (соответствующие операторы определены внутри класса).
Алгоритм бинарного возведения матрицы в степень полезен при решении более широкого круга задач, в связи с чем также реализован. При необходимости, программа легко обобщается на большие степени матрицы.
Предусмотрены три типа конструкторов: конструктор по умолчанию и два параметрических конструктора, один из которых позволяет заполнить матрицу некоторым наперед заданным значением.
Для удобства работы с заданным представлением данных, добавлен синтаксический сахар: перегружен оператор [latex][][/latex], осуществляющий доступ к заданному элементу матрицы в линейном её представлении.

Related Images:

А700а

21/05/2015 by Оніщенко Олександр

Задача: Дана квадратная матрица [latex]A[/latex] порядка [latex]n[/latex]. Получить матрицу [latex]AB[/latex]; элементы матрицы [latex]B[/latex] вычисляются по формуле :

[latex]b_{ij} = \frac{1}{i+j-1}[/latex], при [latex]i,j=1,2,\dotsb n[/latex].

Тесты:

[latex]n[/latex]	[latex]A[/latex]	[latex]AB[/latex]	Комментарий
2	[latex] \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} [/latex]	[latex] \begin{pmatrix} 1 & 0.5 \\ 0.5 & 0.33 \end{pmatrix} [/latex]	Пройден
3	[latex]\begin{pmatrix}2 & 16 & -3 \\ 4 & 0 & 1 \\ -7 & 10 & 9\end{pmatrix}[/latex]	[latex]\begin{pmatrix}9 & 5.58 & 4.067\\ 4.33 & 2.25 & 1.53\\ 1 & 2.08 &1.96\end{pmatrix}[/latex]	Пройден

Код

#include <iostream>
#include <math.h>
using namespace std;
 
int main() {
	int  n;
	double p,q;
	cin >> n;
	double a[n][n], b[n][n], ab[n][n];
	for(int i=0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			cin >> a[i][j]; 
		}
	}
 	for(int i=0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
		 	 p=i+1; q=j+1;
		 	b[i][j]=1/(p+q-1);		
		}
	}
	for(int i=0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			ab[i][j]=0;
			for(int p=0; p < n; p++ )
			{
				 ab[i][j]+=a[i][p]*b[p][j];
			}
		}
	}
	for(int i=0; i < n; i++)
	{
		for(int j=0;  j < n; j++)
		{
			cout << ab[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

int n;

double p,q;

cin >> n;

double a[n][n], b[n][n], ab[n][n];

for(int i=0; i < n; i++)

{

for(int j = 0; j < n; j++)

{

cin >> a[i][j];

}

for(int i=0; i < n; i++)

{

for(int j = 0; j < n; j++)

{

p=i+1; q=j+1;

b[i][j]=1/(p+q-1);

}

for(int i=0; i < n; i++)

{

for(int j = 0; j < n; j++)

{

ab[i][j]=0;

for(int p=0; p < n; p++ )

{

ab[i][j]+=a[i][p]*b[p][j];

}

for(int i=0; i < n; i++)

{

for(int j=0; j < n; j++)

{

cout << ab[i][j] << " ";

}

cout << endl;

}

return 0;

}

Для начала создаем и вводим размерность [latex]n[/latex] матрицы [latex]A[/latex]. Создаем три двумерных массива [latex]a[/latex], [latex]b[/latex] и [latex]ab[/latex]. Вводим значения матрицы [latex]A[/latex] и заполняем ими массив [latex]a[/latex]. Определяем значения матрицы [latex]B[/latex] и помещаем их в массив [latex]yb[/latex]. С помощью трёх циклов [latex]for[/latex] перемножаем матрицы [latex]A[/latex] и [latex]B[/latex] и помещаем результат в массив [latex]ab[/latex]. Выводим полученную матрицу.

Ссылка на Ideone

Related Images:

A711a

20/05/2015 by Калачьов Андрій Сергійович

Задача: Дана матрица [latex]A [/latex] размера [latex]m\times m [/latex]. Получить матрицу [latex]AA^{*} [/latex] (ее размер [latex]m\times m [/latex]).

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

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

    #include <iostream>
    using namespace std;
     
    int main() {
    	int n;
    	cin>>n;
    	double x[n][n],y[n][n],z[n][n],mu=0;
    	for (int i = 0; i < n; i++){
    		for (int j = 0; j < n; j++){
    			cin>>x[i][j];
    			y[j][i]=x[i][j];
    		}
    	}
    	for (int i = 0; i < n; i++){
    		for (int j = 0; j < n; j++){
    			for (int p = 0; p < n; p++){	
    				mu += x[i][p]*y[p][j];
    			}
    			z[i][j] = mu;
    			mu = 0;
    		}
    	}
    	for (int i = 0; i < n; i++){
    		for (int j = 0; j < n; j++){
    			cout<<z[i][j]<<" ";
    		}
    		cout<<endl;
    	}
    }

#include <iostream>

using namespace std;

int main() {

int n;

cin>>n;

double x[n][n],y[n][n],z[n][n],mu=0;

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++){

cin>>x[i][j];

y[j][i]=x[i][j];

}

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++){

for (int p = 0; p < n; p++){

mu += x[i][p]*y[p][j];

}

z[i][j] = mu;

mu = 0;

}

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++){

cout<<z[i][j]<<" ";

}

cout<<endl;

}

Ссылка на ideone Java: http://ideone.com/u96MDY

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		double mu=0;
    	int n=in.nextInt();
    	double[][] x = new double[n][n];
    	double[][] y = new double[n][n];
    	double[][] z = new double[n][n];
    	for (int i = 0; i < n; i++){
    		for (int j = 0; j < n; j++){
    			x[i][j]=in.nextDouble();;
    			y[j][i]=x[i][j];
    		}
    	}
    	for (int i = 0; i < n; i++){
    		for (int j = 0; j < n; j++){
    			for (int p = 0; p < n; p++){	
    				mu += x[i][p]*y[p][j];
    			}
    			z[i][j] = mu;
    			mu = 0;
    		}
    	}
    	for (int i = 0; i < n; i++){
    		for (int j = 0; j < n; j++){
    			System.out.printf("%.1f ",z[i][j]);
    		}
    		System.out.println();
    	}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double mu=0;

int n=in.nextInt();

double[][] x = new double[n][n];

double[][] y = new double[n][n];

double[][] z = new double[n][n];

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++){

x[i][j]=in.nextDouble();;

y[j][i]=x[i][j];

}

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++){

for (int p = 0; p < n; p++){

mu += x[i][p]*y[p][j];

}

z[i][j] = mu;

mu = 0;

}

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++){

System.out.printf("%.1f ",z[i][j]);

}

System.out.println();

}

Вводим матрицу [latex]A[i][j] [/latex] и матрицу [latex]B[j][i] [/latex] в цикле по [latex] i,j[/latex] от одного до [latex] n[/latex]. Умножаем матрицу [latex] A[/latex] на [latex]A^{*} [/latex].

Related Images:

А714

19/05/2015 by Ковальський Олександр Дмитрович

Задача

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

Пример

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

Вывод

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

16 13 70

9 24 39

-68 -91 -75

99 141 186

96 108 167

110 165 218

Решение

#include <iostream>
using namespace std;

int main()
	{
		int m;
		cin>>m;
		int A[m][m], B[m][m], C[m][m], D[m][m];
		int X[m][m], Y[m][m];
		int el;
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				cin>>A[i][j];
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				cin>>B[i][j];
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				cin>>C[i][j];
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				cin>>D[i][j];
		
		for(int i=0;i<m;i++)
			{
				for(int j=0;j<m;j++)
					{
						el=0;
						for(int l=0;l<m;l++)
							{
								el=el+A[i][l]*C[l][j]-B[i][l]*D[l][j];
							}
						X[i][j]=el;
					}
			}
		for(int i=0;i<m;i++)
			{
				for(int j=0;j<m;j++)
					{
						el=0;
						for(int l=0;l<m;l++)
							{
								el=el+A[i][l]*D[l][j]+B[i][l]*C[l][j];
							}
						Y[i][j]=el;
					}
			}
		cout<<"X:"<<endl;
		for(int i=0;i<m;i++)
			{
				for(int j=0;j<m;j++)
					{
						cout<<X[i][j]<<" ";
					}
				cout<<endl;
			}
		cout<<endl;
		cout<<"Y:"<<endl;
		for(int i=0;i<m;i++)
			{
				for(int j=0;j<m;j++)
					{
						cout<<Y[i][j]<<" ";
					}
				cout<<endl;
			}
		return 0;
	}

#include <iostream>

using namespace std;

int main()

{

int m;

cin>>m;

int A[m][m], B[m][m], C[m][m], D[m][m];

int X[m][m], Y[m][m];

int el;

for(int i=0;i<m;i++)

for(int j=0;j<m;j++)

cin>>A[i][j];

for(int i=0;i<m;i++)

for(int j=0;j<m;j++)

cin>>B[i][j];

for(int i=0;i<m;i++)

for(int j=0;j<m;j++)

cin>>C[i][j];

for(int i=0;i<m;i++)

for(int j=0;j<m;j++)

cin>>D[i][j];

for(int i=0;i<m;i++)

{

for(int j=0;j<m;j++)

{

el=0;

for(int l=0;l<m;l++)

{

el=el+A[i][l]*C[l][j]-B[i][l]*D[l][j];

}

X[i][j]=el;

}

for(int i=0;i<m;i++)

{

for(int j=0;j<m;j++)

{

el=0;

for(int l=0;l<m;l++)

{

el=el+A[i][l]*D[l][j]+B[i][l]*C[l][j];

}

Y[i][j]=el;

}

cout<<"X:"<<endl;

for(int i=0;i<m;i++)

{

for(int j=0;j<m;j++)

{

cout<<X[i][j]<<" ";

}

cout<<endl;

}

cout<<endl;

cout<<"Y:"<<endl;

for(int i=0;i<m;i++)

{

for(int j=0;j<m;j++)

{

cout<<Y[i][j]<<" ";

}

cout<<endl;

}

return 0;

}

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
        int m = in.nextInt(), el;
		int[][] A = new int[m][m], B = new int[m][m], C = new int[m][m], D = new int[m][m],X = new int[m][m], Y = new int[m][m];
		for(int i = 0; i < m; i++)
			for(int j = 0; j < m; j++)
				A[i][j] = in.nextInt();
		for(int i = 0; i < m; i++)
			for(int j = 0; j < m; j++)
				B[i][j] = in.nextInt();
		for(int i = 0; i < m; i++)
			for(int j = 0; j < m; j++)
				C[i][j] = in.nextInt();
		for(int i = 0; i < m; i++)
			for(int j = 0; j < m;j++)
				D[i][j] = in.nextInt();
		for(int i = 0; i < m; i++)
			{
				for(int j = 0; j < m; j++)
					{
						el = 0;
						for(int l = 0;l < m; l++)
							{
								el += A[i][l] * C[l][j] - B[i][l] * D[l][j];
							}
						X[i][j] = el;
					}
			}
		for(int i = 0; i < m; i++)
			{
				for(int j = 0; j < m; j++)
					{
						el = 0;
						for(int l = 0; l < m; l++)
							{
								el += A[i][l] * D[l][j] + B[i][l] * C[l][j];
							}
						Y[i][j] = el;
					}
			}
		System.out.println("X:");
		for(int i = 0; i < m; i++)
			{
				for(int j = 0; j < m; j++)
					{
						System.out.printf(X[i][j] + " ");
					}
				System.out.println();
			}
		System.out.println();
		System.out.println("Y:");
		for(int i = 0; i < m; i++)
			{
				for(int j = 0; j < m; j++)
					{
						System.out.printf(Y[i][j] + " ");
					}
				System.out.println();
			}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int m = in.nextInt(), el;

int[][] A = new int[m][m], B = new int[m][m], C = new int[m][m], D = new int[m][m],X = new int[m][m], Y = new int[m][m];

for(int i = 0; i < m; i++)

for(int j = 0; j < m; j++)

A[i][j] = in.nextInt();

for(int i = 0; i < m; i++)

for(int j = 0; j < m; j++)

B[i][j] = in.nextInt();

for(int i = 0; i < m; i++)

for(int j = 0; j < m; j++)

C[i][j] = in.nextInt();

for(int i = 0; i < m; i++)

for(int j = 0; j < m;j++)

D[i][j] = in.nextInt();

for(int i = 0; i < m; i++)

{

for(int j = 0; j < m; j++)

{

el = 0;

for(int l = 0;l < m; l++)

{

el += A[i][l] * C[l][j] - B[i][l] * D[l][j];

}

X[i][j] = el;

}

for(int i = 0; i < m; i++)

{

for(int j = 0; j < m; j++)

{

el = 0;

for(int l = 0; l < m; l++)

{

el += A[i][l] * D[l][j] + B[i][l] * C[l][j];

}

Y[i][j] = el;

}

System.out.println("X:");

for(int i = 0; i < m; i++)

{

for(int j = 0; j < m; j++)

{

System.out.printf(X[i][j] + " ");

}

System.out.println();

}

System.out.println();

System.out.println("Y:");

for(int i = 0; i < m; i++)

{

for(int j = 0; j < m; j++)

{

System.out.printf(Y[i][j] + " ");

}

System.out.println();

}

[latex]X+iY=(A+iB)(C+iD)=(AC-BD)+i(AD+BC)[/latex], т. е. [latex]X=AC-BD[/latex], [latex]Y=AD+BC[/latex].

Код на ideone.

Related Images:

A719a

14/05/2015 by Ілларіонова Марія Валеріївна

Симметричные квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex] заданы последовательностями из [latex]n\left(n+1 \right)/2[/latex] чисел, аналогично правым треугольным матрицам. Получить матрицу [latex]AB[/latex].

[latex]n[/latex]	[latex]A[/latex]	[latex]B[/latex]	[latex]AB[/latex]
3	0 1 2 0 2 1	0 1 3 0 2 1	7 4 4 6 5 5 5 4 11
2	0 1 0	1 0 1	0 1 1 0
3	1 2 3 4 5 6	1 0 0 4 2 2	1 14 10 2 26 18 3 32 22
4	1 1 1 1 2 2 2 3 3 4	6 6 6 6 5 5 5 3 2 1	24 21 16 14 42 36 26 22 54 46 31 25 60 51 33 26

Тесты проверены на этом сайте.

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

#include <iostream>
using namespace std;

int A[100][100];
int B[100][100];
int C[100][100];

int main() {
    int n;
    cin >> n;
    int i=0, j=0, t=0;
    for (i=0; i<n; i++) {
        for (j=i; j<n; j++) {
            cin >> t;
            A[i][j]=A[j][i]=t;
        }
    }
    for (i=0; i<n; i++) {
        for (j=i; j<n; j++) {
            cin >> t;
            B[i][j]=B[j][i]=t;
        }
    }
    for (i=0; i<n; i++) {
        for (j=0; j<n; j++) {
            for (int k=0; k<n; k++) {
                C[i][j]+=A[i][k]*B[k][j];
            }
        }
    }
    for (i=0; i<n; i++) {
        for (j=0; j<n; j++) {
            cout << C[i][j] << "\t";
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int A[100][100];

int B[100][100];

int C[100][100];

int main() {

int n;

cin >> n;

int i=0, j=0, t=0;

for (i=0; i<n; i++) {

for (j=i; j<n; j++) {

cin >> t;

A[i][j]=A[j][i]=t;

}

for (i=0; i<n; i++) {

for (j=i; j<n; j++) {

cin >> t;

B[i][j]=B[j][i]=t;

}

for (i=0; i<n; i++) {

for (j=0; j<n; j++) {

for (int k=0; k<n; k++) {

C[i][j]+=A[i][k]*B[k][j];

}

for (i=0; i<n; i++) {

for (j=0; j<n; j++) {

cout << C[i][j] << "\t";

}

cout << endl;

}

return 0;

}

Алгоритм решения:

Изначально мы считываем последовательность из [latex]n\left(n+1 \right)[/latex] для двух матриц (чтобы они были симметричекими, цикл по столбцам запускается с позиции текущей строки, а затем введённое значение копируется относительно главной диагонали).

Пусть [latex]C=\begin{Vmatrix}c_{ij}\end{Vmatrix} \in M_{m\times n}\left( \mathbb{R}\right) \left(i=1,2,\ldots,m; j=1,2,\ldots,n \right)[/latex].

Умножение матриц происходит по формуле [latex]c_{ij}=\sum_{r=1}^{n}{a_{ir}b_{rj}}\left(i=1,2,\ldots,m; j=1,2,\ldots,n \right)[/latex].

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: умножение матриц

А705

Related Images:

А700в

Related Images:

А719б

Условие

Решение

Замечание 1

Пример

Замечание 2

Тесты

Реализация

Тесты

Детали реализации

Related Images:

А700а

Related Images:

A711a

Related Images:

А714

Related Images:

A719a

Related Images: