A713

16/06/2015 by Недомовний Владислав

Задача

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

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

#include <iostream>
using namespace std;

int main() {
	int m,n;
	cin >> m >> n;
	int A[m][m]; //массив для хранения исходной матрицы
	int B[m][m]; //массив для хранения степеней исходной матрицы
	int C[m][m]; //массив для хранения произведений A на B при возведении в степень
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin >> A[i][j];
			B[i][j]=A[i][j];
		}
	}
	int sum=0;
	int result=0;
	if(n>0)
	{
		for(int i=0;i<m;i++)
		{
			result+=B[i][i]; //нахождение следа исходной матрицы 
		}
		cout << result << " ";
	}
	for(int q=0;q<n-1;q++)
	{
		for(int i=0;i<m;i++) //перемножение матриц
        {
           for(int z=0;z<m;z++)
           {
           		for(int j=0;j<m;j++)
				{
					sum+=A[i][j]*B[j][z];
				}
				C[i][z]=sum; 
				sum=0;
			}
		}
		for(int i=0;i<m;i++) //переприсваивание элементов матрицы
		{
			for(int j=0;j<m;j++)
			{
				B[i][j]=C[i][j];
			}
		}
		result=0;
		for(int i=0;i<m;i++)
		{
			result+=B[i][i]; //нахождение следа полученной матрицы
		}
		cout << result << " ";
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int m,n;

cin >> m >> n;

int A[m][m]; //массив для хранения исходной матрицы

int B[m][m]; //массив для хранения степеней исходной матрицы

int C[m][m]; //массив для хранения произведений A на B при возведении в степень

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

{

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

{

cin >> A[i][j];

B[i][j]=A[i][j];

}

int sum=0;

int result=0;

if(n>0)

{

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

{

result+=B[i][i]; //нахождение следа исходной матрицы

}

cout << result << " ";

}

for(int q=0;q<n-1;q++)

{

for(int i=0;i<m;i++) //перемножение матриц

{

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

{

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

{

sum+=A[i][j]*B[j][z];

}

C[i][z]=sum;

sum=0;

}

for(int i=0;i<m;i++) //переприсваивание элементов матрицы

{

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

{

B[i][j]=C[i][j];

}

result=0;

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

{

result+=B[i][i]; //нахождение следа полученной матрицы

}

cout << result << " ";

}

return 0;

}

Java

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

class Ideone
{
	public static void main (String[] args) 
	{
		int m,n;
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		n = sc.nextInt();
		int[][] A = new int[m][m]; //массив для хранения исходной матрицы
		int[][] B = new int[m][m]; //массив для хранения степеней исходной матрицы
		int[][] C = new int[m][m]; //массив для хранения произведений A на B при возведении в степень
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<m;j++)
			{
				A[i][j] = sc.nextInt();
				B[i][j]=A[i][j];
			}
		}
		int sum=0;
		int result=0;
		if(n>0)
		{
			for(int i=0;i<m;i++)
			{
				result+=B[i][i]; //нахождение следа исходной матрицы 
			}
			System.out.printf("%d ",result);
		}
		for(int q=0;q<n-1;q++)
		{
			for(int i=0;i<m;i++) //перемножение матриц
	        {
	           for(int z=0;z<m;z++)
	           {
	           		for(int j=0;j<m;j++)
					{
						sum+=A[i][j]*B[j][z];
					}
					C[i][z]=sum; 
					sum=0;
				}
			}
			for(int i=0;i<m;i++) //переприсваивание элементов матрицы
			{
				for(int j=0;j<m;j++)
				{
					B[i][j]=C[i][j];
				}
			}
			result=0;
			for(int i=0;i<m;i++)
			{
				result+=B[i][i]; //нахождение следа полученной матрицы
			}
			System.out.printf("%d ",result);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

int m,n;

Scanner sc = new Scanner(System.in);

m = sc.nextInt();

n = sc.nextInt();

int[][] A = new int[m][m]; //массив для хранения исходной матрицы

int[][] B = new int[m][m]; //массив для хранения степеней исходной матрицы

int[][] C = new int[m][m]; //массив для хранения произведений A на B при возведении в степень

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

{

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

{

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

B[i][j]=A[i][j];

}

int sum=0;

int result=0;

if(n>0)

{

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

{

result+=B[i][i]; //нахождение следа исходной матрицы

}

System.out.printf("%d ",result);

}

for(int q=0;q<n-1;q++)

{

for(int i=0;i<m;i++) //перемножение матриц

{

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

{

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

{

sum+=A[i][j]*B[j][z];

}

C[i][z]=sum;

sum=0;

}

for(int i=0;i<m;i++) //переприсваивание элементов матрицы

{

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

{

B[i][j]=C[i][j];

}

result=0;

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

{

result+=B[i][i]; //нахождение следа полученной матрицы

}

System.out.printf("%d ",result);

}

Решение

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

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

Related Images:

A711б

19/05/2015 by Сорокина Полина

Задача:

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

#include <iostream>
using namespace std;

int main() {
	int m, n;
	cin >> m >> n;
	int A[m][n], AAt[m][m];
	for(int i=0; i<m; i++){
		for(int j=0; j<n; j++){
			cin >> A[i][j];
		}
	}
	for(int i=0; i<m; i++){
        for(int j=0; j<m; j++){
            int tmp=0;
            for(int k=0; k<n; k++){
                tmp+=A[i][k]*A[j][k];
            }
            AAt[i][j]=tmp;
        }
    }
    for(int i=0; i<m; i++){
		for(int j=0; j<m; j++){
			cout << AAt[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int m, n;

cin >> m >> n;

int A[m][n], AAt[m][m];

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

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

cin >> A[i][j];

}

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

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

int tmp=0;

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

tmp+=A[i][k]*A[j][k];

}

AAt[i][j]=tmp;

}

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

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

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

}

cout << endl;

}

return 0;

}

Java:

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();
		int n = in.nextInt();
		
		int A[][] = new int [m][n];
		int AAt[][] = new int [m][m];
		
		for(int i=0; i<m; i++){
			for(int j=0; j<n; j++){
				A[i][j] = in.nextInt();
			}
		}
		for(int i=0; i<m; i++){
	        for(int j=0; j<m; j++){
	            int tmp=0;
	            for(int k=0; k<n; k++){
	                tmp+=A[i][k]*A[j][k];
	            }
	            AAt[i][j]=tmp;
	        }
	    }
	    for(int i=0; i<m; i++){
			for(int j=0; j<m; j++){
				System.out.print(AAt[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();

int n = in.nextInt();

int A[][] = new int [m][n];

int AAt[][] = new int [m][m];

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

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

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

}

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

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

int tmp=0;

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

tmp+=A[i][k]*A[j][k];

}

AAt[i][j]=tmp;

}

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

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

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

}

System.out.println("");

}

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

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

Related Images:

A699

17/05/2015 by Григорян Артак

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

#include <iostream>
using namespace std;

int main() 
{
	int n;
	cin>>n;
	
	int **A = new int*[n]; 
	for (int i=0;i<n;i++)
           A[i] = new int [n];
         
        int **B = new int*[n]; 
        for (int i=0;i<n;i++)
           B[i] = new int [n];
        
        int **C = new int*[n]; 
        for (int i=0;i<n;i++)
           C[i] = new int [n];
    
        for(int i=0;i<n;i++)
    	   for(int j=0;j<n;j++)
    		C[i][j]=0;
        
         int **D = new int*[n]; 
         for (int i=0;i<n;i++)
             D[i] = new int [n];
        
        for(int i=0;i<n;i++)
    	   for(int j=0;j<n;j++)
    		D[i][j]=0;
        
        int **E = new int*[n]; 
        for (int i=0;i<n;i++)
            E[i] = new int [n];
        
        for(int i=0;i<n;i++)
    	    for(int j=0;j<n;j++)
    		E[i][j]=0;
        
        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++)
    		{
    			for(int k=0;k<n;k++)
    			C[i][j]=C[i][j]+A[i][k]*B[k][j];
    		}
    
        for(int i=0;i<n;i++)
    	    for(int j=0;j<n;j++)
    		{ 
    			for(int k=0;k<n;k++)
    			D[i][j]=D[i][j]+B[i][k]*A[k][j];
    		}
    		
        for(int i=0;i<n;i++)
    	    for(int j=0;j<n;j++)
    		{
    			E[i][j]=C[i][j]-D[i][j];
    		}
    		
        for(int i=0;i<n;i++)
           {
    	     for(int j=0;j<n;j++)
    		 cout<<E[i][j]<<" ";
    	     cout<<"\n";
           }
	return 0;
	
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin>>n;

int **A = new int*[n];

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

A[i] = new int [n];

int **B = new int*[n];

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

B[i] = new int [n];

int **C = new int*[n];

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

C[i] = new int [n];

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

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

C[i][j]=0;

int **D = new int*[n];

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

D[i] = new int [n];

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

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

D[i][j]=0;

int **E = new int*[n];

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

E[i] = new int [n];

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

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

E[i][j]=0;

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++)

{

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

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

}

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

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

{

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

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

}

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

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

{

E[i][j]=C[i][j]-D[i][j];

}

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

{

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

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

cout<<"\n";

}

return 0;

}

Создаем матрицы [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].

Код программы можно посмотреть тут

Related Images:

А706 Алгоритм быстрого возведения в степень

14/05/2015 by Осецимський Анатолій Вадимович

Степень

Входная матрица

Результирующая матрица

0	1
2	3

2	3
6	11

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] мы можем домножить на временную матрицу матрицу ответ.

#include <iostream>
#include <string>
#include <vector>
#include <deque>
using namespace std;

class matrix{ //создаем класс матрицы, в основном для красивого перемножения
    private:
        int n,m;
        int long long **arr;
    public:
        matrix(){
            n = 1; m = 1;
        }
        matrix(int x){
            n = x; m = x;
            arr = new int long long *[n];
            for(int i = 0; i < n; i++){
                arr[i] = new int long long [m];
            }
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    arr[j][k] = 0;
                }
            }
        }
        matrix(int x, int y){
            n = x; m = y;
            arr = new int long long *[n];
            for(int i = 0; i < n; i++){
                arr[i] = new int long long [m];
            }
            for(int j = 0; j < this->n; j++){ // необходимо инициализировать нулями,покольку в памяти может быть забытый мусор
                for(int k = 0; k < this->m; k++){
                    arr[j][k] = 0;
                }
            }
        } // выше были описанны конструкторы
        ~matrix(){
            for(int i = 0; i < n; i++){
                delete arr[i];
            }
            delete arr;
        }// деструктор
        void read(){
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    cin >> arr[j][k];
                }
            }
        }//функция ввода
        void write(){
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    cout << arr[j][k] << " ";
                }
                cout << endl;
            }
        }// функция вывода
        void create(int x, int y){
            n = x; m = y;
            arr = new int long long *[n];
            for(int i = 0; i < n; i++){
                arr[i] = new int long long [m];
            }
        }//функция измененияколичества выделяемой под нас памяти
        matrix& operator=(const matrix& x){
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    arr[j][k] = x.arr[j][k];
                }
            }
            return *this;
        }// переопределение оператора присваивания для матриц
        const matrix operator*(const matrix& x){
            matrix ans(this->n, this->m);
            for(int i = 0; i < this->n; i++){
                for(int j = 0; j < this->m; j++){
                    for(int k = 0; k < this->m; k++){
                        ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];
                    }
                }
            }
            return ans;
        }//переопределение умножения для матриц
        matrix& operator*=(const matrix& x){
            matrix ans(this->n, this->m);
            for(int i = 0; i < this->n; i++){
                for(int j = 0; j < this->m; j++){
                    for(int k = 0; k < this->m; k++){
                        ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];
                    }
                }
            }
            *this=ans;
            return *this;
        }//переопределение присвоить равно
        
        matrix& pow(int n){
            string s;
            for(int i = 0; i < sizeof(int)*8 -1; i++){// цикл где мы побитово сдвигаем вправо и умножаем на 1, если в этом бите была 1,то мы добавим в строку 1,если был 0,то 0 конъюнкия 1 будет 0
                s+= to_string((n >> i)&1);; 
            }
            int i = s.size()-1; // заводим переменную, в которой будет храниться наивисший разряд двойки
            for(; s[i]!= '1'; i--){} //находим этот разряд,двигаясь с конца в поисках первой 
            matrix ans(this->n,this->m);
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    if(j == k) ans.arr[j][k] = 1; else ans.arr[j][k] = 0; 
                }
            }
            matrix temp(this->n,this->m);
            temp = *this;
            for(int j = 0; j <= i; j++){
                if(s[j] == '1'){
                    ans*=temp;
                }
                temp*=temp;
            }
            *this=ans;
            return *this;
        }
};

int main() {
    int n,size = 2; string s; //n число,в которую нам надо возвести в степень,размеры матрицы и строка,в которой будем для удобства хранить двоичное представление числа
    cin >> n;
    matrix mas(size); // создаем матрицу
    mas.read();
    mas.pow(n);
    mas.write();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

#include <iostream>

#include <string>

#include <vector>

#include <deque>

using namespace std;

class matrix{ //создаем класс матрицы, в основном для красивого перемножения

private:

int n,m;

int long long **arr;

public:

matrix(){

n = 1; m = 1;

}

matrix(int x){

n = x; m = x;

arr = new int long long *[n];

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

arr[i] = new int long long [m];

}

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

for(int k = 0; k < this->m; k++){

arr[j][k] = 0;

}

matrix(int x, int y){

n = x; m = y;

arr = new int long long *[n];

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

arr[i] = new int long long [m];

}

for(int j = 0; j < this->n; j++){ // необходимо инициализировать нулями,покольку в памяти может быть забытый мусор

for(int k = 0; k < this->m; k++){

arr[j][k] = 0;

}

} // выше были описанны конструкторы

~matrix(){

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

delete arr[i];

}

delete arr;

}// деструктор

void read(){

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

for(int k = 0; k < this->m; k++){

cin >> arr[j][k];

}

}//функция ввода

void write(){

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

for(int k = 0; k < this->m; k++){

cout << arr[j][k] << " ";

}

cout << endl;

}

}// функция вывода

void create(int x, int y){

n = x; m = y;

arr = new int long long *[n];

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

arr[i] = new int long long [m];

}

}//функция измененияколичества выделяемой под нас памяти

matrix& operator=(const matrix& x){

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

for(int k = 0; k < this->m; k++){

arr[j][k] = x.arr[j][k];

}

return *this;

}// переопределение оператора присваивания для матриц

const matrix operator*(const matrix& x){

matrix ans(this->n, this->m);

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

for(int j = 0; j < this->m; j++){

for(int k = 0; k < this->m; k++){

ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];

}

return ans;

}//переопределение умножения для матриц

matrix& operator*=(const matrix& x){

matrix ans(this->n, this->m);

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

for(int j = 0; j < this->m; j++){

for(int k = 0; k < this->m; k++){

ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];

}

*this=ans;

return *this;

}//переопределение присвоить равно

matrix& pow(int n){

string s;

for(int i = 0; i < sizeof(int)*8 -1; i++){// цикл где мы побитово сдвигаем вправо и умножаем на 1, если в этом бите была 1,то мы добавим в строку 1,если был 0,то 0 конъюнкия 1 будет 0

s+= to_string((n >> i)&1);;

}

int i = s.size()-1; // заводим переменную, в которой будет храниться наивисший разряд двойки

for(; s[i]!= '1'; i--){} //находим этот разряд,двигаясь с конца в поисках первой

matrix ans(this->n,this->m);

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

for(int k = 0; k < this->m; k++){

if(j == k) ans.arr[j][k] = 1; else ans.arr[j][k] = 0;

}

matrix temp(this->n,this->m);

temp = *this;

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

if(s[j] == '1'){

ans*=temp;

}

temp*=temp;

}

*this=ans;

return *this;

}

};

int main() {

int n,size = 2; string s; //n число,в которую нам надо возвести в степень,размеры матрицы и строка,в которой будем для удобства хранить двоичное представление числа

cin >> n;

matrix mas(size); // создаем матрицу

mas.read();

mas.pow(n);

mas.write();

return 0;

}

link.

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

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

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

A713

Related Images:

A711б

Related Images:

A699

Related Images:

А706 Алгоритм быстрого возведения в степень

Related Images: