Thuật toán Tháp Hà Nội sử dụng stack Python
|
def TowerOfHanoi(n, start_rod, end_rod, transition_rod) Show ## hộp đế chỉ còn lại một đĩa in "Chuyển đĩa 1 từ thanh",start_rod,"sang thanh",end_rod ## Gọi đệ quy để di chuyển đĩa trên cùng thành chồng 2 TowerOfHanoi(n-1, start_rod, transition_rod, end_rod) in "Di chuyển đĩa",n,"từ thanh",start_rod,"sang thanh",end_rod ## Gọi đệ quy để di chuyển đĩa trên cùng thành chồng 3 TowerOfHanoi(n-1, transition_rod, end_rod, start_rod) TowerOfHanoi(n,'A','C','B') Câu đố Tháp Hà Nội do nhà toán học người Pháp Edouard Lucas phát minh năm 1883. Anh ấy được truyền cảm hứng từ một truyền thuyết kể về một ngôi đền Hindu, nơi câu đố được đưa ra cho các linh mục trẻ. Vào thời kỳ đầu, các thầy tu được trao cho ba cây sào và một chồng 64 đĩa vàng, mỗi đĩa nhỏ hơn đĩa bên dưới một chút. Nhiệm vụ của họ là chuyển tất cả 64 đĩa từ một trong ba cực sang một cực khác, với hai ràng buộc quan trọng. Họ chỉ có thể di chuyển một đĩa tại một thời điểm và họ không bao giờ có thể đặt đĩa lớn hơn lên trên đĩa nhỏ hơn. Các linh mục làm việc rất hiệu quả, cả ngày lẫn đêm, mỗi giây di chuyển một đĩa. Khi họ hoàn thành công việc của mình, truyền thuyết kể rằng, ngôi đền sẽ tan thành cát bụi và thế giới sẽ biến mất Mặc dù truyền thuyết rất thú vị, nhưng bạn không cần phải lo lắng về việc thế giới sẽ sớm kết thúc. Số lần di chuyển cần thiết để di chuyển chính xác một tháp có 64 đĩa là \(2^{64}-1 = 18,446,744,073,709,551,615\). Với tốc độ một bước mỗi giây, tức là \(584,942,417,355\) năm. Rõ ràng có nhiều điều cho câu đố này hơn là bắt mắt hiển thị một ví dụ về cấu hình của các đĩa ở giữa quá trình di chuyển từ chốt đầu tiên sang chốt thứ ba. Lưu ý rằng, như các quy tắc chỉ định, các đĩa trên mỗi chốt được xếp chồng lên nhau sao cho các đĩa nhỏ hơn luôn ở trên các đĩa lớn hơn. Nếu bạn chưa thử giải câu đố này trước đây, bạn nên thử ngay bây giờ. Bạn không cần những chiếc đĩa và cột điện cầu kỳ – một chồng sách hoặc mẩu giấy sẽ phù hợp Hình 1. Một ví dụ sắp xếp các đĩa cho tháp Hà Nội Làm thế nào để chúng ta giải quyết vấn đề này một cách đệ quy? . Giả sử bạn có một tháp gồm năm đĩa, ban đầu trên chốt một. Nếu bạn đã biết cách di chuyển một tháp bốn đĩa sang chốt hai, thì bạn có thể dễ dàng di chuyển đĩa dưới cùng sang chốt ba, sau đó di chuyển tháp bốn đĩa từ chốt hai sang chốt ba. Nhưng nếu bạn không biết cách di chuyển một tòa tháp cao bốn thì sao? . Nhưng nếu bạn không biết cách di chuyển tháp ba người thì sao? . Điều này nghe giống như một trường hợp cơ bản trong quá trình sản xuất Dưới đây là phác thảo cấp cao về cách di chuyển tháp từ cột xuất phát đến cột mục tiêu, sử dụng cột trung gian
Miễn là chúng ta luôn tuân theo quy tắc rằng các đĩa lớn hơn vẫn ở dưới cùng của ngăn xếp, chúng ta có thể sử dụng ba bước trên theo cách đệ quy, xử lý bất kỳ đĩa lớn hơn nào như thể chúng thậm chí không có ở đó. Điều duy nhất còn thiếu trong phác thảo ở trên là việc xác định một trường hợp cơ sở. Bài toán Tháp Hà Nội đơn giản nhất là tháp một đĩa. Trong trường hợp này, chúng ta chỉ cần di chuyển một đĩa đơn đến đích cuối cùng của nó. Một tháp của một đĩa sẽ là trường hợp cơ sở của chúng tôi. Ngoài ra, các bước được nêu ở trên đưa chúng ta đến trường hợp cơ bản bằng cách giảm chiều cao của tháp ở bước 1 và 3. hiển thị mã Python để giải câu đố Tháp Hà Nội Liệt kê 1 1def moveTower(height,fromPole, toPole, withPole): 2 if height >= 1: 3 moveTower(height-1,fromPole,withPole,toPole) 4 moveDisk(fromPole,toPole) 5 moveTower(height-1,withPole,toPole,fromPole) Lưu ý rằng mã trong gần giống với mô tả tiếng Anh. Chìa khóa cho sự đơn giản của thuật toán là chúng ta thực hiện hai lời gọi đệ quy khác nhau, một ở dòng 3 và một ở dòng 5. Ở dòng 3, chúng tôi di chuyển tất cả trừ đĩa dưới cùng trên tháp ban đầu sang cột trung gian. Dòng tiếp theo chỉ cần di chuyển đĩa dưới cùng đến nơi an nghỉ cuối cùng của nó. Sau đó, trên dòng 5, chúng tôi di chuyển tháp từ cực trung gian đến đỉnh của đĩa lớn nhất. Trường hợp cơ sở được phát hiện khi chiều cao tháp bằng 0; . Điều quan trọng cần nhớ về việc xử lý trường hợp cơ bản theo cách này là chỉ cần quay lại từ Hàm Liệt kê 2 def moveDisk(fp,tp):
print("moving disk from",fp,"to",tp)
Chương trình trong ActiveCode 1 cung cấp toàn bộ giải pháp cho ba đĩa Bây giờ bạn đã xem mã cho cả Tháp Hà Nội có sử dụng ngăn xếp không?Quy tắc của Câu đố Tháp Hà Nội
. Mỗi lần chỉ có thể di chuyển một đĩa. Chỉ có thể chuyển đĩa trên cùng của một ngăn xếp sang đầu của một ngăn xếp khác hoặc thanh trống . Đĩa lớn hơn không thể xếp chồng lên đĩa nhỏ hơn.
Làm cách nào để tạo Tháp Hà Nội bằng Python?Chương trình Python/ Mã nguồn . # Tạo hàm đệ quy def tower_of_hanoi(đĩa, nguồn, phụ, đích) nếu (đĩa == 1) print('Chuyển đĩa 1 từ thanh {} sang thanh {}. '. định dạng (nguồn, đích)) trở lại # tự gọi hàm tower_of_hanoi(đĩa - 1, nguồn, đích, phụ trợ) Thuật toán của Tháp Hà Nội cho 5 đĩa là gì?Trong công thức này, S là số bước và N là số đĩa. Vì vậy, nếu tháp có năm đĩa, công thức sẽ là 25-1 , tức là 31. Do đó, việc giải câu đố sẽ mất tối thiểu 31 bước.
Bài toán Tháp Hà Nội viết ra thuật toán của nó là gì?Tháp Hà Nội là một câu đố toán học trong đó chúng ta có ba thanh (A, B và C) và N đĩa . Ban đầu, tất cả các đĩa được xếp chồng lên nhau theo giá trị giảm dần của đường kính i. e. , đĩa nhỏ nhất được đặt trên cùng và chúng nằm trên thanh A. |
