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

SUY NGẪM Chương này giới thiệu một số bài toán thuộc các lớp thuật giải khác nhau để bạn đọc tự luyện tập. Thông thường, nếu chỉ biết một phương pháp giải mà gặp bài toán "trúng tủ", nghĩa là bài toán vận dụng chính phương pháp đã biết thì ta gần như không phải suy nghĩ gì. Tuy nhiên, khi đã có trong tay một số phương pháp thì việc chọn thuật giải cho mỗi bài toán cụ thể sẽ không dễ dàng chút nào. Luyện tập và suy ngẫm để tìm kiếm đường đi trong các tình huống...
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 1 - Chương 8 223 Sáng tạo trong Thuật toán và Lập trình Tập I CHƢƠNG 8 SUY NGẪM Chương này giới thiệu một số bài toán thuộc các lớp thuật giải khác nhau để bạn đọc tự luyện tập. Thông thường, nếu chỉ biết một phương pháp giải mà gặp bài toán trúng tủ, nghĩa là bài toán vận dụng chính phương pháp đã biết thì ta gần như không phải suy nghĩ gì. Tuy nhiên, khi đã có trong tay một số phương pháp thì việc chọn thuật giải cho mỗi bài toán cụ thể sẽ không dễ dàng chút nào. Luyện tập và suy ngẫm để tìm kiếm đường đi trong các tình huống như trên sẽ cung cấp cho chúng ta nhiều kinh nghiệm quý. Bài 8.1. Lát nền Người ta cần lát kín một nền nhà hình vuông cạnh dài n = 2k, (k là một số tự nhiên trong khoảng 1..6) khuyết một phần tư tại góc trên phải bằng những viên gạch màu hình thước thợ (chữ L) tạo bởi 3 ô vuông đơn vị như trong hình 2b. Hai viên gạch kề cạnh nhau dù chỉ 1 đơn vị dài phải có màu khác nhau. Hãy cho biết một cách lát với số màu ít nhất. D B A C a) Nền nhà b) Gạch lát Hình 2 Dữ liệu vào: tệp văn bản NEN.INP chứa số tự nhiên n. Dữ liệu ra: tệp văn bản NEN.OUT. Dòng đầu tiên là hai số tự nhiên m biểu thị số viên gạch và c là số màu cần dùng cho việc lát nền. Tiếp đến là một phương án lát nền tìm được, trong đó mỗi viên gạch lát được tạo bởi ba chữ số giống nhau thể hiện màu của viên gạch đó. Các số trên mỗi dòng cách nhau qua dấu cách. 224 Sáng tạo trong Thuật toán và Lập trình Tập I Thí dụ, với n = 8 ta có một cách lát nền như NEN.INP NEN.OUT sau: Lời giải sau đây của bạn Lê Hoàng Hải, lớp 8 16 3 10 chuyên Tin, Đại học Khoa học Tự nhiên, Đại 331 1 học Quốc gia Hà Nội (năm 2002). 322 1 Để tính số viên gạch ta lấy ba phần tư diện 123 3 tích hình vuông phủ nền nhà chia cho 3 là diện 113 2 tích 1 viên gạch thước thợ: 331 2 2 3 1 1 sogach:=((3*n*n) div 4) div 3; 321 1 3 3 2 1 122 3 1 2 2 3 113 3 1 1 3 3 3 3 11 Về số màu, với n = 2 thì chỉ cần 1 viên gạch màu 1. Với mọi n > 2 ta sẽ trình bày một thuật toán cần tối đa ba 3 2 21 màu. 1 2 33 Đầu tiên ta gọi thủ tục Init để khởi trị với 1 1 32 hình vuông cạnh v = 2 nằm ở góc dưới trái của 3 3122311 nền nhà được biểu diễn dưới dạng một mảng hai 3 2113321 chiều a: ba ô trong hình vuông 2  2 sẽ được 1 2231223 điền giá trị 1, ô nằm ở góc trên phải được điền giá trị 2 (phần tô đậm, hình 6). Gọi hình được 1 1331133 khởi trị là A. Mỗi bước tiếp theo ta thực hiện ba Hình 3. Nền nhà với n = 8 thao tác biến hình sau đây: - Tịnh tiến A đi lên theo đường chéo để thu được hình B (xem thủ tục DichCheo). - Lật A sang phải (tức là lấy đối xứng gương qua trục tung) để thu được hình C (xem thủ tục LatPhai). - Lật A lên trên (tức là lấy đối xứng gương qua trục hoành) để thu được hình D (xem thủ tục LatLen). Chú ý rằng khi lật ta cần thực hiện thêm phép hoán đổi trị 1 và 3 cho nhau. Mỗi lần lặp như vậy ta sẽ thu được hình vuông có cạnh tăng gấp đôi hình trước. Khi v = n ta gọi thủ tục Fini để ghi ba mảnh D, A và C vào tệp kết quả. 3 3 1 1 3 2 2 1 1 2 3 3 1 1 3 2 3 3 1 2 1 1 1 1 3 3 1 2 2 3 1 1 3 2 1 1 3 2 1 1 3 3 2 1 1 2 1 1 1 1 1 1 1 2 2 3 1 2 2 3 1 2 2 3 1 1 1 1 3 3 1 1 3 3 1 1 3 3 225 Sáng tạo ...