Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 4 Thực hành tổng hợp thiết kế thuật toán đệ quy (P2)

Mẫu giáo án chuyên đề khoa học máy tính 11 cánh diều. Chi tiết chuyên đề bài 4 Thực hành tổng hợp thiết kế thuật toán đệ quy (P2). Giáo án được biên soạn chi tiết. Có thể tải về tham khảo. Cách tải nhanh chóng, dễ dàng. Ngoài ra, hệ thống có đủ giáo án các bài khác của chuyên đề khoa học máy tính 11 cánh diều

Nội dung giáo án

HOẠT ĐỘNG LUYỆN TẬP
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.
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.
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.
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:

print("Chuyển đĩa", n, "từ cọc A sang cọc C")
n = int(input("Nhập kích thước n = "))
HanoiTower(n-1, B, C, A)
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 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 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:

Mỗi lần được chuyển một đĩa ở vị trí bất kì của một cọc.
Mỗi lần được chuyển hai đĩa ở trên cùng của một cọc.
Mỗi lần chỉ chuyển một đĩa ở trên cùng của một cọc.
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?

print("Chuyển đĩa "+str(n)+" từ cọc "+ ten_coc_xuat phat+ " sang cọc "+ ten_coc_dich)
n = int(input("Nhập số lượng đĩa n = "))
HanoiTower(n, "A", "C", "B")
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. A

2. A

3. B

4. C

5. D

HOẠT ĐỘNG VẬN DỤNG
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.
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.
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.
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:

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.

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.