tailieunhanh - 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: | 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 Vi jí I i p 1 j r k l Ví dụ A là ma trận kích thước 3x4 B là ma trận kích thước 4x5 thì C sẽ là ma trận kích thước 3x5 5 6 7 B 4 5 Ễ 1 100 Để thực hiện phép nhân hai ma trận A mxn và B nxp ta có thể làm như đoạn chươ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 hai ma trận A pxq và B qxr ta cần thực hiện 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 3x4 B là ma trận cấp 4x10 và C là ma trận cấp 10x15 thì Để tính A B C ta thực hiện A B trước được ma trận X kích thước 3x10 sau 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 3x15 sau 450 phép nhân số. Vậy tổng số phép nhân số học phả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 4x15 sau 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 3x15 sau 180 phép nhân số. Vậy tổng số phép nhân số học phả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 . Mn Với M1 là ma trận kích thước a1 x a2 M2 là ma trận kích thước a2 x a3 Mn là ma trận kích thước an x an 1 Input file văn bản Dòng 1 Chứa số nguyên dương n 100 Dòng 2 Chứa n 1 số nguyên dương a15 a2 . an 1 vi 1 ai 100 cách nhau ít nhất một dấu cách Output file văn bản 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ận MATRIXES OUT ri ri m ri lý m 31 M 11 M 21 M 4 M 5J Trước hết nếu dãy chỉ có một ma trận thì chi phí bằng 0 .