Задача о порядке перемножения матриц - 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();
        }
    }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 3.857 из 5
Похожие ответы