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.Mục tiêu của Tháp Hà Nội
Quy tắc và ràng buộc
Đại diện trực quan của Tháp Hà Nội of the Tower of Hanoi problem
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 ở Python
def 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:
- s_pole: cực nguồn
- I_pole: Cực trung gian
- D_pole: Cực đích
Đầu ra của mã trên là:
Sự kết luận
Vì 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 —
- Trong mỗi bước, chỉ có một đĩa được phép di chuyển.
- Không có đĩa nên phủ lên đĩa nhỏ hơn của nó. Điều này có nghĩa là nếu đĩa có kích thước 2 thì nó có thể được đặt trên đĩa có kích thước 1, nhưng nó có thể được đặt trên bất kỳ đĩa nào khác lớn hơn với đĩa đó.
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.
Although we are not using that auxiliary tower, consider that.
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]
- Toh [a, b, c, 1]
- Đĩa phim từ A đến C
- Toh [b, a, c, 1]
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 -
If we consider the tower of 4 disks then we can judge that to move these 4 disks from source tower to destination tower we need to follow some steps -
- Chúng ta phải di chuyển 3 đĩa ra khỏi 4 từ tháp nguồn [tháp A] đến tháp phụ [tháp B].
- Sau đó di chuyển đĩa thứ 4 từ tháp nguồn [tháp A] đến tháp đích [tháp C].
- Và cuối cùng, di chuyển 3 đĩa từ tháp phụ [tháp B] sang tháp đích [tháp 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.
Yes, that’s the recursive function that we have to make, and that will solve our problem.
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]
- Toh [nguồn, điểm đến, phụ trợ, 3] source, destination, auxiliary, 3 ]
- Di chuyển đĩa từ nguồn đến đích bằng cách sử dụng phụ trợ.
- Toh [phụ trợ, nguồn, điểm đến, 3][ auxiliary, source, destination, 3 ]
Mã Python để giải quyết Tháp Hà Nội cho 4 đĩa sẽ-
Đầu vào- 4 đĩa.
Output-
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.
Move 1 disk from A to C using B.
Move 1 disk from B to C using A.
Move 1 disk from A to B using C.
Move 1 disk from C to A using B.
Move 1 disk
from C to B using A.
Move 1 disk from A to B using C.
Move 1 disk from A to C using B.
Move 1 disk from B to C using A.
Move 1 disk from B to A using C.
Move 1 disk from C to A using B.
Move 1 disk from B to C using A.
Move 1 disk from A to B using C.
Move 1 disk from A to C using B.
Move 1 disk from B to C using 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]
- Toh [nguồn, điểm đến, phụ trợ, 4]
- Di chuyển đĩa từ nguồn đến đích bằng cách sử dụng phụ trợ.
- Toh [phụ trợ, nguồn, điểm đến, 3]
Mã Python để giải quyết Tháp Hà Nội cho 4 đĩa sẽ-
Đầu vào- 4 đĩa.
Output — Move 1 disk from A to C using B.
Move 1 disk from A to B using C.
Move 1 disk from C to B using A.
Move 1 disk from A to C using B.
Move 1 disk from B to A using C.
Move 1 disk from B to C using A.
Move 1 disk from A to C using B.
Move 1 disk from A to B using C.
Move 1 disk from C to B using A.
Move 1 disk from C to
A using B.
Move 1 disk from B to A using C.
Move 1 disk from C to B using A.
Move 1 disk from A to C using B.
Move 1 disk from A to B using C.
Move 1 disk from C to B using A.
Move 1 disk from A to C using B.
Move 1 disk from B to A using C.
Move 1 disk from B to C using A.
Move 1 disk from A to C using B.
Move 1 disk from B to A using C.
Move 1 disk from C to B using A.
Move 1 disk from C to A using B.
Move 1 disk from B to A using C.
Move 1 disk from B
to C using A.
Move 1 disk from A to C using B.
Move 1 disk from A to B using C.
Move 1 disk from C to B using A.
Move 1 disk from A to C using B.
Move 1 disk from B to A using C.
Move 1 disk from B to C using A.
Move 1 disk from A to C using B.
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]
- Toh [nguồn, điểm đến, phụ trợ, numofdisk]
- Di chuyển đĩa từ nguồn đến đích bằng cách sử dụng phụ trợ.
- Toh [phụ trợ, nguồn, đ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,
- Đối với bất kỳ số n số đĩa nào, trước tiên, đĩa N-1 sẽ được chuyển từ nguồn sang phụ trợ.
- Sau đó, đĩa thứ n sẽ được chuyển từ tháp nguồn sang tháp đích.
- Và sau đó, đĩa N-1 sẽ được chuyển từ tháp phụ đến tháp đích.
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]:
#Base case of Recursion that when there is no disk to move
#then terminate the call.
if numOfDisk > 0:
#Recursively calling for moving the n-1 disk from source
#to auxiliary using destination.
TOH[source, destination, auxiliary, numOfDisk-1]#Moving the disk from source to destination
print[“Move 1 disk from {0} to {1} using {2}.”
.format[source, destination, auxiliary]]#Recursively asking to move remaining disk from
if __name__ == “__main__”:
#auxiliary to destination using source.
TOH[auxiliary, source, destination, numOfDisk-1]
numOfDisk = int[input[]]
TOH[‘A’, ‘B’, ‘C’, 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.
Although we can verify the time complexity by the number of steps it has taken for the different inputs.
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]
For 2 Disk — 3 Moves. [2^2–1]
For 3 Disk — 7 Moves. [2^3–1]
For 4 Disk — 15 Moves. [2^4–1]
For 5 Disk — 31 Moves. [2^5–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.
This problem seems to be impossible to solve in the real world considering the temple priest example. But in the programming using recursion. It can be easily solved.