Giáo án chuyên đề Tin học 11 Khoa học máy tính cánh diều chuyên đề 1 Bài 4: Thực hành tổng hợp thiết kế thuật toán đệ quy (P2)

1. HOẠT ĐỘNG LUYỆN TẬP
2. Mục tiêu: HS củng cố lại kiến thức về thiết kế thuật toán đệ quy giải bài toán Tháp Hà Nội.
3. Nội dung: HS hoạt động cá nhân trả lời câu hỏi liên quan đến thiết kế thuật toán đệ quy giải bài toán Tháp Hà Nội.
4. Sản phẩm: Hướng dẫn trả lời câu hỏi liên quan đến thiết kế thuật toán đệ quy giải bài toán Tháp Hà Nội.
5. Tổ chức thực hiện

Bước 1: Chuyển giao nhiệm vụ

- GV cho HS trả lời nhanh các câu hỏi trắc nghiệm về các nội dung liên quan đến thuật toán đệ quy.

Câu 1: Giai đoạn 2 trong bài toán Tháp Hà Nội với số lượng đĩa n gồm một bước: Chuyển đĩa có đường kính lớn nhất (đĩa n) từ cọc A sang cọc C được thực hiện thông qua câu lệnh:

1. print("Chuyển đĩa", n, "từ cọc A sang cọc C")
2. n = int(input("Nhập kích thước n = "))
3. HanoiTower(n-1, B, C, A)
4. HanoiTower(n–1, ten_coc_xuat_phat, ten_coc_ trung_gian, ten_coc_dich)

Câu 2: Với n = 1 có bao nhiêu giai đoạn chuyển đĩa từ cọc A sang cọc C?

1. 1 B. 2 C. 3                   D. 4

Câu 3: Khi giải bài toán Tháp Hà Nội với n = 4, ta cần giải bao nhiêu lần bài toán với n = 3?

1. 1 B. 2 C. 3                   D. 4

Câu 4: Chọn đáp án đúng khi nói về quy tắc chuyển chồng đĩa từ cọc A sang cọc C:

1. Mỗi lần được chuyển một đĩa ở vị trí bất kì của một cọc.
2. Mỗi lần được chuyển hai đĩa ở trên cùng của một cọc.
3. Mỗi lần chỉ chuyển một đĩa ở trên cùng của một cọc.
4. Mỗi lần được chuyển lớn nhất trên một cọc.

Câu 5: Cho chương trình:

def HanoiTower(n, ten_coc_xuat_phat, ten_coc_dich, ten_coc_trung_gian):

   if (n ==0):    #Trường hợp cơ sở

      return      #Không làm gì

   else:           #Gọi đệ quy

   HanoiTower(n–1, ten_coc_xuat_phat, ten_coc_ trung_gian, ten_coc_dich)

   print("Chuyển đĩa "+str(n)+" từ cọc "+ ten_coc_xuat phat+ " sang cọc "+ ten_coc_dich)

   HanoiTower(n, ten_coc_trung_gian, ten_coc_dich, ten_coc_xuat_phat)

n = int(input("Nhập số lượng đĩa n = "))

HanoiTower(n, "A", "C", "B")

Câu lệnh nào bị viết sai?

1. print("Chuyển đĩa "+str(n)+" từ cọc "+ ten_coc_xuat phat+ " sang cọc "+ ten_coc_dich)
2. n = int(input("Nhập số lượng đĩa n = "))
3. HanoiTower(n, "A", "C", "B")
4. HanoiTower(n, ten_coc_trung_gian, ten_coc_dich, ten_coc_xuat_phat)

Bước 2: Thực hiện nhiệm vụ:

• HS đọc câu hỏi và trả lời.

Bước 3: Báo cáo, thảo luận:

• Đại diện HS giơ tay phát biểu.
• Các HS khác nhận xét, góp ý, bổ sung.

Bước 4: Kết luận, nhận định:

-  GV chữa bài, chốt đáp án.

- GV nhận xét thái độ học tập, phương án trả lời của HS, ghi nhận và tuyên dương.

Đáp án

1. HOẠT ĐỘNG VẬN DỤNG
2. a) Mục tiêu: Vận dụng kiến thức giải một số bài tập liên quan đến thiết kế thuật toán đệ quy giải bài toán Tháp Hà Nội ở các phiên bản số lượng đĩa khác nhau.
3. b) Nội dung: HS làm việc cá nhân thực hiện giải một số bài tập liên quan đến thiết kế thuật toán đệ quy giải bài toán Tháp Hà Nội ở các phiên bản số lượng đĩa khác nhau.
4. c) Sản phẩm: Gợi ý trả lời bài tập liên quan đến thiết kế thuật toán đệ quy giải bài toán Tháp Hà Nội ở các phiên bản số lượng đĩa khác nhau.
5. d) Tổ chức thực hiện:

Bước 1: Chuyển giao nhiệm vụ:

- GV yêu cầu HS làm việc cá nhân giải bài tập Vận dụng trang 22 sách CĐHT.

Bước 2: Thực hiện nhiệm vụ:

- HS suy nghĩ và giải bài tập liên quan đến thiết kế thuật toán đệ quy giải bài toán Tháp Hà Nội ở các phiên bản số lượng đĩa khác nhau.

Bước 3: Báo cáo, thảo luận:

- HS xung phong trình bày bài làm của mình.

- HS khác nhận xét và bổ sung.

Bước 4: Kết luận, nhận định:

- GV chữa bài, chốt đáp án.

- GV nhận xét thái độ làm việc, sản phẩm, phương án trả lời của các học sinh, ghi nhận và tuyên dương.

Gợi ý trả lời:

1. a) Đánh thứ tự các đĩa trên cọc A như ở hình bên dưới, các bước di chuyển đĩa trong bài toán với kích thước n = 2 được chia làm 3 giai đoạn:

• Giai đoạn 1 gồm bước 1 + bước 2: Chuyển lần lượt 2 đĩa trên cùng (gồm 2 đĩa size 1) từ cọc A sang cọc B. Giai đoạn này tương ứng với giải bài toán kích thước n = 1, cọc xuất phát là A, cọc đích là B.
• Giai đoạn 2 gồm bước 3 + bước 4: Chuyển toàn bộ lần lượt 2 đĩa đang ở cọc A (gồm 2 đĩa size 2) sang cọc C. Giai đoạn này tương ứng với giải bài toán kích thước n = 1, cọc xuất phát là A, cọc đích là C.
• Giai đoạn 3 gồm bước 5 + bước 6: Chuyển toàn bộ lần lượt 2 đĩa đang ở cọc B (gồm 2 đĩa size 1)sang cọc C. Giai đoạn này tương ứng với giải bài toán kích thước n = 1, cọc xuất phát là B, cọc đích là C.

1. b) Tương tự như trường hợp n = , các đĩa trong trường hợp n = 3 bao gồm {2 đĩa size 1, 2 đĩa size 2, 2 đĩa size 3}.

• Giai đoạn 1: Chuyển 4 đĩa trên cùng (gồm 2 đĩa size 1 và 2 đĩa size 2) từ cọc A → cọc B, trong quá trình vận chuyển có thể dùng cọc C làm trung gian. Thực hiện tương tự giải bài toán kích thước n = 1 như sau:

+ Lần 1 gồm bước 1 + bước 2: Chuyển lần lượt 2 đĩa trên (2 đĩa size 1) từ cọc A → cọc C.

+ Lần 2 gồm bước 3 + bước 4: Chuyển lần lượt 2 đĩa size 2 đang ở cọc A → cọc B.

+ Lần 3 gồm bước 5 + bước 6: Chuyển lần lượt 2 đĩa size 1 đang ở cọc C → cọc B.

• Giai đoạn 2: Chuyển lần lượt 2 đĩa size 3 đang ở cọc A sang cọc C. Giai đoạn này tương ứng với giải bài toán kích thước n = 1, cọc xuất phát là A, cọc đích là C, không cần sử dụng cọc trung gian.
• Giai đoạn 3: Chuyển toàn bộ 4 đĩa đang ở cọc B (gồm 2 đĩa size 1 và 2 đĩa size 2) sang cọc C, sử dụng cọc A làm trung gian. Giai đoạn này tương ứng với giải bài toán kích thước n = 2, cọc xuất phát là B, cọc đích là C. Trong giai đoạn này, cọc trung gian A bắt buộc phải sử dụng để có thể tuân theo được quy luật di chuyển theo yêu cầu của đề bài. Thực hiện tương tự giải bài toán kích thước n = 1 như sau:

+ Lần 1 gồm bước 1 + bước 2: : Chuyển lần lượt 2 đĩa size 1 trên cùng từ cọc B → cọc C.

+ Lần 2 gồm bước 3 + bước 4: Chuyển lần lượt 2 đĩa size 2 đang ở cọc B → cọc C.

+ Lần 3 gồm bước 5 + bước 6: Chuyển lần lượt 2 đĩa size 1 đang ở cọc A → cọc C.

1. c) Chương trình hoàn thiện như sau:

def HanoiTowerDouble(n, ten_coc_xuat_phat, ten_coc_dich, ten_coc_trung_gian):

    if (n ==0):    #Trường hợp cơ sở

         return     #Không làm gì

    else:           #Gọi đệ quy

         HanoiTowerDouble(n–1, ten_coc_xuat_phat, ten_coc_ trung_gian, ten_coc_dich)

         print("Chuyển đĩa size "+str(n)+" từ cọc "+ ten_coc_xuat phat+ " sang cọc "+ten_coc_dich)

         print("Chuyển đĩa size "+str(n)+" từ cọc "+ ten_coc_xuat phat+ " sang cọc "+ten_coc_dich)

   HanoiTowerDouble(n–1, ten_coc_trung_gian, ten_coc_dich, ten_coc_xuat_phat)

      n = int(input("Nhập kích thước n = "))

      HanoiTowerDouble(n, "A", "C", "B")

* HƯỚNG DẪN VỀ NHÀ

- Ghi nhớ kiến thức trong bài.

- Chuẩn bị Chuyên đề 2. Thực hành thiết kế thuật toán theo kĩ thuật chia để trị - Bài 1. Ý tưởng chia để trị.