Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 2 - Chương 4

Các thuật toán sắp đặ t4.1 Cờ tam tàiOlimpic quốc tế Một số quốc gia như Ba Lan, Bỉ, Pháp… có quốc kỳ tạo từ ba giải màu thường được gọi là cờ tam tài. Ba bạn trẻ A, B và C chơi trò ghép hình để tạo thành một lá cờ tam tài với ba giải màu dọc lần A lượt tính từ trái qua phải là xanh (X), trắng (T) và đỏ (D).
Nội dung trích xuất từ tài liệu:
Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 2 - Chương 4 C hươ ng 4 C á c th uật t oá n sắ p đặ t4.1 Cờ tam tài Olimpic quốc tế Một số quốc gia như Ba Lan, Bỉ, Pháp… cóquốc kỳ tạo từ ba giải màu thường được gọi là cờtam tài. Ba bạn trẻ A, B và C chơi trò ghép hình đểtạo thành một lá cờ tam tài với ba giải màu dọc lần Alượt tính từ trái qua phải là xanh (X), trắng (T) vàđỏ (D). Mặt bàn để ghép cờ có kích thước 2N  3Nô vuông đơn vị được kẻ sẵn thành lưới ô vuông với Cmã số các hàng tính từ trên xuống dưới là 1, 2,…,2N và mã số các cột tính từ trái qua phải là 1, 2,…,3N. Đầu tiên bạn A chọn một ô trên cột 1 có tọa độ Blà (Ax, Ay = 1), bạn B chọn một ô trên dòng cuốicùng có tọa độ là (Bx=2N, By), bạn C chọn một ôtrên cột cuối cùng có tọa độ là (Cx, Cy = 3N). Sau Cờ tam tài 4  6đó lần lượt theo thứ tự quay vòng A, B, C ba bạnchọn các mảnh ghép đơn vị 1 1 với màu phù hợp N=2để đặt vào các ô trong bàn cờ. Lần đầu tiên mỗibạn đặt một mảnh ghép vào ô đã chọn. Những lần tiếp theo, đến lượt mình, mỗi bạn đặt một số mảnh ghépkề với mảnh ghép do chính bạn ấy đã đặt tại lần trước. Dĩ nhiên, mỗi ô trên bàn chỉ được đặt đúng 1 mảnhghép. Bạn nào không thể ghép được thì bạn đó ngừng chơi, những người còn lại sẽ tiếp tục chơi đến khihoàn thành lá cờ. Biết các giá trị N, Ax, By và Cx. Hãy cho biết mỗi bạn đã ghép được bao nhiêu mảnh mỗimàu. Với thí dụ như trong hình, N = 2, Ax = 2, By = 2, Cx = 3 ta tính được kết quả như trong bảng. Ýnghĩa của các ô trên bàn ghép cờ cho biết bạn nào trong lần đi thứ mấy của mình, ghép mảnh màu gì. Thídụ, A5:T cho biết bạn A, trong lần đi thứ 5 ghép mảnh màu trắng. Ô xuất phát của mỗi bạn kí hiệu là 0.        Trắng Đỏ A1:X A2:X A3:T A4:T C3:D C2:D Xanh  A0:X A1:X A2:T A3:T C2:D C1:D 5 4 0 A 115  A1:X B1:X B2:T C2:T C1:D C0:D 3 3 0 B  B1:X B0:X B1:T B2:T C2:D C1:D 0 1 8 C Cờ tam tài, N = 2, A(2,1), B(4,2), C(3,6) Kết quả X: Xanh, T: Trắng, D: Đỏ.Thuật toán Bài này khá dễ giải. Nếu bạn khéo tổ chức dữ liệu thì chương trình sẽ rất gọn. Trước hết ta cần xácđịnh rằng mỗi ô (i,j) trên bàn cờ sẽ do bạn nào ghép: A, B hay C ? Ta định nghĩa khoảng cách giữa hai ô(i,j) và (x,y) trên bàn cờ là số ô ít nhất nằm trên đường đi từ ô này đến ô kia qua các ô kề cạnh nhau.Khoảng cách này chính là tổng chiều dài hai cạnh kề nhau của hình chữ nhật nhận hai ô đã cho làm haiđỉnh đối diện, do đó được tính theo công thức d = abs(i-x) + abs(j-y) +1 Giá trị d có ý nghĩa gì ? Nếu ta qui định đánh số các lần đi cho mỗi đấu thủ là 0, 1, 2, … thì d -1 chobiết lần đi thứ mấy của mỗi bạn. Vì trật tự tính lần đi của các bạn là A  B  C nên ta cần xác định giá trịmin trong ba khảng cách d A, dB và dC. Tuy nhiên chúng ta sẽ khôn ngoan một chút, cụ thể là t a sẽ tính dtheo công thức hụt 1 d = abs(i-x) + abs(j-y) và viết hàm min3 nhận vào là ba giá trị d A, dB và dC và cho ra là tên của người được ghép mảnh tại ôđang xét. function Min3(a,b,c: integer): char; var k: char; begin k := A; if a > b then begin k := B; a := b end; if a > c then k := C; Min3 := k; end; Sau khi xác định được chủ của mảnh ghép tại ô (i,j) ta dễ dàng tính được màu của mảnh ghép tại ôđó. Vì lá cờ có ba màu và ta tạm qui ước các giải màu tính từ trái qua phải là 0, 1 và 2 nên màu cần chọn đểđặt tại ô (i,j) khi đó sẽ là (j-1) div N. Ta khai báo mảng kq dùng để tích lũy kết quả như sau: kq: array[A..C,0..2] of integer; Khi đó c[v,i] sẽ cho biết bạn v đã ghép bao nhiêu quân màu i, v = A, B, C; i = 0 (màu X anh), 1(màu Trắng), 2 (màu Đỏ). Các biến chung của chương trình sẽ là: var n: inte ...