Tower of Hanoi được phát minh bởi nhà toán học người Pháp Édouard Lucas năm 1883 và ông này không có gốc Việt.

Bài toán phát biểu như sau:

• Cho 3 cái cột, cần chuyển các đĩa từ cột 1 sang cột 3, thông qua cột 2
• Mỗi lần chỉ được chuyển 1 đĩa, đĩa bên dưới phải to hơn đĩa bên trên.

Bài giải

Hình ảnh minh họa sinh động bài giải:

Phân tích cách viết function đệ quy:

Đặt 3 cột là source (nguồn), dest (đích), tmp (trung gian), function tên move, ban đầu có thể nghĩ function trông như sau:

Khi viết recursive function, thường sử dụng các argument để lưu trạng thái (state) function. Bài toán này có 1 trạng thái là số lượng đĩa còn lại cần chuyển, ban đầu có giá trị là n, khi kết thúc là 0. Sau mỗi bước chuyển, trạng thái của bài toán được lưu giữ trong số đĩa còn lại và nội dung của mỗi cột. Vậy function sẽ trở thành

move(n, source, dest, tmp)

Có thể cho rằng chỉ cần 3 cột cũng đủ biểu diễn trạng thái của chương trình, không cần tới n, và dùng len(source) để tính số đĩa còn lại, nhưng khi giải, các cột lần lượt thay đổi vai trò của nhau khiến không thể biết cột nào là cột source ban đầu.

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 đố-

Bài toán Tháp Hà Nội

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 ban đầu là về việc di chuyển 64 chiếc đĩa. Các linh mục có thể di chuyển từng đĩa một theo quy định. 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 thời gian complexTrong phần này, chúng tôi sẽ chỉ ra rằng một bộ n đĩa của Tháp Hà Nội 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 hours, 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 một lúcneoThông thường, chúng ta sẽ gọi lệnh gọi đệ 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

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 bằng 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

Vớiplextính chất của Tháp Hà Nội

Đây là Com thời gian và không gianplexTính chất của Tháp Hà Nội:

1. Thời gian complextính chất:

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à –

(2n-1 * thời gian không đổi để di chuyển đĩa 1 + 2n-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(2n-1) hoặc O(2n), đó là số mũ.

2. Không gian complexity

không gian complexity của Tháp Hà Nội là 0(n). Đó là bởi vì chúng ta cần lưu trữ thứ tự của các tấm. Khi chúng ta sử dụng đệ quy, đó 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 không gian complexity trở thành O(n).

Bài toán tháp Hà Nội do ai tạo ra?

“Tòa tháp Hà Nội” là bài toán do một người Pháp, Francois Lucas phát minh vào năm 1883. Nó bao gồm một chồng đĩa xếp lớn dưới, nhỏ trên và 3 cây cột.nullKiến giải được bài toán "Tòa tháp Hà nội" - Báo Tuổi Trẻtuoitre.vn › kien-giai-duoc-bai-toan-toa-thap-ha-noi-415494null

Bài toán tháp Hà Nội bắt nguồn từ đâu?

Bài toán tháp Hà Nội có nguồn gốc từ một truyền thuyết Ấn Độ và đã được biết đến rộng rãi do nhà toán học người Pháp, Édouard Lucas, giới thiệu vào năm 1883 trong quyển sách "Récréations Mathématiques". Truyền thuyết kể về một ngôi đền cổ ở Ấn Độ, nơi có ba cây cột đá và 64 chiếc đĩa vàng khác kích cỡ.28 thg 9, 2023nullBài toán tháp Hà Nội và cách giải sử dụng Đệ Quy - 200Lab200lab.io › blog › bai-toan-thap-ha-noinull