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