Даны три матрицы A(m1,n1); B(m2,n2); C(m3,n3). Как мне вычислить количество умножений чисел, которое потребуется для умножения матриц, например, следующим образом (A*B)*C ??
это выяснил, если:
A(k,n)*B(n,m) = AB(k,m)
число умножений k*n*m
AB(k,m)*C(m,l) = ABC(k,l)
число умножений k*m*l
в результате k*n*m + k*m*l.
А вот если матриц у меня от 1 до n штук, то как мне расставить скобки при умножении этих матриц, чтобы количество умножений чисел было минимальным ??
Могу дать тебе половину решения..
Вот программа, которая выдает само минимальное количество умножений, но не говорит, как расставить скобки. Попробуй разобраться с ней и добавить расстановку скобок .
Начальные данные задаются в константе Dim. При этом, поскольку соседние размерности одинаковые, я не повторяю их. Например, если у тебя есть 5 матриц таких размеров:
(3,4), (4,5), (5,6), (6,7), (7,2)
- то в массив Dim (его размер будет 5+1=6) надо занести:
3, 4, 5, 6, 7, 2
(Этот пример как раз использован в программе)
const
n=5;
type
tDim=array[1..n+1]of integer;
const
Dim:tDim=(3,4,5,6,7,2);
var
i,L:integer;
function MinMult(L:integer):integer;
var
i,j,k,q,D,Mult:integer;
begin
if L=2 then MinMult:=Dim[1]*Dim[2]*Dim[3]
else begin
k:=MaxInt;
for j:=1 to L-1 do begin
Mult:=Dim[j]*Dim[j+1]*Dim[j+2];
D:=Dim[j+1];
for i:=j+1 to L do Dim[i]:=Dim[i+1];
q:=MinMult(L-1);
if q+Mult<k then k:=q+Mult;
for i:=L downto j+1 do Dim[i+1]:=Dim[i];
Dim[j+1]:=D
end;
MinMult:=k
end
end;
begin
WriteLn(MinMult(n));
end.
Почти такой же пример (только не рекурсивный вариант, в книге сказано, что рекурсивный вариант алгоритма экспоненциально зависит от количества матриц, что не лучше полного перебора...) я нашёл в книге Кормена: Алгоритмы. Построение и анализ.
Вот так я его реализовал на паскале:
program matr;
uses crt;
const KOL_M=50;
type
matr_typ=array[1..KOL_M,1..KOL_M] of Longint;
var
p:array[0..KOL_M] of integer;
kol:integer;
m,s:matr_typ;
procedure vvod;
var
i:integer;
begin
write('Vvedite kol-vo matric: ');
readln(kol);
writeln('Vvod razmernostey matric');
writeln('Vvedite razmernost 1-oy matrici: ');
write('Vvedite kol-vo strok: ');
readln(p[0]);
write('Vvedite kol-vo stolbcov: ');
readln(p[1]);
for i:=2 to kol do
begin
write('Vvedite kol-vo stolbcov ',i,'-oy matrici: ');
readln(p[i]);
end;
end;
procedure Minim;
var
n,i,j,l,k:integer;
q:Longint;
begin
n:=kol;
for i:=1 to n do
m[i,i]:=0;
for l:=2 to n do
for i:=1 to n-l+1 do
begin
j:=i+l-1;
m[i,j]:=2147483647;
for k:=i to j-1 do
begin
q:=m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j];
if (q<m[i,j]) then
begin
m[i,j]:=q;
s[i,j]:=k;
end;
end;
end;
writeln('M');
for i:=1 to kol do
begin
for j:=1 to kol do
write(m[i,j]:10,' ');
writeln;
end;
writeln('S');
for i:=1 to kol do
begin
for j:=1 to kol do
write(s[i,j]:3,' ');
writeln;
end;
end;
begin
clrscr;
vvod;
Minim;
readkey;
end.