IPB
ЛогинПароль:

> Количество умножений чисел, при умножении матриц
сообщение
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской
Реальное имя: Юра

Репутация: -  1  +


Даны три матрицы A(m1,n1); B(m2,n2); C(m3,n3). Как мне вычислить количество умножений чисел, которое потребуется для умножения матриц, например, следующим образом (A*B)*C ??
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов(1 - 3)
сообщение
Сообщение #2


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской
Реальное имя: Юра

Репутация: -  1  +


это выяснил, если:
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 штук, то как мне расставить скобки при умножении этих матриц, чтобы количество умножений чисел было минимальным ??
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Могу дать тебе половину решения..
Вот программа, которая выдает само минимальное количество умножений, но не говорит, как расставить скобки. Попробуй разобраться с ней и добавить расстановку скобок smile.gif.

Начальные данные задаются в константе 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.

Можешь задавать вопросы.. smile.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской
Реальное имя: Юра

Репутация: -  1  +


Почти такой же пример (только не рекурсивный вариант, в книге сказано, что рекурсивный вариант алгоритма экспоненциально зависит от количества матриц, что не лучше полного перебора...) я нашёл в книге Кормена: Алгоритмы. Построение и анализ.
Вот так я его реализовал на паскале:

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.


В матрице m в элементе [1..n], где n - количество матриц, хранится минимальное количество умножений. В матрице s, в элементе s[i,j] - записано место последнего умножения при оптимальной расстановке скобок.
Также в этой книге есть процедура, реализующая произведение матриц с оптимальной расстановкой скобок, вот её псевдокод:
Код

Matrix-Chain-Multiply(A,s,i,j);

1 if j>i
2  then X<-Matrix-Chain-Multiply(A,s,i,s[i,j])
3       Y<-Matrix-Chain-Multiply(A,s,s[i,j]+1,j)
4       return Matrix-Multiply(X,Y)
5 else return Ai


Думаю, что для расстановки скобок переделать нужно именно эту процедуру...но вот как? что то у меня не получается sad.gif... помогите, пожалуйста....

Сообщение отредактировано: samec -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 22:28
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name