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

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
chuyển được. Chẳng hạn, nếu tầng đáy này màu xanh và a=1, b=3 thì theo quy luật chuyển
tầng cho màu xanh bạn không thể chuyển tầng này từ vị trí 1 sang vị trí 3 mà chỉ có thể
chuyển sang vị trí 2 mà thôi. Tóm lại, trước khi dỡ n-1 tầng trên của tháp bạn phải xác định
xem tầng đáy có thể chuyển trực tiếp từ a sang b hay không. Như vậy, với mỗi cấu hình ta
phải xét màu của tầng tháp cuối cùng đặt tại a là s[n]. Với mỗi s[n] ta xét hai trường hợp:
Trường hợp 1. Tầng đáy n từ a có thể chuyển trực tiếp sang b.
Trường hợp 2. Tầng đáy n từ a không thể chuyển trực tiếp sang b.
Trong các cấu hình dưới đây bạn không nên hiểu là vị trí a đặt cạnh vị trí b. Các vị trí có
thể bố trí thoải mái, miễn là chúng khác nhau.
Các cấu hình buộc phải có cho trường hợp 1 là:
(a:[1..n], b:[], c:[])- cấu hình ban đầu (giả thiết)
(a:[n], b:[], c:[1..n-1] )- cất tạm n-1 tầng trên từ a sang c
(a:[], b:[n], c:[1..n-1])? rồi chuyển trực tiếp tầng thứ n từ a qua b
(a:[], b:[1..n], c:[])? cấu hình cuối cùng (kết luận);
Với trường hợp 2 ta thấy sau khi giải phóng n-1 tầng trên của tháp khỏi vị trí a ta vẫn
không thể chuyển trực tiếp tầng cuối cùng từ a sang b được cho nên ta phải thực hiện 2 lần
di chuyển tầng cuối cùng, cụ thể là: Trước hết chuyển trực tiếp tầng đó qua c rồi mới
chuyển trực tiếp tầng nàu từ c qua b.
(a:[1..n], b:[], c:[])- cấu hình ban đầu (giả thiết)
(a:[n], b:[1..n-1], c:[] )- cất tạm n-1 tầng trên từ a sang b
(a:[], b:[1..n-1], c:[n])? rồi chuyển trực tiếp tầng thứ n từ a qua c
(a:[1..n-1], b:[], c:[n] )- cất tạm n-1 tầng trên từ b sang a
(a:[1..n-1], b:[n], c:[] )- rồi chuyển trực tiếp tầng thứ n từ c qua b
(a:[], b:[1..n], c:[])? cấu hình cuối cùng (kết luận);
Tổng kết lại ta thấy, trong trường hợp tầng đáy n tại a có thẻ chuyển trực tiếp đến b, tháp

x
Hà Nội vòng
xuôi
B=ă mod 3)+1
Tructiep(n,a,b)
B<>(a Mod 3)+1
GianTiep(n,a,b)
n
Hà Nội vòng
ngược
A=(b Mod 3)+1
TrucTiep(n,a,b)
A<>(b Mod 3)+1
GianTiep(n,a,b)
t Hà Nội thẳng
Abs(a-b)=1
TrucTiep(n,a,b)
Abs(a-b)=1
GianTiep(n,a,b)
Bảng 1.Các điều kiện và phương thức xử lý bàitoán tháp Hà Nội sắc màu tổng quát. Các ô
cùng màu trong bảng đượcxử lý giống nhau. Với màu t, nếu a và b không kề nhau thì c
chính làvị trí nằm giữa a và b, tức là c=6-a-b=2;
Vi Huynh