Xem thảo luận
Cải thiện bài viết
Lưu bài viết
Xem thảo luận
Cải thiện bài viết
Lưu bài viết
Đọc
1] Only one disk can be moved at a time.
2] Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3] No disk may be placed on top of a smaller disk.
Note: Transferring the top n-1 disks from source rod to Auxiliary rod can again be thought of as a fresh problem and can be solved in the same
manner.
Python3
Bàn luận
Tower of Hà Nội là một câu đố toán học nơi chúng tôi có ba thanh và đĩa N. Mục tiêu của câu đố là di chuyển toàn bộ ngăn xếp sang một thanh khác, tuân theo các quy tắc đơn giản sau: & nbsp; 1] Chỉ có thể di chuyển một đĩa. các ngăn xếp và đặt nó lên trên một ngăn xếp khác, tức là một đĩa chỉ có thể được di chuyển nếu đó là đĩa trên cùng trên ngăn xếp. & nbsp; 3] không có đĩa nào được đặt trên đầu của một đĩa nhỏ hơn. 1 đĩa từ thanh nguồn đến thanh phụ trợ một lần nữa có thể được coi là một vấn đề mới và có thể được giải quyết theo cách tương tự. & Nbsp;
def TowerOfHanoi[n , source, destination, auxiliary]:
def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']2Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 2 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C Chuyển đĩa 3 từ cọc A sang cọc B Chuyển đĩa 1 từ cọc C sang cọc A Chuyển đĩa 2 từ cọc C sang cọc B Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 4 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C Chuyển đĩa 2 từ cọc B sang cọc A Chuyển đĩa 1 từ cọc C sang cọc A Chuyển đĩa 3 từ cọc B sang cọc C Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 2 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C0
if n==
def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']011def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']2def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']3 def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']4def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']5def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']6def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']7def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']8
Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 2 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C Chuyển đĩa 3 từ cọc A sang cọc B Chuyển đĩa 1 từ cọc C sang cọc A Chuyển đĩa 2 từ cọc C sang cọc B Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 4 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C Chuyển đĩa 2 từ cọc B sang cọc A Chuyển đĩa 1 từ cọc C sang cọc A Chuyển đĩa 3 từ cọc B sang cọc C Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 2 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C2
Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 2 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C Chuyển đĩa 3 từ cọc A sang cọc B Chuyển đĩa 1 từ cọc C sang cọc A Chuyển đĩa 2 từ cọc C sang cọc B Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 4 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C Chuyển đĩa 2 từ cọc B sang cọc A Chuyển đĩa 1 từ cọc C sang cọc A Chuyển đĩa 3 từ cọc B sang cọc C Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 2 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C3
def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']0def9
Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 2 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C Chuyển đĩa 3 từ cọc A sang cọc B Chuyển đĩa 1 từ cọc C sang cọc A Chuyển đĩa 2 từ cọc C sang cọc B Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 4 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C Chuyển đĩa 2 từ cọc B sang cọc A Chuyển đĩa 1 từ cọc C sang cọc A Chuyển đĩa 3 từ cọc B sang cọc C Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 2 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C2223
def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']0TowerOfHanoi[n , source, destination, auxiliary]:3TowerOfHanoi[n , source, destination, auxiliary]:4TowerOfHanoi[n , source, destination, auxiliary]:5TowerOfHanoi[n , source, destination, auxiliary]:6TowerOfHanoi[n , source, destination, auxiliary]:5TowerOfHanoi[n , source, destination, auxiliary]:8TowerOfHanoi[n , source, destination, auxiliary]:9
def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']3 def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']4Chuyển đĩa 1 từ cọc A sang cọc B
Chuyển đĩa 2 từ cọc A sang cọc C
Chuyển đĩa 1 từ cọc B sang cọc C
Chuyển đĩa 3 từ cọc A sang cọc B
Chuyển đĩa 1 từ cọc C sang cọc A
Chuyển đĩa 2 từ cọc C sang cọc B
Chuyển đĩa 1 từ cọc A sang cọc B
Chuyển đĩa 4 từ cọc A sang cọc C
Chuyển đĩa 1 từ cọc B sang cọc C
Chuyển đĩa 2 từ cọc B sang cọc A
Chuyển đĩa 1 từ cọc C sang cọc A
Chuyển đĩa 3 từ cọc B sang cọc C
Chuyển đĩa 1 từ cọc A sang cọc B
Chuyển đĩa 2 từ cọc A sang cọc C
Chuyển đĩa 1 từ cọc B sang cọc C
9____________def1def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']6def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']7def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']8
Move disk 1 from source A to destination C Move disk 2 from source A to destination B Move disk 1 from source C to destination B Move disk 3 from source A to destination C Move disk 1 from source B to destination A Move disk 2 from source B to destination C Move disk 1 from source A to destination C Move disk 4 from source A to destination B Move disk 1 from source C to destination B Move disk 2 from source C to destination A Move disk 1 from source B to destination A Move disk 3 from source C to destination B Move disk 1 from source A to destination C Move disk 2 from source A to destination B Move disk 1 from source C to destination B
TowerOfHanoi[n , source, destination, auxiliary]:0= TowerOfHanoi[n , source, destination, auxiliary]:2O[2n]
Đầu raO[n]
Độ phức tạp về thời gian: O [2N]
Bài toán Tháp Hà Nội là một bài toán rất nổi tiếng và kinh điển, rất thích hợp để minh họa cho thuật toán đệ quy.
Bài toán Tháp Hà Nội là gì?
Có 3 chiếc cọc được đánh dấu lần lượt là A, B, C và
nchiếc đĩa. Các đĩa này có kích thước [đường kính] khác nhau và mỗi đĩa đều có một lỗ ở giữa để lồng vào cọc. Ban đầu, các đĩa đều nằm ở cọc A, trong đó, đĩa có đường kính nhỏ hơn luôn ở nằm trên đĩa đường kính lớn hơn.
Yêu cầu : Chuyển n đĩa từ cọc A sang cọc C với các điều kiện sau: Chuyển n đĩa từ cọc A sang cọc C với các điều kiện sau:
- Mỗi lần chỉ chuyển được
def TowerOfHanoi[n , source, destination, auxiliary]: if n==1: print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination] return TowerOfHanoi[n-1, source, auxiliary, destination] print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination] TowerOfHanoi[n-1, auxiliary, destination, source] # Ví dụ với n = 4 n = 4 TowerOfHanoi[n,'A','C','B']0 đĩa - Trong quá trình chuyển, đĩa nhỏ phải luôn nằm trên đĩa lớn hơn.
- Cho phép sử dụng cọc B làm cọc trung gian
Cách giải Bài toán Tháp Hà Nội
Chúng ta sẽ xét các trường hợp của n:
- Trường hợp đơn giản nhất,
- Với
- Với
nđĩa từ cọc nguồn sang cọc đích, ta cần chuyển
Ví dụ, với if1, chúng ta phải chuyển 7 lần tất cả như hình sau.
Mã nguồn chương trình bằng Python:
def TowerOfHanoi[n , source, destination, auxiliary]:
if n==1:
print["Chuyển đĩa 1 từ cọc",source,"sang cọc",destination]
return
TowerOfHanoi[n-1, source, auxiliary, destination]
print["Chuyển đĩa",n,"từ cọc",source,"sang cọc",destination]
TowerOfHanoi[n-1, auxiliary, destination, source]
# Ví dụ với n = 4
n = 4
TowerOfHanoi[n,'A','C','B']Kết quả chạy chương trình:
Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 2 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C Chuyển đĩa 3 từ cọc A sang cọc B Chuyển đĩa 1 từ cọc C sang cọc A Chuyển đĩa 2 từ cọc C sang cọc B Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 4 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C Chuyển đĩa 2 từ cọc B sang cọc A Chuyển đĩa 1 từ cọc C sang cọc A Chuyển đĩa 3 từ cọc B sang cọc C Chuyển đĩa 1 từ cọc A sang cọc B Chuyển đĩa 2 từ cọc A sang cọc C Chuyển đĩa 1 từ cọc B sang cọc C