Впринципе сам алгоритм умножения последовательности матриц у меня есть но нужен конкретный пример так как в самом алгоритме маот чё понятно. Ну может кто то имел дело с такой темой но на всякий случай скажу что смысл этого алгоритма в том что он оптимально расставляет скобки в последовательности матриц (это раздел с динамического програмирования).

или может кто подскажет как там надо выбирать все эти индексы и что с ними делать

Перемножить можно только матрицы у которых количество столбцов первого сомножителя совпадает с количеством строк второго сомножителя.

А(nxm) * B(mxl) = C(nxl), где n,m,l-соответствующая размерность.

Пример:

Матрица А:

1 2
3 4

Матрица B:

1 0 -1
0 5 2

С11=1*1+2*0=1
С12=1*0+2*5=10
С13=1*(-1)+2*2=3
С21=3*1+4*0=3
С22=3*0+4*5=20
С23=3*(-1)+4*2=5

Получили матрицу
С:
1 10 3
3 20 5

Это сообщение отредактировал(а) ДобренькийПапаша - 27.2.2006, 18:01

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

введем обозначение C(n,n+m) - сложность перемножения матриц An*An+1*...*An+m
для начала очевидно, что C(n,n)=0 - сама матрица уже и есть результат, ничего вычислять не надо
теперь посчитаем C(n,n+m)
чтобы перемножить матрицы, нужно решить, какое умножение будет последним - т.е. скобками разбить весь набор на две части, потом посчитать эти две части, а потом умножить две получившиеся матрицы
т.е. C(n,n+m)=C(n,n+k-1)+C(n+k,n+m)+f( c(An),r(An+k-1),c(An+k),r(An+m) )
здесь n+k - номер матрицы, после которой мы сделали разбиение
c(A) - количество столбцов матрицы
r(A) - количество строк
f(c,r,cc,rr) - функция сложности умножения матрицы размерами c*r на матрицу размерами cc*rr, если, например, учитывать только умножения и не обращать внимания на сложения, то f(c,r,cc,rr)=c*r*cc*rr
c(An),r(An+k-1) - размеры матрицы, которая получится из левой части
c(An+k),r(An+m) - из правой

теперь сам выбор оптимальной расстановки скобок:
для этого нужно взять такое k, чтобы C(n,n+m) было минимально
C(n,n+m)=min[k=1..m]{ C(n,n+k-1)+C(n+k,n+m)+f( c(An),r(An+k-1),c(An+k),r(An+m) ) }
получается рекурсия
она не зависнет, т.к. при вычислении каждого C(n,n+m) используются C(i,j), где i-j меньше m, а значит, рано или поздно все сведется к C(i,i) и слагаемым, полученным по пути

теперь динамическое программирование:
чтобы не пересчитывать по много раз одни и те же значения, можно их запомнить
запоминать удобно в таблице N*N (N - количество матриц вообще)
в ячейку (i,j) будем записывать C(i,j)
часть таблицы, где i>j исползоваться не будет
по диагонали будут нули
а остальные ячейки будут вычисляться
порядок вычислений должен идти по удалению от главной диагонали (чтобы в каждый момент все нужное для вычислений было уже посчитано):
сначала C(n,n) (нулями)
потом C(n,n+1)
потом C(n,n+2)
и т.д....

Проще: скачивашь книжку Кормена "Алгоритмы: построение и анализ."
Там прекрасно сказано как перемножать матрицы и приведен алгоритм и код.

Если не влом дай ссылку на скачку, а то влом там копаться.

У нас в разделе "Литература компьютерная, обычная "
http://g6prog.narod.ru/mycop/cormen.rar
Добавлено @ 21:08
http://pogorskiy.narod.ru/algos.htm
http://rangh.mail2k.ru/cormen.rar
http://pogorskiy.narod.ru/algos.htm