Пусть известно, что для перемножения матрицы размера n*m на матрицу размера m*k требуется n*m*k операций. Необходимо определить, какое минимальное число операций потребуется для перемножения n матриц А1,...Аn, заданных своими размерами n(i)*m(i).
При этом можно перемножать любые две рядом стоящие матрицы, в результате чего получается матрица нужного размера.
Замечание:
n(i) - число строк в матрице Ai
m(i) - число столбцов в матрице Ai
n(i)=m(i)+1.
Определим через F[i,j] минимальное число операций, которое требуется для перемножения группы матриц с номерами от i до j включительно. Ясно, что F[i,i]=0. Перемножение матриц в такой группе может производиться различными способами, а именно, производить сначала перемножение наилучшим способом группы от i до k, затем от k+1 до j, наконец перемножить получившиеся матрицы. Понятно, что k может быть величиной от i до j-1. Учитывая требование получить наилучший результат, величина F[i,j] определяется как
F[i,j]=max(F[i,k]+F[k+1,j]+n[i]*n[k+1]*m[j]), где k может быть величиной от i до j-1, n[i], n[k+1], m[j] определяют размеры матриц, получившихся при перемножении в группах.
|
|
Задача №14
А) Из последовательности, состоящей из N чисел, вычеркнуть минимальное количество элементов так, чтобы оставшиеся образовали строго возрастающую последовательность.
б) Из заданной числовой последовательности A[1..N] вычеркнуть минимальное число элементов так, чтобы в оставшейся подпоследовательности каждый последующий элемент был больше предыдущего кроме, быть может, одной пары соседних элементов (одного "разрыва" возрастающей подпоследовательности).
Например: A=(1,2,3,2,4,3,4,6);
Искомая подпоследовательность (1,2,3,2,3,4,6)