Реализации алгоритмов/Задача о перемножении цепочки матриц

Реализация задачи о перемножении цепочки матриц на разных языках программирования.

C++

 
#include <iostream>
#include <vector>

using namespace std;

const int INT_INF = 1e7+3;

void print_optimal_parens(vector<vector<int>> &s, int i, int j)
{
    if(i == j) cout<<"A_i";
    else {
        cout<<"(";
        print_optimal_parens(s, i, s[i][j]);
        print_optimal_parens(s, s[i][j] + 1, j);
        cout<<")";        
    }
}

int main() {
    vector<int> p;
    int p_cur;
    while(cin>>p_cur) p.push_back(p_cur);
    int n = p.size() - 1;
    vector<vector<int>> m(n + 1, vector<int> (n + 1, INT_INF));
    vector<vector<int>> s(n + 1, vector<int> (n + 1, INT_INF));

    for(int i = 1; i <= n; i++) m[i][i] = 0; //минимальное количество скалярных умножений матрицы самой на себя 0

    for(int l = 2; l <= n; l++) { //длина цепочки
        for(int i = 1; i <= (n - l + 1); i++) {
            int j = i + l - 1;
            m[i][j] = INT_INF;
            for(int k = i; k <= (j - 1); k++) {
                int q = m[i][k] + m[k + 1][j] + p[i - 1]*p[k]*p[j];
                if (q < m[i][j]) {
                    m[i][j] = q;
                } else {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }

    //Ответ
    cout<<m[1][n]<<"\n";

    //Восстановление ответа
    print_optimal_parens(s, 1, n);
}