Hướng dẫn what is tower of hanoi problem in python? - vấn đề tower of hanoi trong python là gì?
|
Tháp Hà Nội là một vấn đề toán học (câu đố) bao gồm 3 cực và số lượng đĩa, mỗi đĩa có đường kính khác nhau. Mục tiêu hoặc mục tiêu của vấn đề này là chuyển tất cả các đĩa ’n từ cực nguồn sang cực đích theo cách mà chúng ta có được sự sắp xếp tương tự của các đĩa như trước đây. Nhưng mục tiêu này phải đạt được bằng cách tuân thủ các quy tắc. Các ràng buộc phải được thỏa mãn trong khi giải quyết vấn đề là - Hình ảnh sau đây cho thấy giải pháp riêng cho một tòa tháp Hà Nội với 3 cực (nguồn, trung gian, đích) và 3 đĩa. Mục tiêu là di chuyển tất cả 3 đĩa từ cực A sang cực C. Như chúng ta có thể thấy từ giải pháp trên, số lượng di chuyển cần thiết cho 3 đĩa = 8. Vì vậy, một công thức tổng quát cho tổng số lượng di chuyển chúng ta cần là: Tổng số di chuyển = n2 & nbsp; - 1 Trong đó ’n, là tổng số không. của đĩa. Giải quyết vấn đề của Hà Hà hội ở Pythondef TowerOfHanoi(n , s_pole, d_pole, i_pole):
if n == 1:
print("Move disc 1 from pole",s_pole,"to pole",d_pole)
return
TowerOfHanoi(n-1, s_pole, i_pole, d_pole)
print("Move disc",n,"from pole",s_pole,"to pole",d_pole)
TowerOfHanoi(n-1, i_pole, d_pole, s_pole)
n = 3
TowerOfHanoi(n, 'A', 'C', 'B')
# A, C, B are the name of poles
Trong mã trên, chúng tôi gọi chức năng của chúng tôi TowerofHanoi đã đệ quy cho 3 đĩa. Here:
Đầu ra của mã trên là: Sự kết luậnVì vậy, đây là cách chúng tôi giải quyết vấn đề của Tháp Hà Nội. Mã này có thể được khái quát cho bất kỳ số lượng đĩa. Vì vậy, nếu bạn muốn giải pháp cho 4 đĩa, chỉ cần thay đổi giá trị của n từ 3 thành 4 là n = 4 và đầu ra sẽ được hiển thị cho 4 đĩa, v.v. Tháp Hà Nội là gì? Tháp Hà Nội là vấn đề trong đó có 3 tòa tháp, hãy để đánh dấu nó với tên Tháp A, Tower B và Tower C. và trong Tower A, chúng tôi có n số đĩa. Và nhiệm vụ là di chuyển tất cả các đĩa từ tháp A sang tháp C bằng Tháp B. Nguồn gốc của vấn đề- Vấn đề này được tạo ra bởi nhà toán học người Pháp édouard Lucas trong thế kỷ 19. Vấn đề này có liên quan đến thần thoại Ấn Độ giáo. Và đây cũng được gọi là Tháp Brahmas hoặc Tháp Lucas. Vấn đề này được cho là không thể giải quyết được. Bởi vì có một câu chuyện đằng sau điều này. Và điều đó có liên quan đến các linh mục của ngôi đền. Người ta nói rằng tại Đền Kashi Vishwanath ở Ấn Độ, có một chồng gồm 64 đĩa vàng được giữ liên tục trên một thứ khác. Và các linh mục đang cố gắng sắp xếp lại đĩa đó trên một tòa tháp khác từ nhiều năm trước. Họ đã từng tin rằng một khi tất cả 64 đĩa được di chuyển thành công thì thế giới sẽ kết thúc. Và phiên bản khác của câu chuyện là về địa điểm (Hà Nội) ở Việt Nam. Các tấm vàng thuộc về đó. Câu đố toán học này được cho là không thể giải quyết được. Nhưng sử dụng sự trợ giúp của đệ quy, nó trở nên rất dễ giải quyết. Đệ quy là gì? Về mặt lập trình, một đệ quy là một chức năng tự gọi. Có một trường hợp cơ sở trong đệ quy giúp chấm dứt đệ quy. Nếu trường hợp cơ sở không có mặt thì nó sẽ không bao giờ chấm dứt.In terms of programming, A recursion is a function that calls itself. There is a base case in the recursion that helps to terminate the recursion. If the base case is not present then it will never terminate. Các quy tắc để giải quyết vấn đề Tháp Hà Nội -Tower of Hanoi Problem —
Vì vậy, 2 điều kiện này phải được áp dụng để di chuyển các đĩa này từ Tháp A sang tháp C. và chỉ với 2 tòa tháp, chúng ta không thể di chuyển đĩa. Vì vậy, chúng tôi đã lấy một tòa tháp phụ (tháp B) để đạt được điều đó. Vì vậy, điều kiện bổ sung cũng cần phải được thỏa mãn là chúng ta phải sử dụng Tower B để giữ đĩa trên cơ sở tạm thời vì chúng ta có thể đặt đĩa ra ngoài tháp. Báo cáo vấn đề: Làm thế nào chúng ta có thể giải quyết vấn đề này bằng cách sử dụng sự trợ giúp của đệ quy? Để hiểu giải pháp tốt hơn. Hãy để hiểu các bước chúng ta cần tuân theo khi chúng ta chỉ có 1 đĩa. Bởi vì đó sẽ giống như một trường hợp cơ sở cho giải pháp của chúng tôi. Vì vậy, chỉ trong 1 đĩa di chuyển, chúng tôi chỉ cần di chuyển 1 đĩa đó, từ nguồn đến đích. Sau đó, thuật toán giống như - di chuyển đĩa từ nguồn đến đích bằng cách sử dụng tháp phụ. Mặc dù chúng tôi không sử dụng tháp phụ đó, hãy xem xét điều đó.Move disk from source to destination
using the auxiliary tower. Sau đó đối với 2 đĩa, các bước nên giống như - Vì vậy, thuật toán cho 2 đĩa di chuyển sẽ là - Toh (a, b, c, 2)
Sau đó, sử dụng phương pháp này, chúng ta có thể giải quyết vấn đề này với bất kỳ số lượng đĩa nào không? Vì vậy, hãy để Lừa lấy một ví dụ để giải quyết nó với sự trợ giúp của 4 đĩa. Nếu chúng ta xem xét tháp của 4 đĩa thì chúng ta có thể đánh giá rằng để di chuyển 4 đĩa này từ tháp nguồn sang tháp đích, chúng ta cần làm theo một số bước -
Vấn đề đã được giải quyết, chỉ với 3 bước đơn giản để kết thúc giải pháp của vấn đề. Nhưng điều kiện 1 được nêu để giải quyết vấn đề là chúng ta chỉ cần di chuyển 1 đĩa cùng một lúc. Nhưng ở đây chúng tôi đang di chuyển 3 đĩa cùng một lúc (di chuyển 3 đĩa từ A đến B và di chuyển 3 đĩa từ B đến C). Làm thế nào để chúng ta giải quyết vấn đề này?, With just 3 simple steps to have concluded the solution of the problem. But the condition 1 that is stated for solving the problem is that we need to move only 1 disk at a time. But here we are moving 3 disks at a time (Move 3 Disks from A to B and Move 3 disks from B to C). How do we solve this problem? Vì vậy, tại sao chúng ta không thể làm một điều mà ở bước đầu tiên, thay vì di chuyển 3 đĩa, chúng ta có thể yêu cầu ai đó di chuyển 1 đĩa từ nguồn đến đích, sau đó người đó hỏi người khác, và sau đó chúng ta tiến hành phù hợp? Vâng, đó là chức năng đệ quy mà chúng ta phải thực hiện, và điều đó sẽ giải quyết vấn đề của chúng ta. Bây giờ, hãy để Lừa đi sâu vào từng bước để giải câu đố này - Chúng tôi đã cung cấp tổng cộng 4 đĩa và 3 tòa tháp ‘A,’ B, và ‘C ,. Nhiệm vụ là chuyển đĩa này từ tháp ‘A (nguồn) sang tháp‘ B, (điểm đến) bằng cách tuân theo các quy tắc của Tháp Hà Nội. Vì vậy, các bước để giải quyết vấn đề của Hà Hà với 4 đĩa là- Được - Các bước - Bước 1: Di chuyển đĩa từ A sang B bằng C: Bước 2: Di chuyển đĩa từ A sang C bằng B: Bước 3: Di chuyển đĩa từ B sang C bằng cách sử dụng A: Bước 4: Di chuyển đĩa từ A sang B bằng C: Bước 5: Di chuyển đĩa từ C sang A bằng B: Bước 6: Di chuyển đĩa từ C sang B bằng cách sử dụng A: Bước 7: Di chuyển đĩa từ A sang B bằng C: Bước 8: Di chuyển đĩa từ A sang C bằng B: Bước 9: Di chuyển đĩa từ B sang C bằng cách sử dụng A: Bước 10: Di chuyển đĩa từ B sang A bằng C:+ Bước 11: Di chuyển đĩa từ C sang A bằng B: Bước 12: Di chuyển đĩa từ B sang C bằng cách sử dụng A: Bước 13: Di chuyển đĩa từ A sang B bằng C: Bước 14: Di chuyển đĩa từ A sang C bằng B: Bước 15: Di chuyển đĩa từ B đến C bằng A. Vì vậy, thuật toán cho giải pháp của Tháp Hà Nội với 4 bước sẽ là - Toh (nguồn, phụ trợ, điểm đến, 4)
Mã Python để giải quyết Tháp Hà Nội cho 4 đĩa sẽ- Đầu vào- 4 đĩa. Di chuyển 1 đĩa từ A đến B bằng cách sử dụng đĩa C.Move 1 từ A đến C bằng cách sử dụng đĩa B.Move 1 từ B đến C bằng cách sử dụng đĩa 1 từ A đến B bằng cách sử dụng đĩa C.Move 1 từ C sang A bằng B. Di chuyển 1 đĩa từ C sang B bằng cách sử dụng đĩa 1 từ A đến B bằng cách sử dụng đĩa C.Move 1 từ A đến C bằng cách sử dụng đĩa B.Move 1 từ B đến C bằng cách sử dụng đĩa a.move 1 từ B đến A bằng cách sử dụng C. Di chuyển 1 đĩa từ C sang A sử dụng đĩa B.Move 1 từ B đến C bằng cách sử dụng đĩa a.move 1 từ A đến B bằng cách sử dụng đĩa C.Move 1 từ A đến C bằng cách sử dụng đĩa B.Move 1 từ B đến C bằng A. Bây giờ hãy xem xét giải pháp vấn đề với 5 đĩa- Chúng tôi đã được cung cấp 5 ngăn xếp đĩa được sắp xếp trên tháp ‘một nguồn. Bây giờ chúng ta cần di chuyển đĩa này từ nguồn sang tháp đích ‘C, theo Tháp quy tắc Hà Nội. Vì vậy, các bước để giải câu đố với 5 đĩa sẽ - Được - Các bước - Bước 1: Di chuyển 1 đĩa từ A sang C bằng B. Bước 2: Di chuyển 1 đĩa từ A sang B bằng cách sử dụng C. Bước 3: Di chuyển 1 đĩa từ C sang B bằng A. Bước 4: Di chuyển 1 đĩa từ A sang C bằng B. Bước 5: Di chuyển 1 đĩa từ B sang A Sử dụng C. Bước 6: Di chuyển 1 đĩa từ B đến C bằng A. Bước 7: Di chuyển 1 đĩa từ A sang C bằng B. Bước 8: Di chuyển 1 đĩa từ A sang B bằng cách sử dụng C. Bước 9: Di chuyển 1 đĩa từ C sang B bằng A. Bước 10: Di chuyển 1 đĩa từ C sang A Sử dụng B. Bước 11: Di chuyển 1 đĩa từ B sang A Sử dụng C. Bước 12: Di chuyển 1 đĩa từ C sang B bằng A. Bước 13: Di chuyển 1 đĩa từ A sang C bằng B. Bước 14: Di chuyển 1 đĩa từ A sang B bằng cách sử dụng C. Bước 15: Di chuyển 1 đĩa từ C sang B bằng A. Bước 16: Di chuyển 1 đĩa từ A sang C bằng B. Bước 17: Di chuyển 1 đĩa từ B sang A Sử dụng C. Bước 18: Di chuyển 1 đĩa từ B đến C bằng A. Bước 19: Di chuyển 1 đĩa từ A sang C bằng B. Bước 20: Di chuyển 1 đĩa từ B sang A Sử dụng C. Bước 21: Di chuyển 1 đĩa từ C sang B bằng A. Bước 22: Di chuyển 1 đĩa từ C sang A Sử dụng B. Bước 23: Di chuyển 1 đĩa từ B sang A Sử dụng C. Bước 24: Di chuyển 1 đĩa từ B đến C bằng A. Bước 25: Di chuyển 1 đĩa từ A sang C bằng B. Bước 26: Di chuyển 1 đĩa từ A sang B bằng cách sử dụng C. Bước 27: Di chuyển 1 đĩa từ C sang B bằng A. Bước 28: Di chuyển 1 đĩa từ A sang C bằng B. Bước 29: Di chuyển 1 đĩa từ B sang A Sử dụng C. Bước 30: Di chuyển 1 đĩa từ B đến C bằng A. Bước 31: Di chuyển 1 đĩa từ A sang C bằng B. Vì vậy, thuật toán cho giải pháp của tháp Hà Nội với 5 đĩa sẽ là - Toh (nguồn, phụ trợ, điểm đến, 5)
Mã Python để giải quyết Tháp Hà Nội cho 4 đĩa sẽ- Đầu vào- 4 đĩa. Sau khi phân tích 2 ví dụ về giải quyết Tháp Hà Nội với 4 và 5 đĩa, thuật toán cho N số đĩa sẽ là - Toh (nguồn, phụ trợ, điểm đến, numofdisk)
Giải thích về thuật toán - Giống như chúng tôi đã phân tích ở trên cho giải pháp 4 đĩa,
Và các động tác N-1 này được gọi là đệ quy sao cho cuộc gọi chức năng riêng lẻ có trách nhiệm xử lý di chuyển đĩa 1 trong mỗi cuộc gọi. Chương trình Python để giải quyết Tháp Hà Nội là - def TOH(source, auxiliary, destination, numOfDisk): Phân tích độ phức tạp thời gian - Nếu chúng tôi kiểm tra các bước để giải quyết vấn đề này thì chúng tôi thấy rằng trước tiên nó đang kêu gọi một cách đệ quy vấn đề (n-1), thì đó là một bước không đổi. Và một lần nữa kêu gọi các bước (n-1). Vì vậy, trong thuật ngữ toán học, chúng ta có thể nêu hàm thời gian là-t (n) = 2T (n-1) +1. T(n) = 2T(n-1) +1. Vì vậy, nếu chúng ta giải phương trình này thì độ phức tạp của thời gian sẽ là O (2N). Mặc dù chúng tôi có thể xác minh độ phức tạp về thời gian theo số bước nó đã thực hiện cho các đầu vào khác nhau. Cho 1 đĩa - 1 di chuyển. (2^1 bóng1) cho 2 đĩa - 3 di chuyển. (2^2 bóng1) cho 3 đĩa - 7 di chuyển. (2^3 bóng1) cho 4 đĩa - 15 di chuyển. (2^4 bóng1) cho 5 đĩa - 31 di chuyển. (2^5 trận1)(2^1–1) Vì vậy, mức độ của phương trình O (2N-1) là O (2n). O(2n-1) is O(2n). Độ phức tạp không gian - Vì thời gian được thực hiện O (2N), chúng tôi đang sử dụng đệ quy để giải quyết vấn đề. Vì vậy, độ phức tạp không gian cũng sẽ là O (2N). Bởi vì đệ quy sử dụng ngăn xếp cuộc gọi. — Since the time is taken of O(2n), we are using recursion for solving the problem. So the space complexity also will be O(2n). Because recursion uses call stack. Sự kết luận - Tháp Hà Nội là một câu đố toán học được phát hiện bởi nhà toán học người Pháp Édouard Lucas. Và câu đố này dựa trên một số thần thoại. Vấn đề này dường như là không thể giải quyết trong thế giới thực khi xem xét ví dụ của linh mục đền thờ. Nhưng trong chương trình sử dụng đệ quy. Nó có thể dễ dàng giải quyết. Tháp của vấn đề Hà Nội là gì?Tháp Hà Nội (còn được gọi là vấn đề của Đền Benares hoặc Tháp của Tháp Brahma hoặc Lucas và đôi khi được nhiều người làm việc, hoặc đơn giản là Pyramid Puzz có thể trượt lên bất kỳ thanh.a mathematical game or puzzle consisting of three rods and a number of disks of various diameters, which can slide onto any rod.
Mục tiêu của Tower of Hà Nội là gì?Mục tiêu của trò chơi là chuyển toàn bộ chồng đĩa từ một thanh này sang thanh khác theo ba quy tắc này: chỉ có thể di chuyển một đĩa một lần.Chỉ có thể di chuyển đĩa trên cùng từ một ngăn xếp trên đỉnh của một ngăn xếp khác hoặc một thanh trống.Các đĩa lớn hơn không thể được đặt trên đỉnh của các đĩa nhỏ hơn.to shift the entire stack of disks from one rod to another rod following these three rules : Only one disk can be moved at a time. Only the uppermost disk from one stack can be moved on to the top of another stack or an empty rod. Larger disks cannot be placed on the top of smaller disks.
Tháp công thức Hà Nội là gì?Tháp ban đầu của câu đố Hà Nội, được phát minh bởi nhà toán học người Pháp Edouard Lucas vào năm 1883, kéo dài "cơ sở 2".Đó là - số lượng di chuyển của số đĩa K là 2^(K -1) và tổng số lượng di chuyển cần thiết để giải câu đố với các đĩa n là 2^n - 1.the number of moves of disk number k is 2^(k-1), and the total number of moves required to solve the puzzle with N disks is 2^N - 1.
Tháp Hà Nội minh họa với một ví dụ là gì?Tháp của Hà Nội, là một câu đố toán học bao gồm ba tòa tháp (chốt) và nhiều hơn một vòng như được mô tả - những chiếc nhẫn này có kích thước khác nhau và xếp theo thứ tự tăng dần, tức là cái nhỏ hơn nằm trên cái lớn hơn. |
