Bài toán tháp Hà Nội
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (62.65 KB, 5 trang )
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
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
màu được xử lý giống như thủ tục Hà Nội cổ. Trong trường hợp tầng đáy n tại a không thể
chuyển nó làm hai giai đoạn, qua vị trí trung gian c, sau đó từ c qua b. Việc còn lại là đặc
tả điều kiện từ a có thể đến trực tiếp b cho mỗi màu cụ thể. Dễ thấy:
Nếu tầng đáy n có màu xanh: s[n]='x' thì điều kiện là b=(a mod 3)+1.
Nếu tầng đáy n có màu nâu: s[n]='n' thì điều kiện là a=( b mod 3)+1
Nếu tầng đáy n có màu trắng: s[n]='t' thì điều kiện là abs(a-b)=1
Gọi thủ tục cần xây dựng là hn(n,a,b) với uý nghĩa: chuyển ít bước nhất tháp n tầng từ vị
trí a sang vị trí b. Lại gọi Ghi(a,b) là thủ tục ghi vào tệp kết quả một lần chuyển tầng tháp
từ vị trí a sang vị trí b. Ta sẽ sử dụng hai thủ tục chuyển với hai trường hợp phân tích ở
trên.
Thủ tục chuyển trực tiếp, TrucTiep(n,a,b) bao gồm 3 bước như sau:
Hn(n-1,a,6-b-a);
Ghi(a,b)
Hn(n-1,6-a-b,b);
Thủ tục chuyển gián tiếp, GianTiep(n,a,b) bao gồm 5 bước như sau:
Hn(n-1,a,b)
Ghi(a,6-a-b)
Hn(n-1,b,a)
Ghi(6-a-b,b)
Hn(n-1,a,b)
Ta lập bảng 1 xét các tình huống cho thủ tục đệ quy Hn(n,a,b).
Màu của
tầng đang
xét s[i]
Loại toán
Từ a có thể chuyển trực
tiếp đến b
Từ a không thể chuyển trực tiếp
đến b
h Hà Nội Trực tiếp(n,a,b)
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
