Giải thuật và lập trình

procedure Result; var

fo: Text;

i, t, j: Integer;

Sum: LongInt;

begin

t := 0;

{Tính lại các Count[i] := Số phần tử phương án tối ưu sẽ chọn trong lớp i}

for i := k - 1 downto 0 do begin

j := Trace[i, t];

t := Sub(t, j * i);

Count[i] := j; end;

Assign(fo, OutputFile); Rewrite(fo); WriteLn(fo, f[k - 1, 0]);

Sum := 0;

for i := 1 to n do begin

t := a[i] mod k;

if Count[t] > 0 then begin

WriteLn(fo, 'a[', i, '] = ', a[i]); Dec(Count[t]);

Sum := Sum + a[i]; end;

end;

WriteLn(fo, 'Sum = ', Sum);

Close(fo);

end;

begin

Enter;

Optimize;

Result;

end.

Cách giải thứ hai tốt hơn cách giải thứ nhất vì nó có thể thực hiện với n lớn. Ví dụ này cho thấy một bài toán quy hoạch động có thể có nhiều cách đặt công thức truy hồi để giải.

3.5. 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:

Ví dụ:

Cij Aik .Bkj ;

k1

1  i  p,1  j  r

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

⎢

⎡1

⎢ 5

⎢⎣ 9

2 3

6 7

10 11

4 ⎤

⎥

⎡1

0⎤

⎢0

⎢

1⎥

⎥

⎢3

1⎥

Có thể bạn quan tâm!

Xem toàn bộ 316 trang tài liệu này.

8 ⎥x 12⎥⎦⎢

⎣

1 1 1

⎡⎤



14	6	9	36	9
34	14	25	100	21
54	22	41	164	33

⎢⎥

⎥⎢⎣⎥⎦

⎦

Để 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 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 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 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 3x15 sau

3.10.15 = 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 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 3x15 sau

3.4.15 = 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 MULTMAT.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ách

Output: file văn bản MULTMAT.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ận

MULTMAT.INP

MULTMAT.OUT

3 2 3 1 2 2 3

((M[1] * (M[2] * M[3])) * ((M[4] * M[5]) * M[6]))

Trướ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ép nhân đó là tính được ngay. Vậy thì phí tổn cho phép nhân hai ma trận liên tiếp trong dãy là hoàn toàn có thể ghi nhận lại được. Sử dụng những thông tin đã ghi nhậ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.

3.5.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 < j)

Với một cách kết hợp (phụ thuộc vào cách chọn vị trí k), chi phí tối thiểu phải thực hiện bằng: Chi phí thực hiện phép nhân Mi * Mi+1 * … * Mk = F[i, k]

Cộng với chi phí thực hiện phép nhân Mk+1 * Mk+2 * … * Mj = F[k + 1, j]

Cộng với chi phí thực hiện phép nhân hai ma trận cuối cùng: ma trận tạo thành từ phép nhân (Mi * Mi+1 * … * Mk) có kích thước ai x ak+1 và ma trận tạo thành từ phép nhân (Mk+1 * Mk+2

* … * Mj) có kích thước ak+1 x aj+1, vậy chi phí này là ai * ak+1 * aj+1.

Từ đó suy ra: do có nhiều cách kết hợp, mà ta cần chọn cách kết hợp để có chi phí ít nhất nên ta sẽ cực tiểu hoá F[i, j] theo công thức:



F[i, j]  min(F[i, k]  F[k  1, j]  ai * ak1 * a j1)

i k j

3.5.2. Tính bảng phương án

Bảng phương án F là bảng hai chiều, nhìn vào công thức truy hồi, ta thấy F[i, j] chỉ được tính khi mà F[i, k] cũng như F[k + 1, j] đều đã biết. Tức là ban đầu ta điền cơ sở quy hoạch động vào đường chéo chính của bảng(F[i, i] = 0), từ đó tính các giá trị thuộc đường chéo nằm phía trên (Tính các F[i, i + 1]), rồi lại tính các giá trị thuộc đường chéo nằm phía trên nữa (F[i, i + 2]) … Đến khi tính được F[1, n] thì dừng lại

3.5.3. Tìm cách kết hợp tối ưu

Tại mỗi bước tính F[i, j], ta ghi nhận lại điểm k mà cách tính (Mi * Mi+1 * … * Mk) * (Mk+1 * Mk+2 * … * Mj) cho số phép nhân số học nhỏ nhất, chẳng hạn ta đặt T[i, j] = k.

Khi đó, muốn in ra phép kết hợp tối ưu để nhân đoạn Mi * Mi+1 * … * Mk * Mk+1 * Mk+2 * …

* Mj, ta sẽ in ra cách kết hợp tối ưu để nhân đoạn Mi * Mi+1 * … * Mk và cách kết hợp tối ưu

để nhân đoạn Mk+1 * Mk+2 * … * Mj (có kèm theo dấu đóng mở ngoặc) đồng thời viết thêm dấu "*" vào giữa hai biểu thức đó.

P_3_03_7.PAS * Nhân tối ưu dãy ma trận

program MatrixesMultiplier; const

InputFile = 'MULTMAT.INP';

OutputFile = 'MULTMAT.OUT'; max = 100;

MaxLong = 1000000000;

var

a: array[1..max + 1] of Integer;

F: array[1..max, 1..max] of LongInt; T: array[1..max, 1..max] of Byte;

n: Integer; fo: Text;

procedure Enter; {Nhập dữ liệu từ thiết bị nhập chuẩn}

var

i: Integer; fi: Text;

begin

Assign(fi, InputFile); Reset(fi); ReadLn(fi, n);

for i := 1 to n + 1 do Read(fi, a[i]); Close(fi);

end;

procedure Optimize; var

i, j, k, len: Integer; x, p, q, r: LongInt;

begin

for i := 1 to n do for j := i to n do

if i = j then F[i, j] := 0

else F[i, j] := MaxLong; {Khởi tạo bảng phương án: đường chéo chính = 0, các ô khác = +}

for len := 2 to n do {Tìm cách kết hợp tối ưu để nhân đoạn gồm len ma trận liên tiếp}

for i := 1 to n - len + 1 do begin

j := i + len - 1; {Tính F[i, j]}

for k := i to j - 1 do {Xét mọi vị trí phân hoạch k}

begin {Giả sử ta tính Mi * … * Mj = (Mi * … * Mk) * (Mk+1 * … * Mj)}

p := a[i]; q := a[k + 1]; r := a[j + 1]; {Kích thước 2 ma trận sẽ nhân cuối cùng}

x := F[i, k] + F[k + 1, j] + p * q * r; {Chi phí nếu phân hoạch theo k}

if x < F[i, j] then {Nếu phép phân hoạch đó tốt hơn F[i, j] thì ghi nhận lại}

begin

F[i, j] := x;

T[i, j] := k; end;

end;

procedure Trace(i, j: Integer); {In ra phép kết hợp để nhân đoạn Mi * Mi+1 * … * Mj}

var

k: Integer; begin

if i = j then Write(fo, 'M[', i, ']') {Nếu đoạn chỉ gồm 1 ma trận thì in luôn}

else {Nếu đoạn gồm từ 2 ma trận trở lên}

begin

Write(fo, '('); {Mở ngoặc}

end;

k := T[i, j]; {Lấy vị trí phân hoạch tối ưu đoạn Mi…Mj} Trace(i, k); {In ra phép kết hợp để nhân đoạn đầu} Write(fo, ' * '); {Dấu nhân}

Trace(k + 1, j); {In ra phép kết hợp để nhân đoạn sau}

Write(fo, ')'); {Đóng ngoặc}

end;

begin

Enter;

Optimize;

Assign(fo, OutputFile); Rewrite(fo);

WriteLn(fo, F[1, n]); {Số phép nhân cần thực hiện}

Trace(1, n); {Truy vết bằng đệ quy}

Close(fo); end.

3.6. BÀI TẬP LUYỆN TẬP

3.6.1. Bài tập có gợi ý lời giải

Bài 1

Nhập vào hai số nguyên dương n và k (n, k  100). Hãy cho biết

a) Có bao nhiêu số nguyên dương có  n chữ số mà tổng các chữ số đúng bằng k. Nếu có hơn 1 tỉ số thì chỉ cần thông báo có nhiều hơn 1 tỉ.

b) Nhập vào một số p  1 tỉ. Cho biết nếu đem các số tìm được xếp theo thứ tự tăng dần thì số thứ p là số nào ?

Gợi ý:

Câu a: Ta sẽ đếm số các số có đúng n chữ số mà tổng các chữ số (TCCS) bằng k, chỉ có điều các số của ta cho phép có thể bắt đầu bằng 0. Ví dụ: ta coi 0045 là số có 4 chữ số mà TCCS là

9. Gọi F[n, k] là số các số có n chữ số mà TCCS bằng k. Các số đó có dạng

x1x2...xn ; x1,

x2, …xn ở đây là các chữ số 0…9 và x1 + x2 + … + xn = k. Nếu cố định x1 = t thì ta nhận

thấy

x2 ...xn

lập thành một số có n - 1 chữ số mà TCCS bằng k - t. Suy ra do x1 có thể nhận

các giá trị từ 0 tới 9 nên về mặt số lượng: F[n, k] = F[n 1, k t] . Đây là công thức truy

t 0

hồi tính F[n, k], thực ra chỉ xét những giá trị t từ 0 tới 9 và t  k mà thôi (để tránh trường hợp k - t <0). Chú ý rằng nếu tại một bước nào đó tính ra một phần tử của F > 109 thì ta đặt lại phần tử đó là 109 + 1 để tránh bị tràn số do cộng hai số quá lớn. Kết thúc quá trình tính toán, nếu F[n, k] = 109 + 1 thì ta chỉ cần thông báo chung chung là có > 1 tỉ số.

Cơ sở quy hoạch động thì có thể đặt là:

F[1, k] = số các số có 1 chữ số mà TCCS bằng k, như vậy nếu k  10 thì F[1, k] = 0 còn nếu 0

 k  9 thì F[1, k] = 1.

Câu b: Dựa vào bảng phương án F[0..n, 0..k],

F[n - 1, k] = số các số có n - 1 CS mà TCCS bằng k = số các số có n CS, bắt đầu là 0, TCCS bằng k.

F[n - 1, k - 1] = số các số có n - 1 CS mà TCCS bằng k - 1 = số các số có n CS, bắt đầu là 1, TCCS bằng k. F[n - 1, k - 2] = số các số có n - 1 CS mà TCCS bằng k - 2 = số các số có n CS, bắt đầu là 2, TCCS bằng k.

…

F[n - 1, k - 9] = số các số có n - 1 CS mà TCCS bằng k - 9 = số các số có n CS, bắt đầu là 9, TCCS bằng k. Từ đó ta có thể biết được số thứ p (theo thứ tự tăng dần) cần tìm sẽ có chữ số đầu tiên là chữ số nào, tương tự ta sẽ tìm được chữ số thứ hai, thứ ba v.v… của số đó.

Bài 2

Cho n gói kẹo (n  200), mỗi gói chứa không quá 200 viên kẹo, và một số M  40000. Hãy chỉ ra một cách lấy ra một số các gói kẹo để được tổng số kẹo là M, hoặc thông báo rằng không thể thực hiện được việc đó.

Gợi ý: Giả sử số kẹo chứa trong gói thứ i là Ai

Gọi b[V] là số nguyên dương bé nhất thoả mãn: Có thể chọn trong số các gói kẹo từ gói 1 đến gói b[V] ra một số gói để được tổng số kẹo là V. Nếu không có phương án chọn, ta coi b[V] = +. Trước tiên, khởi tạo b[0] = 0 và các b[V] = + với mọi V > 0. Ta sẽ xây dựng b[V] như sau:

Để tiện nói, ta đặt k = b[V]. Vì k là bé nhất có thể, nên nếu có cách chọn trong số các gói kẹo từ gói 1 đến gói k để được số kẹo V thì chắc chắn phải chọn gói k. Mà đã chọn gói k rồi thì trong số các gói kẹo từ 1 đến k - 1, phải chọn ra được một số gói để được số kẹo là V - Ak. Tức là b[V - Ak]  k - 1 < k. Vậy thì b[V] sẽ được tính bằng cách:

Xét tất cả các gói kẹo k có Ak  V và thoả mãn b[V - Ak] < k, chọn ra chỉ số k bé nhất, sau đó

gán b[V] := k. Đây chính là công thức truy hồi tính bảng phương án.

Sau khi đã tính b[1], b[2], …, b[M]. Nếu b[M] vẫn bằng + thì có nghĩa là không có phương án chọn. Nếu không thì sẽ chọn gói p1 = b[M], tiếp theo sẽ chọn gói p2 = b[M - Ap1], rồi lại chọn gói p3 = b[M - Ap1 - Ap2]… Đến khi truy vết về tới b[0] thì thôi.

Bài 3

Cho n gói kẹo (n  200), mỗi gói chứa không quá 200 viên kẹo, hãy chia các gói kẹo ra làm hai nhóm sao cho số kẹo giữa hai nhóm chênh lệch nhau ít nhất

Gợi ý:

Gọi S là tổng số kẹo và M là nửa tổng số kẹo, áp dụng cách giải như bài 2. Sau đó Tìm số nguyên dương T thoả mãn:

 T  M

 Tồn tại một cách chọn ra một số gói kẹo để được tổng số kẹo là T (b[T]  +)

 T lớn nhất có thể

Sau đó chọn ra một số gói kẹo để được T viên kẹo, các gói kẹo đó được đưa vào một nhóm, số còn lại vào nhóm thứ hai.

Bài 4

1	2	6	7	9
7	6	5	6	7
1	2	3	4	2
4	7	8	7	6

Cho một bảng A kích thước m x n, trên đó ghi các số nguyên. Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được). Quy tắc: Từ ô A[i, j] chỉ được quyền sang một trong 3 ô A[i, j + 1]; A[i - 1, j + 1]; A[i + 1, j + 1]. Hãy tìm vị trí ô xuất phát và hành trình đi từ cột 1 sang cột n sao cho tổng các số ghi trên đường đi là lớn nhất.

A 

Gợi ý:

Gọi B[i, j] là số điểm lớn nhất có thể có được khi tới ô A[i, j]. Rõ ràng đối với những ô ở cột 1 thì B[i, 1] = A[i, 1]:

1	2	6	7	9
7	6	5	6	7
1	2	3	4	2
4	7	8	7	6

A  B 

Với những ô (i, j) ở các cột khác. Vì chỉ những ô (i, j - 1), (i - 1, j - 1), (i + 1, j - 1) là có thể sang được ô (i, j), và khi sang ô (i, j) thì số điểm được cộng thêm A[i, j] nữa. Chúng ta cần B[i, j] là số điểm lớn nhất có thể nên B[i, j] = max(B[i, j - 1], B[i - 1, j - 1], B[i + 1, j - 1]) + A[i, j]. Ta dùng công thức truy hồi này tính tất cả các B[i, j]. Cuối cùng chọn ra B[i, n] là phần tử lớn nhất trên cột n của bảng B và từ đó truy vết tìm ra đường đi nhiều điểm nhất.

3.6.2. Bài tập tự làm

Bài 1

Bài toán cái túi với kích thước như nêu trên là không thực tế, chẳng có siêu thị nào có  100 gói hàng cả. Hãy lập chương trình giải bài toán cái túi với n  10000; M  1000.

Bài 2

Xâu ký tự S gọi là xâu con của xâu ký tự T nếu có thể xoá bớt một số ký tự trong xâu T để được xâu S. Lập chương trình nhập vào hai xâu ký tự S1, S2. Tìm xâu S3 có độ dài lớn nhất là xâu con của cả S1 và S2. Ví dụ: S1 = 'abcdefghi123'; S2 = 'abc1def2ghi3' thì S3 là 'abcdefghi3'. Bài 3

Một xâu ký tự X gọi là chứa xâu ký tự Y nếu như có thể xoá bớt một số ký tự trong xâu X

để được xâu Y: Ví dụ: Xâu '1a2b3c45d' chứa xâu '12345'. Một xâu ký tự gọi là đối xứng nếu

nó không thay đổi khi ta viết các ký tự trong xâu theo thứ tự ngược lại: Ví dụ: 'abcABADABAcba', 'MADAM' là các xâu đối xứng.

Nhập một xâu ký tự S có độ dài không quá 128, hãy tìm xâu ký tự T thoả mãn cả 3 điều kiện:

1. Đối xứng

2. Chứa xâu S

3. Có ít ký tự nhất (có độ dài ngắn nhất)

Nếu có nhiều xâu T thoả mãn đồng thời 3 điều kiện trên thì chỉ cần cho biết một. Chẳng hạn với S = 'a_101_b' thì chọn T = 'ab_101_ba' hay T = 'ba_101_ab' đều đúng.

Ví dụ:

MADAM MADAM

Edbabcd edcbabcde

00_11_22_33_222_1_000 000_11_222_33_222_11_000

abcdefg_hh_gfe_1_d_2_c_3_ba ab_3_c_2_d_1_efg_hh_gfe_1_d_2_c_3_ba

Bài 4

Có n loại tiền giấy: Tờ giấy bạc loại i có mệnh giá là V[i] ( n  20, 1  V[i]  10000). Hỏi muốn mua một món hàng giá là M thì có bao nhiêu cách trả số tiền đó bằng những loại giấy bạc đã cho (Trường hợp có > 1 tỉ cách thì chỉ cần thông báo có nhiều hơn 1 tỉ). Nếu tồn tại cách trả, cho biết cách trả phải dùng ít tờ tiền nhất.

Bài 5

Cho n quân đô-mi-nô xếp dựng đứng theo hàng ngang và được đánh số từ 1 đến n. Quân đô- mi-nô thứ i có số ghi ở ô trên là a[i] và số ghi ở ô dưới là b[i]. Xem hình vẽ:

1	4	4	0	6
6	3	1	1	6	1
1	2	3	4	5	6

Biết rằng 1  n  100 và 0  ai, bi  6 với i: 1  i  n. Cho phép lật ngược các quân đô-mi-nô. Khi một quân đô-mi-nô thứ i bị lật, nó sẽ có số ghi ở ô trên là b[i] và số ghi ở ô dưới là a[i].

Vấn đề đặt ra là hãy tìm cách lật các quân đô-mi-nô sao cho chênh lệch giữa tổng các số ghi ở hàng trên và tổng các số ghi ở hàng dướii là tối thiểu. Nếu có nhiều phương án lật tốt như nhau, thì chỉ ra phương án phải lật ít quân nhất.

Như ví dụ trên thì sẽ lật hai quân Đô-mi-nô thứ 5 và thứ 6. Khi đó: Tổng các số ở hàng trên = 1 + 1 + 4 + 4 + 6 + 1 = 17

Tổng các số ở hàng dưới = 6 + 3 + 1 + 1 + 0 + 6 = 17

Bài 6

Xét bảng H kích thước 4x4, các hàng và các cột được đánh chỉ số A, B, C, D. Trên 16 ô của bảng, mỗi ô ghi 1 ký tự A hoặc B hoặc C hoặc D.