Thuật toán Tháp Hà Nội: Python, C++ Mã

Tháp Hà Nội là gì?

Tháp Hà Nội là một câu đố toán học bao gồm ba thanh và nhiều đĩa được đặt chồng lên nhau. Nó còn được gọi là Tháp Brahma hay tháp Lucas, như nhà toán học người Pháp Edouard Lucas đã giới thiệu vào năm 1883. Câu đố này dựa trên truyền thuyết về việc di chuyển các đĩa vàng giữa ba thanh.

Câu đố này có ba thanh và một số lượng đĩa xếp chồng lên nhau. Những thanh này được thiết kế như những tháp tuần hoàn. Vì vậy, các đĩa có đường kính lớn hơn được xếp ở phía dưới và các đĩa nhỏ hơn được xếp ở trên.

Ban đầu, chúng ta được cấp ba cái chốt hoặc que. Và một trong số chúng (A, được hiển thị trong ví dụ) có tất cả các đĩa được xếp chồng lên nhau. Chúng tôi mong muốn di chuyển toàn bộ chồng đĩa từ thanh này (A) sang thanh khác (C) bằng cách tuân theo một số quy tắc cụ thể.

Đây là thiết lập ban đầu của câu đố-

Và đây là mục tiêu cuối cùng-

Quy định của Tháp Hà Nội

Dưới đây là một số quy tắc cần thiết cho Tháp Hà Nội:

• Trạng thái ban đầu của câu đố này là tất cả các đĩa sẽ được xếp thành một thanh.
• Trạng thái cuối cùng là tất cả các đĩa từ thanh một sẽ được xếp chồng lên thanh hai hoặc thanh ba.
• Chúng ta có thể di chuyển một đĩa từ thanh này sang thanh khác vào bất kỳ thời điểm nào.
• Chúng ta chỉ có thể di chuyển đĩa trên cùng khỏi thanh.
• Không thể đặt một đĩa lên trên một đĩa khác nhỏ hơn.

Truyền thuyết gốc là về việc di chuyển 64 đĩa. Các linh mục có thể di chuyển một đĩa tại một thời điểm theo các quy tắc. Theo truyền thuyết, có một lời tiên tri rằng thế giới sẽ kết thúc nếu họ có thể hoàn thành hành động. Trong phần độ phức tạp thời gian, chúng tôi sẽ chỉ ra rằng một thiết lập Tower of Hanoi gồm n đĩa sẽ tốn 2^n – 1 lần di chuyển.

Vì vậy, nếu các linh mục có thể cần 1 giây để di chuyển các đĩa, tổng thời gian họ cần để giải câu đố sẽ là 2^64 – 1 giây hoặc 584,942,417,356 năm, 26 ngày, 7 giờ và 15 giây.

Thuật toán Tháp Hà Nội

Một cách tổng quát để giải Tháp Hà Nội là sử dụng thuật toán đệ quy. Đầu tiên, chúng ta cần quyết định hai thanh hoặc chốt làm nguồn và đích, còn chốt dự phòng sẽ là phụ trợ hoặc trợ giúp.

Dưới đây là các bước giải câu đố Tháp Hà Nội:

• Di chuyển n-1 đĩa trên cùng từ chốt nguồn sang chốt trợ giúp.
• Sau đó, di chuyển đĩa thứ n từ chốt nguồn sang chốt đích.
• Cuối cùng, di chuyển n-1 đĩa còn lại từ chốt trợ giúp sang chốt đích.

Chú thích: Nếu chúng ta có một đĩa đơn, chúng ta có thể di chuyển trực tiếp nó từ nguồn tới đích.

Cách giải câu đố Tháp Hà Nội

Hãy minh họa thuật toán cho ba đĩa và coi chốt A là nguồn, chốt B là trợ giúp và chốt C là đích

Bước 1) Ban đầu, tất cả các đĩa sẽ được xếp chồng lên cọc A.

Ở giai đoạn này:

Nguồn = Chốt A
Đích = Chốt C
Người trợ giúp = Chốt B

Bây giờ, chúng ta cần di chuyển n-1 đĩa hàng đầu từ nguồn sang trợ giúp.

Lưu ý: Mặc dù chúng tôi chỉ có thể di chuyển một đĩa mỗi lần, nhưng nó sẽ chuyển vấn đề của chúng tôi từ vấn đề 3 đĩa sang vấn đề 2 đĩa, đó là một cuộc gọi đệ quy.

Bước 2) Khi chúng ta gọi một cuộc gọi đệ quy từ chốt A và đích đến là chốt B, chúng ta sẽ sử dụng chốt C làm trợ giúp.

Lưu ý rằng chúng ta lại đang ở giai đoạn một của bài toán tháp Hà Nội cho hai đĩa.

Bây giờ chúng ta cần di chuyển n-1 hoặc một đĩa từ nguồn sang trợ giúp, di chuyển đĩa nhỏ nhất từ ​​chốt A sang chốt C.

Ở giai đoạn này:

Nguồn = chốt A
Đích = chốt B
Người trợ giúp = chốt C

Bước 3) Sau đó, theo thuật toán của chúng tôi, nhu cầu đĩa thứ n hoặc thứ 2 sẽ được chuyển vào đích hoặc chốt B.

Ở giai đoạn này:

Nguồn = chốt A
Đích = chốt B
Người trợ giúp = chốt C

Bước 4) Bây giờ, chúng tôi sẽ di chuyển n-1 đĩa hoặc đĩa một từ trợ giúp hoặc chốt C đến đích hoặc chốt B theo giai đoạn thứ ba của thuật toán của chúng tôi.

Ở giai đoạn này:

Nguồn = chốt A
Đích = chốt B
Người trợ giúp = chốt C

Bước 5) Sau khi hoàn thành lệnh gọi đệ quy, chúng ta sẽ quay lại cài đặt trước đó khi ở giai đoạn đầu tiên của thuật toán.

Bước 6) Bây giờ, trong giai đoạn thứ hai, chúng ta sẽ di chuyển nguồn đến đích, tức là di chuyển đĩa 3 sang chốt C từ chốt A.

Ở giai đoạn này:

Nguồn = chốt A
Đích = chốt C
Người trợ giúp = chốt B

Bước 7) Bây giờ chúng ta có thể thấy điều đó

d là di chuyển các đĩa còn lại từ trợ giúp (peg B) đến đích (peg C). Chúng tôi sẽ sử dụng nguồn ban đầu hoặc chốt A làm trợ giúp trong trường hợp này.

Bước 8) Vì chúng ta không thể di chuyển hai đĩa cùng lúc, chúng ta sẽ gọi lệnh đệ quy cho đĩa 1. Theo bước cuối cùng và thuật toán, đích đến ở bước này là chốt A.

Ở giai đoạn này:

Nguồn = chốt B
Đích = chốt A
Người trợ giúp = chốt C

Bước 9) Cuộc gọi đệ quy của chúng tôi đã hoàn tất. Sau đó, chúng tôi di chuyển đĩa 2 từ nguồn đến đích.

Ở giai đoạn này:

Nguồn = chốt B
Đích = chốt C
Người trợ giúp = chốt A

Bước 10) Sau đó, chúng tôi di chuyển n-1 hoặc đĩa 1 còn lại từ trợ giúp đến đích.

Ở giai đoạn này:

Nguồn = chốt A
Đích = chốt C
Người trợ giúp = chốt B

Mã giả Tháp Hà Nội

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
  		IF disk == 1, THEN
      			move disk from source to dest             
   		ELSE
     			Tower_Of_Hanoi (disk - 1, source, helper, dest)     
      			move disk from source to dest          
      			Tower_Of_Hanoi (disk - 1, helper, dest, source)     
   		END IF   
END Procedure

Mã chương trình trong C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
  if (num == 1) {
    cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
    return;
  }
  tower_of_hanoi(num - 1, source, helper, dest);
  cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
  tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
  int num;
  cin >> num;
  printf("The sequence of moves :\n");
  tower_of_hanoi(num, "I", "III", "II");
  return 0;
}

Đầu ra

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

Mã chương trình trong Python

def tower_of_hanoi(n, source, destination, helper):
	if n==1:
		print ("Move disk 1 from peg", source," to peg", destination)
		return
	tower_of_hanoi(n-1, source, helper, destination)
	print ("Move disk",n," from peg", source," to peg", destination)
	tower_of_hanoi(n-1, helper, destination, source)		
# n = number of disks
n = 3
tower_of_hanoi(n,' A','B','C')

Đầu ra:

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

Sự phức tạp của Tháp Hà Nội

Sau đây là Độ phức tạp về thời gian và không gian của Tháp Hà Nội:

1) Độ phức tạp về thời gian:

Nếu nhìn lại thuật toán của mình, chúng ta có thể thấy rằng chúng ta đang giới thiệu lệnh gọi đệ quy cho (n-1) đĩa hai lần. Các lệnh gọi đệ quy cho (n-1) đĩa có thể được chia thành ((n-1)-1) khác, v.v. cho đến khi chúng ta chỉ còn một đĩa để di chuyển.

Đối với ba đĩa-

• Đĩa 3 gọi hàm đệ quy cho đĩa hai hai lần.
• Đĩa 2 gọi hàm đệ quy cho đĩa một hai lần.
• Đĩa 1 có thể di chuyển trong phạm vi Thời gian không đổi và Thời gian giải quyết cho ba đĩa.

= 2*(Thời gian giải cho 3 đĩa) + hằng số Thời gian di chuyển đĩa XNUMX

= 2*(2*thời gian giải cho một đĩa + hằng số Thời gian di chuyển đĩa 2) + hằng số Thời gian di chuyển đĩa 3

= (2*2) (thời gian không đổi để di chuyển đĩa 1) + 2*thời gian không đổi để di chuyển đĩa 2 + thời gian không đổi để di chuyển đĩa 3

Đối với n đĩa, nó có thể được viết là –

(2^n-1 * thời gian không đổi để di chuyển đĩa 1 + 2^n-2 * thời gian không đổi để di chuyển đĩa 2 +….

Sự tiến triển hình học này sẽ dẫn đến O(2^n-1) hoặc O(2ⁿ), đó là số mũ.

2) Độ phức tạp của không gian

Độ phức tạp không gian của Tháp Hà Nội là 0(n). Đó là vì chúng ta cần lưu trữ trình tự các tấm. Khi chúng ta sử dụng đệ quy, tức là sử dụng ngăn xếp. Và kích thước tối đa của ngăn xếp có thể là “n”. Đó là lý do tại sao độ phức tạp không gian trở thành O(n).