Алгоритм Штрассена на C#
Пишу курсовую работу по дисциплине Алгоритмы и структуры данных. Тема курсовой Алгоритм Штрассена. Ниже прикреплю код. Мой преподаватель не принимает такой код и просит не порождать новый матрицы, не заниматься пустопорожним копированием блоков из одного места памяти в другое, а также добавил "Примером является бинарный поиск в упорядоченном массиве. Там коллекция тоже разделяется, но не на физическом уровне, а посредством указания индексов левой и правой границ. В твоей программе надо разделять матрицу путём указания четырёх индексов: лев, верх, прав, низ. Например, ты можешь в функции Add и Sub передавать не скопированные блоки, а четыре индекса исходной матрицы." Прошу помочь исправить мой код под его требования. Код:
using System;
using System.Diagnostics;
class Program
{
static int[,] Strassen(int[,] A, int[,] B, int blockSize)
{
int n = A.GetLength(0);
int[,] C = new int[n, n];
if (n == 1)
{
C[0, 0] = A[0, 0] * B[0, 0];
}
else
{
int halfSize = n / 2;
int[,] A11 = GetSubMatrix(A, 0, 0, halfSize);
int[,] A12 = GetSubMatrix(A, 0, halfSize, halfSize);
int[,] A21 = GetSubMatrix(A, halfSize, 0, halfSize);
int[,] A22 = GetSubMatrix(A, halfSize, halfSize, halfSize);
int[,] B11 = GetSubMatrix(B, 0, 0, halfSize);
int[,] B12 = GetSubMatrix(B, 0, halfSize, halfSize);
int[,] B21 = GetSubMatrix(B, halfSize, 0, halfSize);
int[,] B22 = GetSubMatrix(B, halfSize, halfSize, halfSize);
int[,] P1 = Strassen(AddMatrix(A11, A22), AddMatrix(B11, B22), blockSize);
int[,] P2 = Strassen(AddMatrix(A21, A22), B11, blockSize);
int[,] P3 = Strassen(A11, SubMatrix(B12, B22), blockSize);
int[,] P4 = Strassen(A22, SubMatrix(B21, B11), blockSize);
int[,] P5 = Strassen(AddMatrix(A11, A12), B22, blockSize);
int[,] P6 = Strassen(SubMatrix(A21, A11), AddMatrix(B11, B12), blockSize);
int[,] P7 = Strassen(SubMatrix(A12, A22), AddMatrix(B21, B22), blockSize);
int[,] C11 = AddMatrix(SubMatrix(AddMatrix(P1, P4), P5), P7);
int[,] C12 = AddMatrix(P3, P5);
int[,] C21 = AddMatrix(P2, P4);
int[,] C22 = AddMatrix(SubMatrix(AddMatrix(P1, P3), P2), P6);
SetSubMatrix(C11, C, 0, 0);
SetSubMatrix(C12, C, 0, halfSize);
SetSubMatrix(C21, C, halfSize, 0);
SetSubMatrix(C22, C, halfSize, halfSize);
}
return C;
}
static int[,] AddMatrix(int[,] A, int[,] B)
{
int n = A.GetLength(0);
int[,] C = new int[n, n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
C[i, j] = A[i, j] + B[i, j];
}
}
return C;
}
static int[,] SubMatrix(int[,] A, int[,] B)
{
int n = A.GetLength(0);
int[,] C = new int[n, n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
C[i, j] = A[i, j] - B[i, j];
}
}
return C;
}
static int[,] GetSubMatrix(int[,] matrix, int rowStart, int colStart, int size)
{
int[,] submatrix = new int[size, size];
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
submatrix[i, j] = matrix[rowStart + i, colStart + j];
}
}
return submatrix;
}
static void SetSubMatrix(int[,] submatrix, int[,] matrix, int rowStart, int colStart)
{
for (int i = 0; i < submatrix.GetLength(0); i++)
{
for (int j = 0; j < submatrix.GetLength(1); j++)
{
matrix[rowStart + i, colStart + j] = submatrix[i, j];
}
}
}
static void Main()
{
Console.WriteLine("Введите значение n для (2^n):");
int n = Convert.ToInt32(Console.ReadLine());
int size = (int)Math.Pow(2, n);
Random rand = new Random();
int[,] A = new int[size, size];
int[,] B = new int[size, size];
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
A[i, j] = rand.Next(1, 10);
B[i, j] = rand.Next(1, 10);
}
}
Console.WriteLine("Матрица A:");
PrintMatrix(A);
Console.WriteLine("Матрица B");
PrintMatrix(B);
Console.WriteLine("Результат умножения матриц: ");
PrintMatrix(Strassen(A, B, size));
}
static void PrintMatrix(int[,] matrix)
{
for (int i = 0; i < matrix.GetLength(0); i++)
{
for (int j = 0; j < matrix.GetLength(1); j++)
{
Console.Write(matrix[i, j] + " ");
}
Console.WriteLine();
}
}
}