SÁNG TẠO

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.


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.

NEN.INP
NEN.OUT

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

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;


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

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ủ tục Init để khởi trị với hình vuông cạnh v = 2 nằm ở góc dưới trái của nền nhà được biểu diễn dưới dạng một mảng hai chiều a: ba ô trong hình vuông 2 ( 2 sẽ được đ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 khởi trị là A. Mỗi bước tiếp theo ta thực hiện ba 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