HỌC TIN CÙNG THỦ KHOA

Nhân một ma trận kích thước m×n với một ma trận n×p, số phép nhân phải thực hiện là m.n.p. Mặt khác phép nhân các ma trận có tính kết hợp, tức là:

(A.B).C = A.(B.C)

Do đó khi tính tích nhiều ma trận, ta có thể thực hiện theo các trình tự khác nhau, mỗi trình tự tính sẽ quyết định số phép nhân cần thực hiện.

Đề bài: Cho N ma trận A1,A2…An, ma trận Ai có kích thước là di–1×di. Hãy xác định trình tự nhân ma trận A1.A2…An sao cho số phép nhân cần thực hiện là ít nhất.

Mời các bạn download tại: Click here

Phân tích thiết kế thuật toán tại: Click here (phần 2)

const fi = 'NHANMATRAN.INP';
      fo = 'NHANMATRAN.OUT';
      MAXN = 100;
      oo = MAXINT;

var  f:text;
     n: integer;
     d: array[0..MAXN] of integer;
     L, H: array[1..MAXN, 1..MAXN] of integer;

procedure Nhap;
var i:integer;
begin
    assign(f, fi); reset(f);
    readln(f, n);
    for i:= 0 to n do read(f, d[i]);
    close(f);
end;

function min(a, b:integer):integer;
begin
    if a<b then exit(a) else exit(b);
end;

procedure QHD;
var i, j, m, k, tong: integer;
begin
    for i:=1 to n do L[i, i] := 0;
    for i:=1 to n-1 do
    begin
        L[i, i+1] := d[i-1] * d[i] *d[i+1];
        // (Ai x Ai+1)
    end;

    for m:=2 to n-1 do
        for i:=1 to n-m do
        begin
            j := i+m;
            L[i, j] := +oo;
            for k:= i to j-1 do
            begin
                 tong:= L[i, k] + L[k+1,j] + d[i-1]*d[k]*d[j];
                 if L[i, j] > tong then
                 begin
                        L[i, j]:= tong;
                        H[i, j] := k;
                 end;
            end;
        end;
end;

function TruyVet(i, j:integer): string;
var k:integer;
    temp, temp2, s1, s2: string;
begin
        if i = j then
        begin
                str(i, temp);
                exit('A' + temp);
        end
        else if j = i + 1 then
        begin
                str(i, temp);
                str(j, temp2);
                exit('(A' + temp + 'x' + 'A' + temp2 + ')');
        end
        else
        begin
                k:= H[i, j];
                s1:= TruyVet(i, k);
                s2:= TruyVet(k+1, j);
                exit('(' + s1 + 'x' + s2 + ')');
        end;
end;


BEGIN
        Nhap;
        QHD;
        assign(f, fo); rewrite(f);
        writeln(f, L[1, n]);
        writeln(f, TruyVet(1, n));
        close(f);
END.