Задача о порядке перемножения матриц - C#
Формулировка задачи:
Алгоритм здесь https://ru.wikipedia.org/wiki/%D0%97...80%D0%B8%D1%86
Сам алгоритм понятен, но непонятна реализация как бы глупо это не звучало.
Пробовал сделать вот так
Но что-то не получается и не работает. Подскажите что исправить. Заранее благодарен.
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace matrixchainconsole { public class DataStore { public List<List<int>> m; //матрица m public List<List<int>> s; //матрица s public List<List<int>> result=new List<List<int>>(); //результат всех перемножений public List<List<List<int>>> source=new List<List<List<int>>>(); //массив из 2-мерных матриц (A0,A1,...,An) которые нужно перемножить public List<int> sizes = new List<int>(); //размеры матриц (записаны таким образом - 12,10,7,4 => значит 3 матрицы размерами 12x10,10x7,7x4) public string order = new string('a', 0); //правильное расположение скобок public DataStore(List<int> l) { sizes = l; } } public class Class { public DataStore dataStore; public Class(DataStore d) { dataStore = d; } public void matrixChainOrder() { int n = dataStore.sizes.Count - 1; //выделяем память под матрицы m и s dataStore.m = new List<List<int>>(); dataStore.s = new List<List<int>>(); for (int i = 0; i < n; i++) { dataStore.m.Add(new List<int>()); dataStore.s.Add(new List<int>()); //заполняем нулевыми элементами for (int a = 0; a < n; a++) { dataStore.m[i].Add(0); dataStore.s[i].Add(0); } } //выполняем итерационный алгоритм int j; for (int l = 1; l < n; l++) for (int i = 0; i < n - l; i++) { j = i + l; dataStore.m[i][j] = int.MaxValue; for (int k = i; k < j; k++) { int q = dataStore.m[i][k] + dataStore.m[k + 1][j] + dataStore.sizes[i] * dataStore.sizes[k + 1] * dataStore.sizes[j + 1]; if (q < dataStore.m[i][j]) { dataStore.m[i][j] = q; dataStore.s[i][j] = k; } } } } //метод - простое перемножение 2-х матриц public List<List<int>> matrixMultiply(List<List<int>> A, List<List<int>> B) { int rowsA = A.Count; int columnsB = B[0].Count; //column count of A == rows count of B int columnsA = B.Count; //memory alloc for "c" List<List<int>> c = new List<List<int>>(); for (int i = 0; i < rowsA; i++) { c.Add(new List<int>()); for (int a = 0; a < columnsB; a++) { c[i].Add(0); } } //do multiplying for (int i = 0; i < rowsA; i++) for (int j = 0; j < columnsB; j++) for (int k = 0; k < columnsA; k++) c[i][j] += A[i][k] * B[k][j]; //return value return c; } //метод, который непосредственно выполняет перемножение в правильном порядке //первоначально вызывается таким образом //dataStore.result = matrixChainMultiply(0, dataStore.sizes.Count - 2); public List<List<int>> matrixChainMultiply(int i, int j) { if (j > i) { List<List<int>> x = matrixChainMultiply(i, dataStore.s[i][j]); List<List<int>> y = matrixChainMultiply(dataStore.s[i][j] + 1, j); return matrixMultiply(x, y); } else return dataStore.source[i]; } //метод печатающий строку с правильной расстановкой скобок public void printOrder(int i, int j) { if (i == j) dataStore.order += "A" + i.ToString(); else { dataStore.order += "("; printOrder(i, dataStore.s[i][j]); dataStore.order += "*"; printOrder(dataStore.s[i][j] + 1, j); dataStore.order += ")"; } } } class Program { static void Main(string[] args) { List<int> list = new List<int>(); list.Add(12); list.Add(10); list.Add(7); list.Add(4); DataStore d=new DataStore(list); Class c = new Class(d); c.matrixChainOrder(); c.dataStore.result= c.matrixChainMultiply(0,c.dataStore.sizes.Count-2); } } }
Решение задачи: «Задача о порядке перемножения матриц»
textual
Листинг программы
class Program { static void Main(string[] args) { List<int> list = new List<int>(); list.Add(12); list.Add(10); list.Add(7); list.Add(4); DataStore d = new DataStore(list); Class c = new Class(d); c.matrixChainOrder(); c.printOrder(0, 2); Console.WriteLine(d.order); //c.dataStore.result = c.matrixChainMultiply(0, c.dataStore.sizes.Count - 2); Console.ReadLine(); } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д