tailieunhanh - 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 đặ t 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 A lượt tính từ trái qua phải là xanh (X), trắng (T) và đỏ (D). | Chương 4 Các thuật toán sắp đặt Cờ tam tài 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 lượ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 X 3N ô vuông đơn vị được kẻ săn thành lưới ô vuông với mã 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 độ là Ax Ay 1 bạn B chọn một ô trên dòng cuối cù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 đó lần lượt theo thứ tự quay vòng A B C ba bạn chọn các mảnh ghép đơn vị 1x 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ồi bạ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ép kề 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ảnh ghé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 khi hoà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ồi màu. Olimpic quốc tế A C B Cờ tam tài 4 X 6 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. o o 0 A1 X A2 X A3 T A4 T C3 D C2 D A0 X A1 X A2 T A3 T C2 D C1 D Xanh Trắng Đỏ A 5 4 0 115 A1 X B1 X B2 T C2 T C1 D C0 D B1 X B0 X B1 T B2 T C2 D C1 D B 3 3 0 C 0 1 8 Kết quả Cờ tam tài N 2 A 2 1 B 4 2 C 3 6 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à