Giải SGK Chuyên đề Tin học 11 Bài 4. Bài toán Tháp Hà Nội

Đọc, tìm hiểu bài toán Tháp Hà Nội và thực hiện giải trò chơi này với số lượng đĩa nhỏ (1, 2, 3). Em có nhận xét gì về lời giải bài toán với n = 1, 2, 3?

Với n = 2, ta có hai cái đĩa, ta sẽ di chuyển đĩa lớn nhất từ cọc 1 sang cọc trung gian 2, sau đó di chuyển đĩa nhỏ từ cọc 1 sang cọc đích 3, và cuối cùng di chuyển đĩa lớn từ cọc 2 sang cọc đích 3

* Với n = 1, bài toán trở nên rất đơn giản, chỉ cần chuyển đĩa từ cột xuất phát sang cột đích là xong

* Với n = 2, ta sẽ thực hiện theo các bước sau:

* Với n = 3, ta sẽ thực hiện theo các bước sau:

* Với n = 1, bài toán trở nên rất đơn giản, chỉ cần chuyển đĩa từ cột xuất phát sang cột đích là xong.

* Với n = 2, ta sẽ thực hiện theo các bước sau:

Chuyển đĩa nhỏ từ cột xuất phát sang cột trung gian.

Chuyển đĩa lớn từ cột xuất phát sang cột đích.

Chuyển đĩa nhỏ từ cột trung gian sang cột đích.

* Với n = 3, ta sẽ thực hiện theo các bước sau:

Chuyển hai đĩa nhỏ từ cột xuất phát sang cột trung gian.

Chuyển đĩa lớn từ cột xuất phát sang cột đích.

Chuyển hai đĩa nhỏ từ cột trung gian sang cột đích.

Chuyển đĩa nhỏ từ cột xuất phát sang cột trung gian.

Chuyển đĩa lớn từ cột đích sang cột xuất phát.

Chuyển đĩa nhỏ từ cột trung gian sang cột đích.

Chuyển hai đĩa nhỏ từ cột xuất phát sang cột trung gian.

Chuyển đĩa lớn từ cột xuất phát sang cột đích.

Chuyển hai đĩa nhỏ từ cột trung gian sang cột đích.

* Giải trò chơi Tháp Hà Nội với n=1:

Di chuyển đĩa 1 từ cọc 1 sang cọc 2.

* Giải trò chơi Tháp Hà Nội với n=2:

Di chuyển đĩa 1 từ cọc 1 sang cọc 3.

Di chuyển đĩa 2 từ cọc 1 sang cọc 2.

Di chuyển đĩa 1 từ cọc 3 sang cọc 2.

* Giải trò chơi Tháp Hà Nội với n=3:

Di chuyển đĩa 1 từ cọc 1 sang cọc 2.

Di chuyển đĩa 2 từ cọc 1 sang cọc 3.

Di chuyển đĩa 1 từ cọc 2 sang cọc 3.

Di chuyển đĩa 3 từ cọc 1 sang cọc 2.

Di chuyển đĩa 1 từ cọc 3 sang cọc 1.

Di chuyển đĩa 2 từ cọc 3 sang cọc 2.

Di chuyển đĩa 1 từ cọc 1 sang cọc 2.

Nhận xét: Với n = 1, chỉ cần di chuyển một đĩa từ cọc 1 sang cọc 2. Với n = 2, ta thực hiện ba lần di chuyển. Với n = 3, ta thực hiện bảy lần di chuyển. Với mỗi tăng thêm một đĩa, số lần di chuyển tăng lên gấp đôi và cộng thêm một.

Ý tưởng giải bài toán Tháp Hà Nội có n đĩa từ cọc 1 sang cọc 3 như sau:

Bước 1. Chuyển n - 1 đĩa từ cọc 1 sang cọc 2 lấy cọc 5 làm trung gian.

Bước 2. Chuyển đĩa n từ cọc 1 sang cọc 3.

Bước 3. Chuyển n - 1 đĩa từ cọc 2 sang cọc 3 lấy cọc 1 làm trung gian.

1. Di chuyển 3 đĩa từ cọc 1 sang cọc 3:

1.1 Di chuyển 2 đĩa từ cọc 1 sang cọc 2:

- Di chuyển 1 đĩa từ cọc 1 sang cọc 3.

- Di chuyển 1 đĩa từ cọc 1 sang cọc 2.

- Di chuyển 1 đĩa từ cọc 3 sang cọc 2.

1.2. Di chuyển 1 đĩa từ cọc 1 sang cọc 3.

1.3. Di chuyển 2 đĩa từ cọc 2 sang cọc 3:

- Di chuyển 1 đĩa từ cọc 2 sang cọc 1.

- Di chuyển 1 đĩa từ cọc 2 sang cọc 3

- Di chuyển 1 đĩa từ cọc 1 sang cọc 3.

2. Di chuyển 1 đĩa từ cọc 1 sang cọc 2.

3. Di chuyển 3 đĩa từ cọc 3 sang cọc 2:

3.1 Di chuyển 2 đĩa từ cọc 3 sang cọc 1:

- Di chuyển 1 đĩa từ cọc 3 sang cọc 2. 3.1.2

- Di chuyển 1 đĩa từ cọc 3 sang cọc 1.

- Di chuyển 1 đĩa từ cọc 2 sang cọc 1.

3.2 Di chuyển 1 đĩa từ cọc 3 sang cọc 2.

3.3 Di chuyển 2 đĩa từ cọc 1 sang cọc 2:

- Di chuyển 1 đĩa từ cọc 1 sang cọc 3.

- Di chuyển 1 đĩa từ cọc 1 sang cọc 2.

- Di chuyển 1 đĩa từ cọc 3 sang cọc 2.

Vậy, tổng số bước để di chuyển 4 đĩa theo quy trình trên là:

- Di chuyển 3 đĩa từ cọc 1 sang cọc 2: 7 bước

- Di chuyển đĩa còn lại từ cọc 1 sang cọc 3: 1 bước

- Di chuyển 3 đĩa từ cọc 2 sang cọc 3: 7 bước

Vậy tổng số bước cần thiết để di chuyển 4 đĩa trong bài toán tháp Hà Nội là 15 bước.Top of Form

Mô tả chi tiết từng bước chuyển như sau:

1. Khi n = 1:

Di chuyển đĩa từ cọc i sang cọc j.

2. Khi n > 1:

- Bước 1: Chuyển n - 1 đĩa từ cọc i sang cọc k:

Gọi lại thuật toán Hanoi(n-1, i, k, j) để chuyển n - 1 đĩa từ cọc i sang cọc k.

- Bước 2: Chuyển đĩa lớn nhất từ cọc i sang cọc j:

Di chuyển đĩa từ cọc i sang cọc j.

- Bước 3: Chuyển n - 1 đĩa từ cọc k sang cọc j:

Gọi lại thuật toán Hanoi(n-1, k, j, i) để chuyển n - 1 đĩa từ cọc k sang cọc j.

Để tính các giá trị H(2), H(3), H(4), H(5) của bài toán Tháp Hà Nội, ta có thể sử dụng công thức như sau:

H(2) = 2

H(3) = 2 * H(2) + 1 = 2 * 2 + 1 = 5

H(4) = 2 * H(3) + 1 = 2 * 5 + 1 = 11

H(5) = 2 * H(4) + 1 = 2 * 11 + 1 = 23

Vậy H(2) = 2, H(3) = 5, H(4) = 11, H(5) = 23.

Viết chương trình đệ quy để tính giá trị H(n) của bài toán Tháp Hà Nội

Chương trình giải bài toán Tháp Hà Nội nhưng với tên các cọc là A, B, C

Chương trình viết đúng. Thử với n = 4, kết quả thu được như sau:

- Nếu chỉ có một đĩa (n=1), H(n) = 1.

- Nếu có n đĩa, để chuyển tất cả các đĩa từ tháp ban đầu sang tháp đích, ta phải thực hiện các bước sau:

Chuyển n-1 đĩa từ tháp ban đầu sang tháp trung gian.

Chuyển đĩa cuối cùng (đĩa lớn nhất) từ tháp ban đầu sang tháp đích.

Chuyển n-1 đĩa từ tháp trung gian sang tháp đích.

Số bước chuyển tất cả các đĩa là H(n) = 2 * H(n-1) + 1.

- Ta sẽ chứng minh công thức này bằng phương pháp quy nạp toán học:

Bước 1: Giả sử công thức đúng với n-1, tức là H(n-1) = 2^(n-1) - 1

Bước 2: Chứng minh công thức đúng với n, tức là H(n) = 2^n - 1

Ta có:

H(n) = 2 * H(n-1) + 1 (theo công thức đề bài)

= 2 * (2^(n-1) - 1) + 1 (theo giả sử ở bước 1)

= 2^n - 2 + 1

= 2^n - 1

Vậy ta đã chứng minh được công thức đúng với mọi n.

Để tính H(64), ta áp dụng công thức đã chứng minh:

H(64) = 2^64 - 1

= 18446744073709551615

Vậy H(64) = 18446744073709551615 trùng với con số ở trên bài báo

Để giải bài toán Tháp Hà Nội và lưu các bước chuyển vào một danh sách, ta có thể sử dụng thuật toán đệ quy. Trong mỗi lần đệ quy, ta sẽ chuyển n-1 đĩa từ cọc ban đầu sang cọc trung gian, sau đó chuyển đĩa lớn nhất từ cọc ban đầu sang cọc đích và cuối cùng chuyển n-1 đĩa từ cọc trung gian sang cọc đích.

Ví dụ, để chuyển 3 đĩa từ cọc A sang cọc C lấy cọc B làm trung gian, ta có thể gọi hàm Hanoi(3, 'A', 'C', 'B') và kết quả trả về sẽ là danh sách các bước chuyển [(1, 'A', 'C'), (2, 'A', 'B'), (1, 'C', 'B'), (3, 'A', 'C'), (1, 'B', 'A'), (2, 'B', 'C'), (1, 'A', 'C')].