Viết sơ đồ chi tiết giải bài toán Tháp Hà Nội cho trường hợp n = 4. Tính H(4)

Giải Chuyên đề Tin học 11 Kết nối tri thức Bài 4: Tháp Hà Nội

Câu hỏi trang 22 Chuyên đề Tin học 11: Viết sơ đồ chi tiết giải bài toán Tháp Hà Nội cho trường hợp n = 4. Tính H(4)

Lời giải:

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