Третий уровень посвящен перемножению матриц. Оказывается, для достаточно длинных цепочек матриц, порядок их перемножения, будучи выбран правильно, позволяет сэкономить массу машинного времени.
Предположим у вас есть матрица A размера 10 × 30, B размера 30 × 5 и C размера 5 × 60.
Вычисление их произведения как A(BC) займёт (30×5×60) + (10×30×60) = 27000 операций умножения. В то же время, их произведение как (AB)C даст тот же результат за 4500 операций.
Ваша задача -- написать класс MatrixChain, позволяющий:
- Добавить матрицу в цепочку
- Распечатать оптимальный порядок перемножения текущей цепочки матриц
- Выполнить перемножение в оптимальном порядке для тестов производительности
- Показать очевидное превосходство над наивным подходом
Стек матриц может поддерживаться динамически и быть достаточно большим -- тесты на цепочки из 10-20 и более матриц приветствуются.
В выборе оптимальной цепочки должен помочь метод динамического программирования
Входные данные: пары размеров матриц, например
Выход: оптимальный порядок, например 0 1 2 это порядок по умолчанию
Третий уровень посвящен перемножению матриц. Оказывается, для достаточно длинных цепочек матриц, порядок их перемножения, будучи выбран правильно, позволяет сэкономить массу машинного времени.
Предположим у вас есть матрица A размера 10 × 30, B размера 30 × 5 и C размера 5 × 60.
Вычисление их произведения как A(BC) займёт (30×5×60) + (10×30×60) = 27000 операций умножения. В то же время, их произведение как (AB)C даст тот же результат за 4500 операций.
Ваша задача -- написать класс MatrixChain, позволяющий:
Стек матриц может поддерживаться динамически и быть достаточно большим -- тесты на цепочки из 10-20 и более матриц приветствуются.
В выборе оптимальной цепочки должен помочь метод динамического программирования
Входные данные: пары размеров матриц, например
Выход: оптимальный порядок, например 0 1 2 это порядок по умолчанию