Category Archives: 6. Многомерные массивы

Работа с прямоугольными массивами.

Массивы

Опубликовано: 20/10/2014

К этой рубрике относятся задания на использование классических массивов, работе с ними через указатели и ссылочные типы. Желательно снова перечитать параграф 3.5 и 3.6 из праймера. Размер массива обычно будет читаться из входного потока. Это вынуждает использовать динамические массивы. В качестве заготовки можно использовать такой код:

#include <iostream>
using namespace std;
 
int main() {
    size_t n;   
    cin >> n;
    double *x = new double [n];
    for(size_t i = 0; i < n; i++)
        cin >> x[i];
        
    // Processing 
    for(size_t i = 0; i < n; i++)
        cout << "x[" << i << "] = " << x[i] << "\t";
}

#include <iostream>

using namespace std;

int main() {

size_t n;

cin >> n;

double *x = new double [n];

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

cin >> x[i];

// Processing

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

cout << "x[" << i << "] = " << x[i] << "\t";

}

Выполнить программу Обратите внимание, что цикл в котором … Continue reading →

нет комментариев

В классе и дома решаются следующие тренировочные задачи (1 балл):

Шоколад

Опубликованные решения

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:

А701б

13/06/2015 by Царев Николай Александрович

Условие

Даны квадратная матрица [latex]A[/latex] порядка [latex]n[/latex] и вектор [latex]b[/latex] c [latex]n[/latex] элементами. Получить вектор [latex]{ A }^{ 2 }b[/latex]

Тесты

n	A	b	Результат
3	1 1 11 1 1 1 1 1	5 5 5	45 45 45
5	1 0 0 0 00 2 0 0 0 0 0 3 0 0 0 0 0 4 0 0 0 0 0 5	8 1 8 1 8	8 4 72 16 200
2	1 00 1	2 2	2 2

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >>n;
    double matr1[n][n];  //Матрица А
    double matr2[n][n]; // Матрица А^2
    double vet1[n];  //Вектор данный по условию (вектор b)
    double vet2[n];  //Конечный вектор
    for(int i=0;i<n;i++){
        for(int j=0; j<n; j++) // Инициализация матрицы А
            cin>>matr1[i][j];
    }

    for(int i=0; i<n;i++){
        for(int j=0;j<n;j++){  //Возведение матрицы А в квадрат
            matr2[i][j]=0;
            for(int p=0;p<n;p++)
                matr2[i][j]+=(matr1[i][p]*matr1[p][j]);
        }
    }

    for(int i=0; i<n; i++) //Инициализация вектора
        cin >> vet1[i];

    for(int i=0;i<n;i++){
        vet2[i]=0;
        for(int j=0; j<n; j++){
            vet2[i]+=matr2[i][j]*vet1[j]; //Умножение матрицы на вектор
        }
    }

    for(int i=0; i<n; i++)
        cout << vet2[i] << "\t"; //Вывод вектора
    cout << endl;

    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >>n;

double matr1[n][n]; //Матрица А

double matr2[n][n]; // Матрица А^2

double vet1[n]; //Вектор данный по условию (вектор b)

double vet2[n]; //Конечный вектор

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

for(int j=0; j<n; j++) // Инициализация матрицы А

cin>>matr1[i][j];

}

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

for(int j=0;j<n;j++){ //Возведение матрицы А в квадрат

matr2[i][j]=0;

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

matr2[i][j]+=(matr1[i][p]*matr1[p][j]);

}

for(int i=0; i<n; i++) //Инициализация вектора

cin >> vet1[i];

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

vet2[i]=0;

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

vet2[i]+=matr2[i][j]*vet1[j]; //Умножение матрицы на вектор

}

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

cout << vet2[i] << "\t"; //Вывод вектора

cout << endl;

return 0;

}

Алгоритм

Считываем матрицу. Возводим ее в квадрат ( перемножение матрицы осуществляется при помощи циклов). Считываем вектор. Умножаем матрицу на вектор. Выводим ответ.

Фактически, умножение матриц пишется по определению. Сумма произведений элементов строки на элементы столбцов.

Ссылка на ideone.com

Related Images:

e-olymp 5072. Подсчет количества ребер (ОГ)

28/05/2015 by Царев Николай Александрович

Задача

Ориентированный граф задан матрицей смежности.
Найдите количество ребер в графе.

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

Входной файл содержит число n (1 ≤ n ≤ 100) — число вершин в графе, и затем n строк по n чисел, каждое из которых равно 0 или 1 — его матрицу смежности.

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

Выведите в выходной файл количество ребер заданного графа.

Решение

Задача на E-Olimp.

30 1 11 0 1

0 1 1

50 1 1 1 11 0 0 0 0

1 0 0 0 0

0 0 1 0 1

1 0 0 0 0

21 11 1

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int k, l=0;
    for(int i=0;i<n;i++){
        for(int j=0; j<n; j++){
            cin >> k;
            if(k)
            l++;
        }
    }
    cout << l << endl;

    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int k, l=0;

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

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

cin >> k;

if(k)

l++;

}

cout << l << endl;

return 0;

}

Алгоритм решения прост. Количество ребер ориентированного графа равно количеству единиц в его матрице смежности. Поэтому просто считываем, суммируем если 1, и выводим ответ.

Задача на ideone

Related Images:

А709

24/05/2015 by Швандт Максим Альбертович

Условие:

Дана квадратная матрица [latex]A[/latex], порядка [latex]m[/latex], натуральное число [latex]n[/latex], действительные числа [latex]p_{n},p_{n-1},\ldots,p_{0}[/latex]. Получить матрицу [latex]p_{n}A^{n}+p_{n-1}A^{n-1}+\ldots p_{1}A+p_{0}E[/latex], где [latex]E[/latex]- единичная матрица порядка [latex]m[/latex].

Тесты:

Ввод количества p	Ввод размерности матрицы А и одновременно Е
6	3

Ввод коэффициентов

Матрица А:

1	2	3
3	2	1
2	1	3

Результат:

544308	445319	692718
544281	445354	692710
544277	445315	692753

Код:

#include <iostream>
#include <stdint.h>
#include <stdio.h>

using namespace std;

// класс, реализующий матрицу
class Matrix
{
   public:

      // конструктор по умолчанию
      Matrix()
      : mNumRows(0)
      , mNumCols(0)
      , mArr(0)
      {
      }

      // конструктор, создающий реальную матрицу ненулевой размерности и заполняет начальным значением
      Matrix( int numRows, int numCols, double initValue )
      : mNumRows( 0 )
      , mNumCols( 0 )
      , mArr( 0 )
      {
         initArr( numRows, numCols, initValue );
      }
      
      // конструктор копии - создающий матрицу как копию матрици-источника
      Matrix( Matrix& source )
      : mNumRows( source.mNumRows )
      , mNumCols( source.mNumCols )
      , mArr( 0 )
      {
         swap( source );
      }

      // деструктор, необходим для удаления выделенного на куче двумерного массива
      ~Matrix()
      {
         resetArr();
      }

      // переопределённый оператор присваивания, необходим для корректного присваивания матриц
      Matrix& operator=( Matrix& rhs )
      {
         swap( rhs );
      }

      // возвращает число строк в матрице
      int getNumRows() { return mNumRows; };

      // возвращает число колонок в матрице
      int getNumCols() { return mNumCols; };

      // возвращает указатель на двумерный массив на куче, содержащий саму матрицу
      double** getArr() { return mArr; };

      // копирует матрицу-источник в себя
      void swap( Matrix& another );

      // создает левую диагональ, заполненную заданным значением
      void setLeftDiag( double value );

      // суммирует другую матрицу с собой
      void sum( Matrix& another );

      // возводит себя в n-ю степень
      void power( int n );

      //выполняет произведение себя и другой матрицы, метод используется в методе power
      void product( Matrix& another );

      // умножает себя на заданное значение
      void multiply( double& value );

      // выводит на консоль содержимое себя, придворенное заголовком
      void show( const char* title );

      // создает заново свой двумерный массив и заполняет заданным значеним, исп. в конструкторе
      void initArr( int numRows, int numCols, double initValue );

      // удаляет двумерный массив из кучи и обнуляет указатель, исп. в деструкторе а также в initArr
      void resetArr();

   private:

      int mNumRows;
      int mNumCols;
      double** mArr;
};

void Matrix::swap( Matrix& another )
{
   initArr( another.mNumRows, another.mNumCols, 0 );
   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         mArr[ row ][ col ] = another.mArr[ row ][ col ];
      }
   }
}

void Matrix::setLeftDiag( double value )
{
   int n = min( mNumRows, mNumCols );
   for( int i = 0; i < n; i++ )
   {
      mArr[ i ][ i ] = value;
   }
}

void Matrix::sum( Matrix& another )
{
   int numRows = min( mNumRows, another.getNumRows() );
   int numCols = min( mNumCols, another.getNumCols() );

   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         mArr[ row ][ col ] += another.mArr[ row ][ col ];
      }
   }
}

void Matrix::power( int n )
{
   for( int i = 1; i < n; i++ )
   {
      product( *this );
   }
}

void Matrix::product( Matrix& another )
{

   if ( mNumCols != another.mNumRows )
   {
      printf( "*** Matrix::product: argument matrix is not complementary, production is impossible ***\n" );
      return;
   }

   Matrix result( mNumRows, another.mNumCols, 0 ); 

   for( int rowResult = 0; rowResult < result.mNumRows; rowResult++ )
   {
      for( int colResult = 0; colResult < result.mNumCols; colResult++ )
      {
         result.mArr[ rowResult ][ colResult ] = 0;
         for( int col = 0; col < mNumCols; col++ )
         {

            result.mArr[ rowResult ][ colResult ] +=
               ( mArr[ rowResult ][ col ] * another.mArr[ col ][ colResult ] );
         }
      }
   }

   swap( result );
} 

void Matrix::multiply( double& value )
{
   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         mArr[ row ][ col ] *= value;
      }
   }
}

void Matrix::show( const char* title )
{
   printf("%s:\n", title);

   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         printf("%10.04lf ", mArr[ row ][ col ] );
      }
      printf("\n");
   }
}

void Matrix::initArr( int numRows, int numCols, double initValue )
{
   resetArr();
   mNumRows = numRows;
   mNumCols = numCols;
   mArr = new double*[ mNumRows ]; // создает массив указателей на подмассивы колонок
   for( int row = 0; row < mNumRows; row++ )
   {
      mArr[ row ] = new double[ mNumCols ]; // создает подмассив колонок для данной строки
      for( int col = 0; col < mNumCols; col++ ) // заполняет подмассив колонок заданным значениям
      {
         mArr[ row ][ col ] = initValue;
      }
   }
}

void Matrix::resetArr()
{
   if ( mArr!= 0 )
   {
      for( int row = 0; row < mNumRows; row++ )
      {
         delete[] mArr[ row ];
      }
      delete [] mArr;
      mArr = 0;
   }
}

//==============================================================================

// ввыд с консоли какого либо целого числа
static int inputNumber( const char *title )
{
   int n = 0;

   printf("input %s:\n", title);

   if ( scanf("%d", &n ) <= 0 )
   {
      printf("error input of %s\n",title);
   }
   else
   if ( n <= 0 )
   {
      printf("wrong %s value, must be positive\n", title);
   }

   return n;
}

// ввод с консоли содержимого какой либо матрицы
static bool inputMatrixData( const char *title, Matrix& x )
{
   printf("input %dx%d %s:\n", x.getNumRows(), x.getNumCols(), title );

   for( int row = 0; row < x.getNumRows(); row++ )
   {
      for( int col = 0; col < x.getNumCols(); col++ )
      {
         double val = 0;
         if ( scanf("%lf", &val ) <= 0 )
         {
            printf("error input of %s\n",title);
            return false;
         }
         x.getArr()[ row ][ col ] = val;

      }
   }
   return true;
}

//==============================================================================

int main()
{
   int numIter = inputNumber( "Number of iterations 'n'" );
   int sizeA   = inputNumber( "matrix size 'm'" );

   if ( numIter <= 0 || sizeA <= 0 )
   {
      return 0;
   }

   Matrix mxP( 1, numIter, 0 ); // для хранения p_0, P_1, ... P_n
   if ( ! inputMatrixData( "P matrix values", mxP ) )
   {
      return 0;
   }

   Matrix mxA( sizeA, sizeA, 0 );
   if ( ! inputMatrixData( "A matrix values", mxA ) )
   {
      return 0;
   }

   Matrix mxE( sizeA, sizeA, 0 );
   mxE.setLeftDiag( 1 );

   // печатаем исходные данные перед вычислением
   mxE.show("============= matrix E ==============");
   mxP.show("============= matrix P ==============");
   mxA.show("============= matrix A ==============");

   Matrix s; // это будет общая сумма полинома

   s.swap( mxE );

   s.multiply( mxP.getArr()[0][0] ); // создает P_0*E, как начальное значение суммирования

   // главный цикл суммирования полинома
   for( int i = 1; i < numIter; i++ )
   {
    
      Matrix x;  // это будет временная матрица для вычисления одного слагаемого полинома (pow(A,i)*P_i*E)
      x.swap( mxA ); // копируем содержимое матрицы A

      x.power( i );  // возводим x в степень i, т.е. pow(A,i)

      x.multiply( mxP.getArr()[0][i] ); // умножаем x на коэфф. p_i , т.е. полуйчаем результат одного слогаемого (pow(A,i)*P_i)

      s.sum( x ); // накапливаем сумму полинома

   }

   s.show("============= result: ==============");// печатаем результат вычисления полинома
   
   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

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

#include <iostream>

#include <stdint.h>

#include <stdio.h>

using namespace std;

// класс, реализующий матрицу

class Matrix

{

public:

// конструктор по умолчанию

Matrix()

: mNumRows(0)

, mNumCols(0)

, mArr(0)

{

}

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

Matrix( int numRows, int numCols, double initValue )

: mNumRows( 0 )

, mNumCols( 0 )

, mArr( 0 )

{

initArr( numRows, numCols, initValue );

}

// конструктор копии - создающий матрицу как копию матрици-источника

Matrix( Matrix& source )

: mNumRows( source.mNumRows )

, mNumCols( source.mNumCols )

, mArr( 0 )

{

swap( source );

}

// деструктор, необходим для удаления выделенного на куче двумерного массива

~Matrix()

{

resetArr();

}

// переопределённый оператор присваивания, необходим для корректного присваивания матриц

Matrix& operator=( Matrix& rhs )

{

swap( rhs );

}

// возвращает число строк в матрице

int getNumRows() { return mNumRows; };

// возвращает число колонок в матрице

int getNumCols() { return mNumCols; };

// возвращает указатель на двумерный массив на куче, содержащий саму матрицу

double** getArr() { return mArr; };

// копирует матрицу-источник в себя

void swap( Matrix& another );

// создает левую диагональ, заполненную заданным значением

void setLeftDiag( double value );

// суммирует другую матрицу с собой

void sum( Matrix& another );

// возводит себя в n-ю степень

void power( int n );

//выполняет произведение себя и другой матрицы, метод используется в методе power

void product( Matrix& another );

// умножает себя на заданное значение

void multiply( double& value );

// выводит на консоль содержимое себя, придворенное заголовком

void show( const char* title );

// создает заново свой двумерный массив и заполняет заданным значеним, исп. в конструкторе

void initArr( int numRows, int numCols, double initValue );

// удаляет двумерный массив из кучи и обнуляет указатель, исп. в деструкторе а также в initArr

void resetArr();

private:

int mNumRows;

int mNumCols;

double** mArr;

};

void Matrix::swap( Matrix& another )

{

initArr( another.mNumRows, another.mNumCols, 0 );

for( int row = 0; row < mNumRows; row++ )

{

for( int col = 0; col < mNumCols; col++ )

{

mArr[ row ][ col ] = another.mArr[ row ][ col ];

}

void Matrix::setLeftDiag( double value )

{

int n = min( mNumRows, mNumCols );

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

{

mArr[ i ][ i ] = value;

}

void Matrix::sum( Matrix& another )

{

int numRows = min( mNumRows, another.getNumRows() );

int numCols = min( mNumCols, another.getNumCols() );

for( int row = 0; row < mNumRows; row++ )

{

for( int col = 0; col < mNumCols; col++ )

{

mArr[ row ][ col ] += another.mArr[ row ][ col ];

}

void Matrix::power( int n )

{

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

{

product( *this );

}

void Matrix::product( Matrix& another )

{

if ( mNumCols != another.mNumRows )

{

printf( "*** Matrix::product: argument matrix is not complementary, production is impossible ***\n" );

return;

}

Matrix result( mNumRows, another.mNumCols, 0 );

for( int rowResult = 0; rowResult < result.mNumRows; rowResult++ )

{

for( int colResult = 0; colResult < result.mNumCols; colResult++ )

{

result.mArr[ rowResult ][ colResult ] = 0;

for( int col = 0; col < mNumCols; col++ )

{

result.mArr[ rowResult ][ colResult ] +=

( mArr[ rowResult ][ col ] * another.mArr[ col ][ colResult ] );

}

swap( result );

}

void Matrix::multiply( double& value )

{

for( int row = 0; row < mNumRows; row++ )

{

for( int col = 0; col < mNumCols; col++ )

{

mArr[ row ][ col ] *= value;

}

void Matrix::show( const char* title )

{

printf("%s:\n", title);

for( int row = 0; row < mNumRows; row++ )

{

for( int col = 0; col < mNumCols; col++ )

{

printf("%10.04lf ", mArr[ row ][ col ] );

}

printf("\n");

}

void Matrix::initArr( int numRows, int numCols, double initValue )

{

resetArr();

mNumRows = numRows;

mNumCols = numCols;

mArr = new double*[ mNumRows ]; // создает массив указателей на подмассивы колонок

for( int row = 0; row < mNumRows; row++ )

{

mArr[ row ] = new double[ mNumCols ]; // создает подмассив колонок для данной строки

for( int col = 0; col < mNumCols; col++ ) // заполняет подмассив колонок заданным значениям

{

mArr[ row ][ col ] = initValue;

}

void Matrix::resetArr()

{

if ( mArr!= 0 )

{

for( int row = 0; row < mNumRows; row++ )

{

delete[] mArr[ row ];

}

delete [] mArr;

mArr = 0;

}

//==============================================================================

// ввыд с консоли какого либо целого числа

static int inputNumber( const char *title )

{

int n = 0;

printf("input %s:\n", title);

if ( scanf("%d", &n ) <= 0 )

{

printf("error input of %s\n",title);

}

else

if ( n <= 0 )

{

printf("wrong %s value, must be positive\n", title);

}

return n;

}

// ввод с консоли содержимого какой либо матрицы

static bool inputMatrixData( const char *title, Matrix& x )

{

printf("input %dx%d %s:\n", x.getNumRows(), x.getNumCols(), title );

for( int row = 0; row < x.getNumRows(); row++ )

{

for( int col = 0; col < x.getNumCols(); col++ )

{

double val = 0;

if ( scanf("%lf", &val ) <= 0 )

{

printf("error input of %s\n",title);

return false;

}

x.getArr()[ row ][ col ] = val;

}

return true;

}

//==============================================================================

int main()

{

int numIter = inputNumber( "Number of iterations 'n'" );

int sizeA = inputNumber( "matrix size 'm'" );

if ( numIter <= 0 || sizeA <= 0 )

{

return 0;

}

Matrix mxP( 1, numIter, 0 ); // для хранения p_0, P_1, ... P_n

if ( ! inputMatrixData( "P matrix values", mxP ) )

{

return 0;

}

Matrix mxA( sizeA, sizeA, 0 );

if ( ! inputMatrixData( "A matrix values", mxA ) )

{

return 0;

}

Matrix mxE( sizeA, sizeA, 0 );

mxE.setLeftDiag( 1 );

// печатаем исходные данные перед вычислением

mxE.show("============= matrix E ==============");

mxP.show("============= matrix P ==============");

mxA.show("============= matrix A ==============");

Matrix s; // это будет общая сумма полинома

s.swap( mxE );

s.multiply( mxP.getArr()[0][0] ); // создает P_0*E, как начальное значение суммирования

// главный цикл суммирования полинома

for( int i = 1; i < numIter; i++ )

{

Matrix x; // это будет временная матрица для вычисления одного слагаемого полинома (pow(A,i)*P_i*E)

x.swap( mxA ); // копируем содержимое матрицы A

x.power( i ); // возводим x в степень i, т.е. pow(A,i)

x.multiply( mxP.getArr()[0][i] ); // умножаем x на коэфф. p_i , т.е. полуйчаем результат одного слогаемого (pow(A,i)*P_i)

s.sum( x ); // накапливаем сумму полинома

}

s.show("============= result: ==============");// печатаем результат вычисления полинома

return 0;

}

Программа базируется на классе Matrix. Этот класс необходим для представления алгоритма вычисления полинома в естественной математической форме. Класс реализует следующие операции:

Создание матрицы заданного размера заполненной заданным числом
Умножение матрицы на число
Сложение матриц
Произведение матриц
Возведение матрицы в степень
Вывод содержимого матрицы на консоль

Класс Matrix содержит 3 члена – число строк, колонок и двумерный массив, который создается на куче. Главный модуль содержит две вспомогательный функции для ввода данных.

Основная часть программы состоит из следующих этапов:

Ввод данных: число итераций, размерности матрицы , списка коэфф. P и самой матрицы А
Создание единичной матрицы Е и далее – начального значения суммы E*P_0
Вывод исходных данных: E, A и P
Цикл суммирования, где вычисляется i-й элемент суммы
Вывод результата

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

Related Images:

А717б

24/05/2015 by Вустянюк Ігор Дмитрович

Условие

Две правые треугольные матрицы [latex] A [/latex] и [latex] B [/latex] порядка [latex] n [/latex] заданы в виде последовательности [latex] \frac{\left( n + 1 \right) n}{2}[/latex] чисел: сначала идёт [latex] n [/latex] элементов первой строки, затем [latex] n-1 [/latex] элемент второй строки, и т.д. (из последней, [latex] n [/latex] -ой строки берётся только [latex] n [/latex] -ый элемент). Нужно получить в аналогичном виде матрицу

б) [latex] A \left( I + B^{2} \right) [/latex], где [latex] I [/latex] — единичная матрица порядка [latex] n [/latex]

Тест

[latex] \begin{bmatrix} 2 & 2 & 2 \\ 0 & 0 & 3 \\ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix} = \begin{bmatrix} 4 & 54 & 236 \\
0 & 0 & 111 \\
0 & 0 & 37 \end{bmatrix} [/latex]

Решение

Создадим класс для работы с треугольными матрицами указанного вида и снабдим его основными методами, необходимыми для решения задачи.

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

Код на С++

#include <iostream>
#include <assert.h> 
#include <stdlib.h> 
using namespace std;

class TriMat {
    private:
        int Size;   
        int** M;
    public:
        TriMat(int n) {
            Size = n;
            M = (int**) malloc(Size * sizeof(int));
            for (int k = 0; k < Size; k++) {
                M[k] = (int*) malloc((Size - k) * sizeof(int));
                for (int j = 0; j <= Size - 1 - k; j++)
                    cin >> M[k][j];
            }
        }
        
        // Конструктор скалярной матрицы с заданным элементом на главной диагонали
        TriMat(int n, int a) {
            Size = n;
            M = (int**) malloc(Size * sizeof(int));
            for (int k = 0; k < Size; k++) {
                M[k] = (int*) malloc((Size - k) * sizeof(int));
                M[k][0] = a;
            }
        }
        
        void print() {
            for (int k = 0; k < Size; k++) {
                for (int j = 0; j < k; j++)
                    cout << "\t";
                for (int j = 0; j <= Size - 1 - k; j++)
                    cout << M[k][j] << "\t";
                cout << endl;
            }
        }
        
        int* operator[](size_t k) {
            assert(0 <= k && k < Size);
            return M[k];
        }
        
        void assign(int i, int j, int a) {
            assert(0 <= i && i < Size && 0 <= j && j < Size);
            M[i][j] = a;
        }
        
        int el(int i, int j) {
            assert(0 <= i && i < Size && 0 <= j && j < Size);
            return M[i][j];
        }

   
        TriMat operator+ (TriMat B) {
            TriMat C(Size);
            for (int k = 0; k < Size; k++)
                for (int j = 0; j <= Size - 1 - k; j++)
                    C[k][j] = M[k][j] + B[k][j];
            return C;
        }
        
        TriMat operator= (TriMat B) {
            for (int k = 0; k < Size; k++)
                for (int j = 0; j <= Size - 1 - k; j++)
                M[k][j] = B[k][j];
            return *this;
        }

        TriMat operator* (TriMat B) {
            TriMat C(Size);
            for (int k = 0; k < Size; k++)
                for (int j = k; j < Size; j++) {
                    for (int r = k; r <= j; r++)
                        C[k][j-k] += M[k][r-k] * B[r][j-r];
                }
            return C;
        }
};


int main() {
    int n;
    cin >> n;
    TriMat A(n), B(n), I(n,1), C = A * (I + B*B);
    A.print();
    B.print();
    C.print();
    return 0;
}

#include <iostream>

#include <assert.h>

#include <stdlib.h>

using namespace std;

class TriMat {

private:

int Size;

int** M;

public:

TriMat(int n) {

Size = n;

M = (int**) malloc(Size * sizeof(int));

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

M[k] = (int*) malloc((Size - k) * sizeof(int));

for (int j = 0; j <= Size - 1 - k; j++)

cin >> M[k][j];

}

// Конструктор скалярной матрицы с заданным элементом на главной диагонали

TriMat(int n, int a) {

Size = n;

M = (int**) malloc(Size * sizeof(int));

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

M[k] = (int*) malloc((Size - k) * sizeof(int));

M[k][0] = a;

}

void print() {

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

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

cout << "\t";

for (int j = 0; j <= Size - 1 - k; j++)

cout << M[k][j] << "\t";

cout << endl;

}

int* operator[](size_t k) {

assert(0 <= k && k < Size);

return M[k];

}

void assign(int i, int j, int a) {

assert(0 <= i && i < Size && 0 <= j && j < Size);

M[i][j] = a;

}

int el(int i, int j) {

assert(0 <= i && i < Size && 0 <= j && j < Size);

return M[i][j];

}

TriMat operator+ (TriMat B) {

TriMat C(Size);

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

for (int j = 0; j <= Size - 1 - k; j++)

C[k][j] = M[k][j] + B[k][j];

return C;

}

TriMat operator= (TriMat B) {

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

for (int j = 0; j <= Size - 1 - k; j++)

M[k][j] = B[k][j];

return *this;

}

TriMat operator* (TriMat B) {

TriMat C(Size);

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

for (int j = k; j < Size; j++) {

for (int r = k; r <= j; r++)

C[k][j-k] += M[k][r-k] * B[r][j-r];

}

return C;

}

};

int main() {

int n;

cin >> n;

TriMat A(n), B(n), I(n,1), C = A * (I + B*B);

A.print();

B.print();

C.print();

return 0;

}

Ideone (C++)

Код на Java

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

class Trimat {
    int Size;
    int[][] M;
    
    public Trimat(int n, Scanner in) {
        Size = n;
        M = new int[Size][];
        for (int k = 0; k < Size; k++) {
            M[k] = new int[Size - k];
            for (int j = 0; j < Size - k; j++)
                M[k][j] = in.nextInt();
        }
    }
    
    public Trimat(int n, int a) {
        Size = n;
        M = new int[Size][];
        for (int k = 0; k < Size; k++) {
            M[k] = new int[Size - k];
            M[k][0] = a;
        }
    }
    
    public void print() {
        for (int k = 0; k < Size; k++) {
            for (int j = 0; j < k; j++)
                System.out.print("\t");
            for (int j = 0; j < Size - k; j++)
                System.out.format("%d\t", M[k][j]);
            System.out.println();
        }
    }
    
    public Trimat add(Trimat B) {
        Trimat C = new Trimat(Size, 0);
        for (int k = 0; k < Size; k++)
            for (int j = 0; j < Size - k; j++)
                C.M[k][j] = M[k][j] + B.M[k][j];
        return C;
    }
    
    public Trimat mul(Trimat B) {
        Trimat C = new Trimat(Size, 0);
        for (int k = 0; k < Size; k++) 
            for (int j = k; j < Size; j++)
                for (int r = k; r <= j; r++)
                    C.M[k][j-k] += M[k][r-k] * B.M[r][j-r];
        return C;
    }
}

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        Trimat A = new Trimat(n, in), B = new Trimat(n, in);
        Trimat I = new Trimat(n,1);
        Trimat C = A.mul(I.add(B.mul(B)));
        A.print();
        B.print();
        C.print();
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Trimat {

int Size;

int[][] M;

public Trimat(int n, Scanner in) {

Size = n;

M = new int[Size][];

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

M[k] = new int[Size - k];

for (int j = 0; j < Size - k; j++)

M[k][j] = in.nextInt();

}

public Trimat(int n, int a) {

Size = n;

M = new int[Size][];

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

M[k] = new int[Size - k];

M[k][0] = a;

}

public void print() {

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

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

System.out.print("\t");

for (int j = 0; j < Size - k; j++)

System.out.format("%d\t", M[k][j]);

System.out.println();

}

public Trimat add(Trimat B) {

Trimat C = new Trimat(Size, 0);

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

for (int j = 0; j < Size - k; j++)

C.M[k][j] = M[k][j] + B.M[k][j];

return C;

}

public Trimat mul(Trimat B) {

Trimat C = new Trimat(Size, 0);

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

for (int j = k; j < Size; j++)

for (int r = k; r <= j; r++)

C.M[k][j-k] += M[k][r-k] * B.M[r][j-r];

return C;

}

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

Trimat A = new Trimat(n, in), B = new Trimat(n, in);

Trimat I = new Trimat(n,1);

Trimat C = A.mul(I.add(B.mul(B)));

A.print();

B.print();

C.print();

}

Ideone (Java)

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:

А717а

20/05/2015 by Денисова Ольга

Задача

Две правые треугольные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex] заданы в виде последовательности [latex]\frac{\left(n+1\right)*n}{2}[/latex] чисел: сначала идет [latex]n[/latex] элементов первой строки, затем [latex]n-1[/latex] элемент второй строки, начиная со второго элемента, и т. д. (из последней, [latex]n[/latex]-й строки берется только [latex]n[/latex]-й элемент).

Получить матрицу [latex]A*B[/latex].

Тесты

матрица A

матрица B

результат (матрица A*B)

комментарий

1 2

4 5

4 17

0 18

пройден

1 -1 2

4 6

1 -1 1

0 0

1 -1 7

0 0 15

0 0 18

пройден

Решение

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

Умножение выполнимо, потому что оба сомножителя — квадратные матрицы одного и того же порядка. Перемножаем матрицы стандартным способом (строки первой матрицы на столбцы второй).

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int a[n][n];
	int b[n][n];
	int res[n][n];
	//обнуляем все массивы
	for(int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			a[i][j] = 0;
			b[i][j] = 0;
			res[i][j] = 0;
		}
	}
	//ввод матрицы A
	for(int i = 0; i < n; i++) {
		for(int j = 0;  i + j < n; j++) {
			cin >> a[i][i+j];
		}
	}
	//ввод матрицы B
	for(int i = 0; i < n; i++) {
		for(int j = 0;  i + j < n; j++) {
			cin >> b[i][i+j];
		}
	}
	//перемножаем матрицы
	for(int i = 0; i < n; i++) {
		for(int j = 0; i + j < n; j++) {
			for(int k = 0; k < n; k ++) {
				res[i][i+j] += a[i][k]*b[k][i+j];
			}
		}
	}
	//выводим результат
	for(int i = 0; i < n; i++) {
			for(int j = 0;  j < n; j++) {
				cout << res[i][j] << "  ";
			}
			cout << endl;
		}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int a[n][n];

int b[n][n];

int res[n][n];

//обнуляем все массивы

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

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

a[i][j] = 0;

b[i][j] = 0;

res[i][j] = 0;

}

//ввод матрицы A

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

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

cin >> a[i][i+j];

}

//ввод матрицы B

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

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

cin >> b[i][i+j];

}

//перемножаем матрицы

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

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

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

res[i][i+j] += a[i][k]*b[k][i+j];

}

//выводим результат

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

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

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

}

cout << endl;

}

return 0;

}

Ссылка на код.

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:

А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:

A708

17/05/2015 by Фесенко Катерина Володимирівна

Задача

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

Код на языке С++:

#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;
}

#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:

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();
		}
	}
}

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], добавляем к результирующей и заменяем вспомогательную матрицу. В завершении мы прибавим единичную матрицу к ответы и выведем его.

Related Images:

А710

17/05/2015 by Зелінський Вячеслав Олександрович

Дана матрица A размера [latex]m*n[/latex]. Получить транспонированную матрицу A*(ее размер [latex]n*m[/latex]).

А*

7 5 3 2

7 8 9 6

2 3 2 4

9 5 3 0

6 3 7 8

7 7 2 9 6

5 8 3 5 3

3 9 2 3 7

2 6 4 0 8

6 7 8 5 3 4
6 8 9 0 5 3
8 7 9 7 3 2
4 6 5 7 8 5
4 5 6 7 9 3

6 7 8 5 3 4

6 8 9 0 5 3

8 7 9 7 3 2

4 6 5 7 8 5

4 5 6 7 9 3

6 6 8 4 4

7 8 7 6 5

8 9 9 5 6

5 0 7 7 7

3 5 3 8 9

4 3 2 5 3

6 7 8

6 8 9

8 7 9

7 8 3

6 6 8 7 
7 8 7 8 
8 9 9 3

6 6 8 7

7 8 7 8

8 9 9 3

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

#include <iostream>
using namespace std;
 
int main() {
 
	int n, m;
	cin>>n>>m;
	int M[n][m]; 
	for(int i=0; i<n; i++) {
	     for(int j=0; j<m; j++) {
		       cin >> M[i][j];  
         }
	}
	int M1[m][n];
 
	for(int i=0; i<m; i++) {
	     for(int j=0; j<n; j++) {
		       M1[i][j]=M[j][i];
	     }
	}
    for(int i=0; i<m; i++) {
         for(int j=0; j<n; j++) {
	         cout<<M1[i][j]<<" ";
	     }
         cout<<endl;
    }
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin>>n>>m;

int M[n][m];

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

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

cin >> M[i][j];

}

int M1[m][n];

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

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

M1[i][j]=M[j][i];

}

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

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

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

}

cout<<endl;

}

return 0;

}

Считываем матрицу [latex]n*m[/latex], а затем создаем транспонированную матрицу, в которой строки исходной матрицы являются столбцами и наоборот. Выводим A*.

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

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, m;
		n = in.nextInt(); 
		m = in.nextInt(); 
		int [][]M = new int [n][m]; 
		for(int i=0; i<n; i++) {
		     for(int j=0; j<m; j++) {
			       M[i][j] = in.nextInt();  
	         }
		}
		int [][]M1 = new int [m][n]; 
		for(int i=0; i<m; i++) {
		     for(int j=0; j<n; j++){
			       M1[i][j]=M[j][i];
		     }
		}
		
	    for(int i=0; i<m; i++) {
	         for(int j=0; j<n; j++) {
		         System.out.println(M1[i][j]);
		     }
	         System.out.println("\n");
	    }
			
	}
}

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, m;

n = in.nextInt();

m = in.nextInt();

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

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

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

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

}

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

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

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

M1[i][j]=M[j][i];

}

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

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

System.out.println(M1[i][j]);

}

System.out.println("\n");

}

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:

A701a

14/05/2015 by Бровко Ілля

Задача

Даны квадратная матрица [latex]A[/latex] порядка [latex]n[/latex] и вектор [latex]b[/latex] с [latex]n[/latex] элементами. Получить вектор:
a) [latex]Ab[/latex];

Размерность
матрицы

Матрица

Вектор

Результирующий
вектор

1	2
3	4

3	2	6
3	2	1
5	3	8

1	2	3	4
5	6	7	8
9	0	1	2
3	4	5	6

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

115

290

465

640

815

Алгоритм действия достаточно прост:
Вводим размерность матрицы. Потом в цикле вводим саму матрицу. Вводим вектор. Далее идет сам алгоритм матрично-векторного произведения.

Последовательный алгоритм умножения матрицы на вектор может быть представлен следующим образом. Исходные данные: [latex]A[n][m][/latex] – матрицы размерности [latex]n[/latex]× [latex]m[/latex] . [latex]B[m][/latex] – вектор, состоящий из [latex]m[/latex] элементов. Результат: [latex]rezult[n][/latex] – вектор из [latex]n[/latex] элементов.

// Поcледовательный алгоритм умножения матрицы на вектор
for(int i=0; i<n; i++)
	{
		rezult[i]=0;							
		for(int j=0; j<m; j++)
		{
			rezult[i]+=A[i][j]*B[j];		
		}
	}

// Поcледовательный алгоритм умножения матрицы на вектор

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

{

rezult[i]=0;

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

{

rezult[i]+=A[i][j]*B[j];

}

Матрично-векторное умножение – это последовательность вычисления скалярных произведений. Поскольку каждое вычисление скалярного произведения векторов длины [latex]m[/latex] требует выполнения [latex]m[/latex] операций умножения и [latex]m-1[/latex] операций сложения, его трудоемкость порядка [latex]O(m)[/latex]. Для выполнения матрично-векторного умножения необходимо выполнить [latex]n[/latex] операций вычисления скалярного произведения, таким образом, алгоритм имеет трудоемкость порядка [latex]O(nm)[/latex].

Ниже представлен сам код (C++).

#include <iostream>
using namespace std;
 
int main() 
{
	size_t n,m;									
	cin>>n;										//Ввод размерности матрицы;
	m=n;
	int A[n][m],B[m],rezult[n];
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
		{
			cin>>A[i][j];						//Ввод самой матрицы;
		}
	}
	for(int j=0; j<m; j++)
	{
		cin>>B[j];								//Ввод вектора
	}
	for(int i=0; i<n; i++)
	{
		rezult[i]=0;							
		for(int j=0; j<m; j++)
		{
			rezult[i]+=A[i][j]*B[j];			//Последовательный алгоритм умножения матрицы на вектор;		
		}
	}
	for(int i=0; i<n; i++)
	{
		cout << rezult[i] << endl;				//Вывод результирующего вектора;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

size_t n,m;

cin>>n; //Ввод размерности матрицы;

m=n;

int A[n][m],B[m],rezult[n];

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

{

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

{

cin>>A[i][j]; //Ввод самой матрицы;

}

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

{

cin>>B[j]; //Ввод вектора

}

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

{

rezult[i]=0;

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

{

rezult[i]+=A[i][j]*B[j]; //Последовательный алгоритм умножения матрицы на вектор;

}

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

{

cout << rezult[i] << endl; //Вывод результирующего вектора;

}

return 0;

}

Код на Java:

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

class Brovko
{
	public static void main (String[] args) throws java.lang.Exception
	{
	Scanner in = new Scanner(System.in);		//Ввод размерности матрицы;
	int n=in.nextInt();
	int[][] A= new int[n][n];
	int[] B= new int[n];
	int[] rezult= new int[n];
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{
			A[i][j]=in.nextInt();						//Ввод самой матрицы;
		}
	}
	for(int j=0; j<n; j++)
	{
		B[j]=in.nextInt();								//Ввод вектора
	}
	for(int i=0; i<n; i++)
	{
		rezult[i]=0;							
		for(int j=0; j<n; j++)
		{
			rezult[i]+=A[i][j]*B[j];			//Последовательный алгоритм умножения матрицы на вектор;		
		}
	}
	for(int i=0; i<n; i++)
	{
		System.out.print(" ");
		System.out.format("%d",rezult[i]);			//Вывод результирующего вектора;
	}
}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Brovko

{

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

{

Scanner in = new Scanner(System.in); //Ввод размерности матрицы;

int n=in.nextInt();

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

int[] B= new int[n];

int[] rezult= new int[n];

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

{

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

{

A[i][j]=in.nextInt(); //Ввод самой матрицы;

}

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

{

B[j]=in.nextInt(); //Ввод вектора

}

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

{

rezult[i]=0;

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

{

rezult[i]+=A[i][j]*B[j]; //Последовательный алгоритм умножения матрицы на вектор;

}

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

{

System.out.print(" ");

System.out.format("%d",rezult[i]); //Вывод результирующего вектора;

}

Также, Вы можете воспользоваться ссылкой (C++)/ссылкой (Java) на саму программу.

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].

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.

Related Images:

А702б

13/05/2015 by Кваша Дар`я Михайлівна

Задача. Дана квадратная матрица порядка n. Получить вектор Ab, где b-вектор, элементы которого вычисляются по формулам:

[latex]b_{i}=\begin{cases}\frac{1}{i^{2}+2} & \text{, if i mod 2=0} \\ \frac{1}{i} & \text{, other case } \end{cases}[/latex]

i=(1,…,n).

Тесты:

Вход	Выход	Комментарий
4 1 2 1 1 1 3 6 9 1 2 1 1 1 6 3 18	1.72222 4 1.72222 4	Пройден
3 0 0 0 1 1 1 2 2 2	0 1.5 3	Пройден
4 1 2 2 9 3 4 1 18 1 1 1 1 0 0 0 0	2.5 5 1.55556 0	Пройден

#include <iostream>
using namespace std;

int main()
{
	int n;
	cin>>n;
	double b[n];
	for (int i=0; i<n; i++)
	{
            if((i+1)%2==0) b[i]=1.0/((i+1)*(i+1) + 2);
	    else b[i]=1.0/(i+1);
        }

	double A[n][n];
	for (int i=0; i<n; i++)
	    for (int j=0; j<n; j++)
	        cin>>A[i][j];
        double Ab[n];
        for (int i=0; i<n; i++)
        {   
    	   Ab[i]=0;
    	   for (int j=0; j<n; j++)
    	   {
    		Ab[i]+=A[i][j]*b[j];
    	   }
        }
        for (int i=0; i<n; i++)
        cout<<Ab[i]<<" ";
 
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin>>n;

double b[n];

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

{

if((i+1)%2==0) b[i]=1.0/((i+1)*(i+1) + 2);

else b[i]=1.0/(i+1);

}

double A[n][n];

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

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

cin>>A[i][j];

double Ab[n];

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

{

Ab[i]=0;

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

{

Ab[i]+=A[i][j]*b[j];

}

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

cout<<Ab[i]<<" ";

return 0;

}

Решение:

Согласно условию находим вектор b. По формуле [latex]Ab_{i}=\sum_{j=1}^{n}A_{ij}b_{j}[/latex], i=(0,…,n) находим произведение матрицы на вектор.

С работой программы можно ознакомится здесь.

Related Images:

e-olimp 4000. Обход в глубину

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

Задача e-olimp 4000

Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности (включая саму вершину).

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

В первой строке содержится два целых числа [latex]n[/latex] и [latex]s[/latex] [latex](1\leq s\leq n\leq 100)[/latex], где [latex]n[/latex] — количество вершин графа, а [latex]s[/latex] — выделенная вершина. В следующих [latex]n[/latex] строках записано по [latex]n[/latex] чисел — матрица смежности графа, в которой цифра «0» означает отсутствие ребра между вершинами, а цифра «1» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

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

Выведите одно число — искомое количество вершин.

Пример:

Входные данные	Выходные данные
5 1	3
0 1 1 0 0
1 0 1 0 0
1 1 0 0 0
0 0 0 0 1
0 0 0 1 0

Решение

#include <iostream>
#include <stack>
using namespace std;

int main()
	{
		int n;
		int s;
		cin>>n>>s;
		s--;
		int matrix[n][n];
		stack<int> st;
		int counter=1;
		for(int i=0;i<n;i++)
			{
				for(int j=0;j<n;j++)
					{
						cin>>matrix[i][j];
					}
			}
		for(int j=0;j<n;j++)
			{
				if(matrix[s][j] == 1) st.push(j);
			}
		matrix[s][s]=1;
		while(!st.empty())
			{
				int a=st.top();
				st.pop();
				if(matrix[a][a]!=1)
					{
						for(int j=0;j<n;j++)
							{
								if(matrix[a][j] == 1) st.push(j);
							}
						counter++;
						matrix[a][a]=1;
					}
				
			}
		cout<<counter<<endl;
	}

#include <iostream>

#include <stack>

using namespace std;

int main()

{

int n;

int s;

cin>>n>>s;

s--;

int matrix[n][n];

stack<int> st;

int counter=1;

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

{

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

{

cin>>matrix[i][j];

}

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

{

if(matrix[s][j] == 1) st.push(j);

}

matrix[s][s]=1;

while(!st.empty())

{

int a=st.top();

st.pop();

if(matrix[a][a]!=1)

{

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

{

if(matrix[a][j] == 1) st.push(j);

}

counter++;

matrix[a][a]=1;

}

cout<<counter<<endl;

}

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

class Ideone
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
        int n = in.nextInt(), s = in.nextInt()-1, counter = 1;
		int[][] matrix = new int[n][n];
		Stack st = new Stack();
		for(int i = 0;i < n; i++)
			{
				for(int j = 0;j < n; j++)
					{
						matrix[i][j] = in.nextInt();
					}
			}
		for(int j = 0; j < n; j++)
			{
				if(matrix[s][j] == 1) st.push(j);
			}
		matrix[s][s] = 1;
		while(!st.empty())
			{
				int a = (int) st.peek();
				st.pop();
				if(matrix[a][a] != 1)
					{
						for(int j = 0; j < n; j++)
							{
								if(matrix[a][j] == 1) st.push(j);
							}
						counter++;
						matrix[a][a] = 1;
					}
				
			}
		System.out.println(counter);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), s = in.nextInt()-1, counter = 1;

int[][] matrix = new int[n][n];

Stack st = new Stack();

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

{

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

{

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

}

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

{

if(matrix[s][j] == 1) st.push(j);

}

matrix[s][s] = 1;

while(!st.empty())

{

int a = (int) st.peek();

st.pop();

if(matrix[a][a] != 1)

{

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

{

if(matrix[a][j] == 1) st.push(j);

}

counter++;

matrix[a][a] = 1;

}

System.out.println(counter);

}

Вводим данные, затем в первом цикле проверяем строку [latex]s[/latex], и записываем в стек все вершины инцидентные данной. Так как в условии гарантируется наличие на главной диагонали нулей, то будем помечать проверенные вершины с помощью элемента расположенного на главной диагонали (то есть будем присваивать ему значение отличное от 0, к примеру 1). После будем проверять все строки в стеке до его опустошения, и увеличивать счётчик на единицу после удаления из стека не помеченной вершины.

Код на ideone.

Засчитанное решение.

Related Images:

e-olimp 5080. Количество висячих вершин 1

29/04/2015 by Марченко Філіп Олександрович

Код:

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

int gr[1001][1001]; // матрица смежности
int n; //кол-во вершин
	
//Просматривая матрицу смежности, подсчитываем кол-во единиц, т.е кол-во
//инцидентных вершин данной вершине. Инцидентные вершины - вершины, которые соединены ребром. Степенью вершины называется кол-во рёбер, инцидентных этой вершине.
//Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице 
//только одна единица, то вершина имеет степень 1 и является висячей.

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	int ans = 0; //предположим, что граф не имеет висячих вершин 
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
			cin >> gr[i][j];	//ввод матрицы смежности
	for (int i=0; i<n; i++){
		int cnt = 0; //счётчик
		for (int j=0; j<n; j++){
			if (gr[i][j] == 1) cnt++;  //подсчёт степени
		}
		if (cnt==1) ans++;  //проверка на висячую вершину
	}
	cout << ans << endl;	//вывод ответа
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int gr[1001][1001]; // матрица смежности

int n; //кол-во вершин

//Просматривая матрицу смежности, подсчитываем кол-во единиц, т.е кол-во

//инцидентных вершин данной вершине. Инцидентные вершины - вершины, которые соединены ребром. Степенью вершины называется кол-во рёбер, инцидентных этой вершине.

//Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице

//только одна единица, то вершина имеет степень 1 и является висячей.

int main() {

ios::sync_with_stdio(false);

cin >> n;

int ans = 0; //предположим, что граф не имеет висячих вершин

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

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

cin >> gr[i][j]; //ввод матрицы смежности

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

int cnt = 0; //счётчик

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

if (gr[i][j] == 1) cnt++; //подсчёт степени

}

if (cnt==1) ans++; //проверка на висячую вершину

}

cout << ans << endl; //вывод ответа

return 0;

}

Related Images:

А410е

25/12/2014 by Носуленко Марк

Дана целочисленная матрица [latex][a_{ij}], ij=1,\ldots,n.[/latex] Получить [latex]b_{1},\ldots,b_{n}[/latex], где [latex]b_{i}[/latex] — это: [latex]\underset{1\leq j\leq n}{\max a_{ij}}\cdot \underset{1\leq j\leq n}{\min a_{ji}}[/latex].

Исходя из задачи ясно, что из данной матрицы надо взять максимальный элемент [latex]i[/latex]-й строки и умножить его на минимальный элемент [latex]i[/latex]-го столбца. Так например, если нам дана матрица 2-го порядка [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] то [latex]b_{1}= 2[/latex], [latex]b_{2}= 4[/latex].

Для нахождения максимума [latex]a_{ij}[/latex], введем переменную и будем придавать ей начальное значение 1-го элемента [latex]i[/latex]-й строки. Дабы при расчете максимума проходя по элементам строки мы не сравнивали каждый [latex]i[/latex]-й элемент с 1-м, придавать начальное значение максимуму мы будем в цикле по [latex]i[/latex]. Аналогично с минимумом [latex]a_{ji}[/latex], одно единственное но, начальное значение минимума будет равно первому элементу [latex]i[/latex]-го столбца.

Тесты:

Матрица порядка [latex]n[/latex], где [latex]n[/latex]:	[latex]a[i][j][/latex]:	Результат:	Комментарий:
2	[latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex]	2 4	Пройден.
3	[latex]\begin{Vmatrix}1&2&3\\4&1&-6\\1&-2&-1\end{Vmatrix}[/latex]	3 -8 -6	Пройден.

#include <iostream>
using namespace std;
int main() {
    int n,maxa,mina;
    cin >>n;
    int a[n][n];
    for(int i=0; i<n;++i){
        for(int j=0;j<n;++j){
            cin >>a[i][j];
        }
    }
    int b[n];
    for(int i=0;i<n;++i){
        maxa=a[i][0]; //Придаем максимуму значение первого элемента i-й строки.
        mina=a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца.
        for(int j=0;j<n;++j){
            maxa=(maxa>a[i][j]?maxa:a[i][j]); //Вычисляем максимум i-й строки.
            mina=(mina<a[j][i]?mina:a[j][i]); //Минимум i-го столбца.
        }
        b[i]=maxa*mina; //Наш результат.
    }   for(int i=0;i<n;++i){
        cout <<b[i]<<" ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,maxa,mina;

cin >>n;

int a[n][n];

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

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

cin >>a[i][j];

}

int b[n];

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

maxa=a[i][0]; //Придаем максимуму значение первого элемента i-й строки.

mina=a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца.

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

maxa=(maxa>a[i][j]?maxa:a[i][j]); //Вычисляем максимум i-й строки.

mina=(mina<a[j][i]?mina:a[j][i]); //Минимум i-го столбца.

}

b[i]=maxa*mina; //Наш результат.

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

cout <<b[i]<<" ";

}

return 0;

}

Ссылка на код.