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. | Sáng tạo trong Thuật toán và Lập trình Tập I 223 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 . 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 2 k là một số tự nhiên trong khoáng 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ữ liệu vào tệp văn bản 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. Sáng tạo trong Thuật toán và Lập trình Tập I 224 Thí dụ với n 8 ta có một cách lát nền như sau Lời giải sau đây của bạn Lê Hoàng Hải lớp 10 chuyên Tin Đại học Khoa học Tự nhiên Đại học Quốc gia Hà Nội năm 2002 . Để tính số viên gạch ta lấy ba phần tư diện tích hình vuông phủ nền nhà chia cho 3 là diện tích 1 viên gạch thước thợ sogach 3 n n div 4 div 3 8 16 3 3 3 1 1 3 2 2 1 1 2 3 3 1 1 3 2 3 3 1 2 2 3 1 1 3 2 1 1 3 3 2 1 1 2 2 3 1 2 2 3 1 1 3 3 1 1 3 3 3 3 1 1 3 1 1 3 3 1 1 3 3 3 1 3 1 1 3 1 1 3 3 1 1 3 1 2 2 3 1 1 3 3 1 1 3 3 Hình 3. Nền nhà với n 8 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 màu. Đầu tiên ta gọi thủ
