3 level task

[derzhavin3016]

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

Предположим у вас есть матрица A размера 10 × 30, B размера 30 × 5 и C размера 5 × 60.

Вычисление их произведения как A(BC) займёт (30×5×60) + (10×30×60) = 27000 операций умножения. В то же время, их произведение как (AB)C даст тот же результат за 4500 операций.

Ваша задача -- написать класс MatrixChain, позволяющий:

1. Добавить матрицу в цепочку
2. Распечатать оптимальный порядок перемножения текущей цепочки матриц
3. Выполнить перемножение в оптимальном порядке для тестов производительности
4. Показать очевидное превосходство над наивным подходом

Стек матриц может поддерживаться динамически и быть достаточно большим -- тесты на цепочки из 10-20 и более матриц приветствуются.

В выборе оптимальной цепочки должен помочь метод динамического программирования

Входные данные: пары размеров матриц, например

30 35
35 15
15 5
5 10

Выход: оптимальный порядок, например 0 1 2 это порядок по умолчанию

[derzhavin3016]

Википедия

[uslsteen]

Неплохое видео по расшариванию динамического алгоритма