Tháp Hà Nội

Hà nội cổ, một thoáng đặc tả

Vi Huynh
Bài toán 1 (Tháp Hà Nội sắc màu) Có ba cọc cắm tạiba vị trí thẳng hàng là 1,2 và 3. Trên một cọc đặt tại vị trí acó một chồng gồm n đĩa bằng gỗ hình tròn to nhỏ và có màu sắckhác nhau đôi một, được xuyên lỗ ở giữa tựa như nhũng đồng xuvà đặt chồng lên nhau để tạo ra một tòa tháp. Người chơi phảichuyển được toà tháp sang cọt đặt tại vị trí a theo các quy tắcsau:
Người chơi được sử dụng thêm một vị trí thứ 3 để đặt tạm các tầng tháp.
Mỗi lần chỉ được chuyeenr 1 ttàng tháp từ một vị trí sang một trong hai vị trí còn lại.
Không được đặt tầng tháp lớn lên tầng tháp nhỏ.
Màu sắc của mỗi tầng tháp quy định thêm về quy luật chuyển tầng như sau.
Nếu tầng tháp màu x(xanh) thì có thể chuyển tầng đó theo chiều kim đồng hồ theo quy luật của bài toán Hà Nội vòng, cụ thể là 1-> 2, 2-> 3 và 3-> 1.
Nếu tầng tháp đó có màu n (nâu) thì có thể chuyển tầng tháp đó ngược chiều kim đồng hồ, tựa như bài toán tháp Hà Nội vòng nhưng theo chiều ngược lại, cụ thể là 1-> 3, 3-> 2 và 2-> 1
Nếu tầng tháp có màu t (trắng) thì chỉ có thể chuyển tầng đó tho đường thẳng như quy luật của bài toán tháp Hà Nội thẳng, cụ thể là 1-> 2, 2?3> và 3-> 2, 2-> 1.
Nếu tầng tháp có màu h ( hồng) thì có thể chuyển từ vị trí bất kỳ sang một vị trí bất kì khác theo quy luật của bài toán tháp Hà Nội kinh điển mà ta tạm gọi là Hà Nội cổ.
Bạn h-y tìm cách giải bài toán trên với số lần chuyển ít nhất.
Thí dụ, cho dữ liệu vào
HaNoi.Inp
1 3
hnt
với ý nghĩa: chuyển tháp 3 tầng có màu mỗi tầng tính từ trên xuống là h,n và t đặt tại vị trí 1 sang vị trí 3. Ta có kết quả sau:
HaNoi.Out
1. 1-> 2
2. 1-> 3
3. 2-> 3
4. 1-> 2
5. 3-> 1
6. 3-> 2
7. 1-> 3
8. 2-> 1
9. 3-> 1
10. 2-> 3
11. 1-> 2
12. 1-> 3
13. 2-> 3
Chú ý1. Muốn dễ nhớ ta hiểu ký tự đặc trưng chomầu của mỗi tầng tháp như sau:
- x- màu xanh, phải chuyển xuôi chiều kim đồng hồ.
- n- màu nâu, phải chuyển ngược chiều kim đồng hồ.
- t- màu trắng, phải chuyển thẳng.
- h- màu hồng, chuyển tự do như Hà Nội cổ.
Chú ý 2. Thay đổi dữ liệu vào ta có thể nhận được lời giải cho các bài toán khác như sau:
Tháp Hà Nội cổ 5 tầng: 1 2 `hhhhh`
Tháp Hà Nội vòng 5 tầng: 1 2 `xxxxx`
Tháp Hà Nội vòng ngược 5 tầng: 1 2 `nnnnn`
Tháp Hà Nội thẳng 5 tầng :1 2 `ttttt`
Tháp Hà Nội đan màu 5 tầng: 1 2 `xnxnx`
....
Bài giải: Trước hết ta đọc dữ liệu từ tệp HaNoi.Inp vào các biến a,b và s, trong đó a là vị trí xuất phát, b là vị trí đích, s là xâu ký tự (string), sơiư cho biết màu của tầng tháp thứ i tính từ đỉnh tháp trở xuống. Với thí dụ trên đ- cho ta đọc được a=1, b=3, s=`hnt`. Nếu bạn đ- có kinh nghiệm nhận biết các cấu hình buộc phải có như trong bài các dạng toán tháp Hà Nội thì bạn có thể giải bài này khá dễ dàng. Xin nhắc lại nguyên tắc này như sau: Giả sử ta quan sát một người chuyển tháp giỏi, tức là anh ta có thể giải được bài toán trên với số lần chuyển ít nhất. Mỗi khi anh ta chuyển một tầng tháp ta chụp một tấm ảnh ghi nhận cấu hình của bài toán. Trong tập ảnh thu được có những bức ảnh nào chắc chắng phải có? Dựa vào các bức ảnh buộc phải có đó ta có thể viết ngay một lời giải đệ quy cho bài toán. Đầu tiên ta thấy rằng muốn chuyển được tháp n tầng từ a sang b ta phải chuyển được tầng đáy tháp tức là dỡ được n-1 tầng trên của tháp tai vị trí a. Giả sử bạn đ- dỡ xong và dĩ nhiên bạn phải đặt tạm n-1 tầng này vào vị trí c. Tầng đáy thứ n tại vịn trí a đựơc tự do. Thử hỏi bạn có thể chuyên nó sang vị trí b được không? Rõ dàng là không phải lúc nào cũng