Phép nhân tổ hợp dãy ma trận

Với ma trận A kích thước pxq và ma trận B kích thước qxr. Người ta có phép nhân hai ma trận đó để được ma trận C kích thước pxr. Mỗi phần tử của ma trận C được tính theo công thức:
Nội dung trích xuất từ tài liệu:
Phép nhân tổ hợp dãy ma trận Phép nhân tổ hợp dãy ma trậnVới ma trận A kích thước pxq và ma trận B kích thước qxr. Người ta có phép nhânhai ma trận đó để được ma trận C kích thước pxr. Mỗi phần tử của ma trận C đượctính theo công thức:Ví dụ:A là ma trận kích thước 3×4, B là ma trận kích thước 4×5 thì C sẽ là ma trận kíchthước 3×5Để thực hiện phép nhân hai ma trận A(mxn) và B(nxp) ta có thể làm như đoạnchương trình sau:for i := 1 to p do for j := 1 to r do begin cij := 0; for k := 1 to q do cij := cij + aik * bkj; end;Phí tổn để thực hiện phép nhân này có thể đánh giá qua số phép nhân, để nhân haima trận A(pxq) và B(qxr) ta cần thực hiện p.q.r phép nhân số học.Phép nhân ma trận không có tính chất giao hoán nhưng có tính chất kết hợp (A * B) * C = A * (B * C)Vậy nếu A là ma trận cấp 3×4, B là ma trận cấp 4×10 và C là ma trận cấp 10×15thì:• Để tính (A * B) * C, ta thực hiện (A * B) trước, được ma trận X kích thước 3×10sau 3.4.10 = 120 phép nhân số. Sau đó ta thực hiện X * C được ma trận kết quảkích thước 3×15 sau 3.10.15 = 450 phép nhân số. Vậy tổng số phép nhân số họcphải thực hiện sẽ là 570.• Để tính A * (B * C), ta thực hiện (B * C) trước, được ma trận Y kích thước 4×15sau 4.10.15 = 600 phép nhân số. Sau đó ta thực hiện A * Y được ma trận kết quảkích thước 3×15 sau 3.4.15 = 180 phép nhân số. Vậy tổng số phép nhân số họcphải thực hiện sẽ là 780.Vậy thì trình tự thực hiện có ảnh hưởng lớn tới chi phí. Vấn đề đặt ra là tính số phítổn ít nhất khi thực hiện phép nhân một dãy các ma trận: M1 * M2 * … * MnVới :M1 là ma trận kích thước a1 x a2M2 là ma trận kích thước a2 x a3…Mn là ma trận kích thước an x an+1Input: file văn bản MATRIXES.INP• Dòng 1: Chứa số nguyên dương n ≤ 100• Dòng 2: Chứa n + 1 số nguyên dương a1, a2, …, an+1 (∀i: 1 ≤ ai ≤ 100) cách nhauít nhất một dấu cáchOutput: file văn bản MATRIXES.OUT• Dòng 1: Ghi số phép nhân số học tối thiểu cần thực hiện• Dòng 2: Ghi biểu thức kết hợp tối ưu của phép nhân dãy ma trậnTrước hết, nếu dãy chỉ có một ma trận thì chi phí bằng 0, tiếp theo ta nhận thấy đểnhân một cặp ma trận thì không có chuyện kết hợp gì ở đây cả, chi phí cho phépnhân đó là tính được ngay. Vậy thì phí tổn cho phép nhân hai ma trận liên tiếptrong dãy là hoàn toàn có thể ghi nhận lại được. Sử dụng những thông tin đã ghinhận để tối ưu hoá phí tổn nhân những bộ ba ma trận liên tiếp … Cứ tiếp tục nhưvậy cho tới khi ta tính được phí tổn nhân n ma trận liên tiếp.1. Công thức truy hồi:Gọi F[i, j] là số phép nhân tối thiểu cần thực hiện để nhân đoạn ma trận liên tiếp:Mi*Mi+1*…*Mj.Thì khi đó F[i, i] = 0 với i.Để tính Mi * Mi+1 * … * Mj, ta có thể có nhiều cách kết hợp:Mi * Mi+1 * … * Mj = (Mi * Mi+1 * … * Mk) * (Mk+1 * Mk+2 * … * Mj) (Với i ≤ k