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 (P1)

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 (P1). 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

Ngày soạn: .../.../...

Ngày dạy: .../.../...

BÀI 4. THỰC HÀNH TỔNG HỢP THIẾT KẾ THUẬT TOÁN ĐỆ QUY

(2 tiết)

MỤC TIÊU
Kiến thức

Sau bài học này, HS sẽ:

Hiểu được các bước giải bài toán Tháp Hà Nội sử dụng thuật toán đệ quy.
Viết và thực hiện được chương trình cài đặt thuật toán đệ quy giải bài toán Tháp Hà Nội.

Năng lực

Năng lực chung:

Năng lực giao tiếp và hợp tác: biết chủ động trong giao tiếp, tự tin phát biểu ý kiến của bản thân về chương trình cài đặt thuật toán đệ quy giải bài toán Tháp Hà Nội.
Năng lực tự chủ và tự học: Xác định được nhiệm vụ học tập Chuyên đề môn Tin học 11 – Khoa học máy tính qua việc tìm hiểu về chương trình cài đặt thuật toán đệ quy giải bài toán Tháp Hà Nội.
Năng lực giải quyết vấn đề và sáng tạo: Vận dụng các kiến thức giải quyết được các lỗi lặp lại vô hạn khi cài đặt thuật toán đệ quy giải bài toán Tháp Hà Nội.

Năng lực riêng:

Năng lực giải quyết vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông: Hiểu được các bước giải bài toán Tháp Hà Nội sử dụng thuật toán đệ quy; Viết và thực hiện được chương trình cài đặt thuật toán đệ quy giải bài toán Tháp Hà Nội.

Phẩm chất

Chăm chỉ: có ý thức đánh giá điểm mạnh, điểm yếu của bản thân, thuận lợi, khó khăn trong học tập để xây dựng kế hoạch học tập; tích cực tìm tòi và sáng tạo trong học tập, có ý chí vượt qua khó khăn để đạt kết quả tốt trong học tập.
Trách nhiệm: tích cực, tự giác và nghiêm túc rèn luyện, tu dưỡng đạo đức; sẵn sàng chịu trách nhiệm về lời nói và hành động của bản thân.

THIẾT BỊ DẠY HỌC
Đối với giáo viên

Giáo án, sách CĐHT, SGV Tin học 11 – Khoa học máy tính bộ Cánh diều.
Máy tính cá nhân có cài đặt phần mềm mô phỏng thuật toán, máy chiếu, màn hình chiếu.

Đối với học sinh

SHS, sách CĐHT Tin học 11 – Khoa học máy tính bộ Cánh diều.
Tư liệu có liên quan đến nội dung bài học và dụng cụ học tập.

TIẾN TRÌNH DẠY HỌC
HOẠT ĐỘNG KHỞI ĐỘNG (MỞ ĐẦU)
Mục tiêu: Đưa ra vấn đề để học sinh suy nghĩ khơi gợi hứng thú học tập.
Nội dung: HS trả lời câu hỏi mở đầu có nội dung liên quan đến bài học.
Sản phẩm: Gợi ý câu trả lời của HS.
Tổ chức thực hiện:

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

GV giới thiệu: Bài toán Tháp Hà Nội là một bài toán kinh điển có thể giải bằng đệ quy. Giả sử câu đố có ba cọc và có 2 đĩa có kích thước như hình bên.

A C B

GV đặt vấn đề: Hãy tìm cách chuyển các đĩa từ cọc A sang cọc C theo thứ tự tăng dần kích thước đĩa.
Chú ý: Cần phải chuyển chồng đĩa từ cọc A sang cọc C theo quy tắc:

(1) Mỗi lần chỉ chuyển một đĩa ở trên cùng của một cọc.

(2) Chỉ được xếp đĩa có đường kính nhỏ hơn lên trên đĩa có đường kính lớn hơn. Trong quá trình di chuyển cọc B làm cọc trung gian.

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

HS nhớ lại kiến thức bài học trước để có câu trả lời cho các câu hỏi.

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

Các học sinh xung phong phát biểu trả lời.

Bước 4: Kết luận và nhận xét:

- Gợi ý đáp án:

GV nhận xét, đánh giá và dẫn vào bài: Làm thế nào để xây dựng thuật toán đệ quy trên bài toán Tháp Hà Nội? Chúng ta cùng nhau đi tìm hiểu bài học ngày hôm nay: Bài 4. Thực hành tổng hợp thiết kế thuật toán đệ quy.”

HÌNH THÀNH KIẾN THỨC MỚI

Hoạt động: Bài toán Tháp Hà Nội

Mục tiêu: Hiểu được các bước thực hiện bài toán Tháp Hà Nội sử dụng thuật toán đệ quy; Viết và thực hiện được chương trình cài đặt thuật toán đệ quy giải bài toán Tháp Hà Nội.
Nội dung:

- Nhiệm vụ 1: HS hoạt động độc lập quan sát hình 3 trang 21 và trả lời câu a trang 22 sách CĐHT.

- Nhiệm vụ 2: HS hoạt động nhóm (3 – 4 HS) nghiên cứu sách CĐHT, trả lời câu b trang 22 sách CĐHT.

- Nhiệm vụ 3: HS hoạt động độc lập viết hàm đệ quy dựa trên sơ đồ chung đã học ở Bài 2 để trả lời câu c trang 22 sách CĐHT.

- Nhiệm vụ 4: HS hoạt độc lập hoàn thiện chương trình giải bài toán Tháp Hà Nội, trả lời câu d trang 22 sách CĐHT.

Sản phẩm: Hướng dẫn trả lời Bài toán Tháp Hà Nội.
Tổ chức thực hiện

HĐ CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Nhiệm vụ 1 – câu a:

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

- GV yêu cầu HS quan sát Hình 3, trang 21 trả lời các câu hỏi sau:

+ Xác định đầu vào và đầu ra tương ứng của ba bước 1, 2, 3.

+ Xác định đầu vào và đầu ra tương ứng của ba bước 5, 6, 7.

+ Mô tả quá trình giải bài toán Tháp Hà Nội với trường hợp n = 3.

+ Khi giải bài toán Tháp Hà Nội cho trường hợp n = 3, cần phải giải bao nhiêu lần bài toán này với n = 2?

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

- HS đọc sách CĐHT, quan sát Hình 3 và trả lời câu hỏi.

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

- HS giơ tay trả lời câu hỏi.

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

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

- GV nhận xét kết quả trả lời câu hỏi của HS.

- GV tổng quát lại kiến thức.

Câu a.

- Ba bước 1, 2, 3 có đầu vào là hình bên trái của bước 1, đầu ra là hình bên phải của bước 3.

→ Cọc A là cọc xuất phát, cọc B là cọc đích.

- Ba bước 5, 6, 7 có đầu vào là hình bên trái của bước 5, đầu ra là hình bên phải của bước 7.

→ Cọc B là cọc xuất phát, cọc C là cọc đích.

- Quá trình giải Bài toán Tháp Hà Nội cho trường hợp n = 3 được chia làm 3 giai đoạn:

+ Giai đoạn 1 gồm ba bước 1, 2, 3: Chuyển 2 đĩa trên cùng từ cọc A sang cọc B, cọc C làm trung gian để thỏa mãn quy tắc di chuyển đã nêu trong bài toán.

+ Giai đoạn 2 gồm bước 4: Chuyển đĩa có đường kính lớn nhất từ cọc A sang cọc C.

+ Giai đoạn 3 gồm ba bước 5, 6, 7: Chuyển 2 đĩa từ cọc B sang cọc C, cọc A làm trung gian để thỏa mãn quy tắc di chuyển đã nêu trong bài toán.

- Khi giải bài toán Tháp Hà Nội cho trường hợp n = 3, cần phải giải hai lần bài toán này với n = 2

Nhiệm vụ 2 – câu b:

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

- GV chia lớp thành các nhóm, mỗi nhóm 3 – 4 HS cùng thảo luận trả lời câu hỏi b trang 22 sách CĐHT.

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

- Các nhóm nghiên cứu sách CĐHT, dựa vào kiến thức vừa nêu ở câu a để trả lời câu hỏi.

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

- Đại diện nhóm báo cáo kết quả thảo luận.

- Các nhóm khác nhận xét, bổ sung cho nhóm bạn.

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

- GV nhận xét kết quả thảo luận của HS, thái độ làm việc của HS trong nhóm.

- GV tổng quát lại kiến thức giải bài toán Tháp Hà Nội trong trường hợp n đĩa (Đính kèm dưới phần Hoạt động)

Câu b.

- Mô tả quá trình thực hiện bài toán Tháp Hà Nội với n = 4 được chia làm 3 giai đoạn:

+ Giai đoạn 1:

o Trạng thái ban đầu: 4 đĩa đang ở cọc A;

o Trạng thái thứ hai: chuyển 3 đĩa trên cùng của cọc A sang cọc B.

→ Như vậy, ta phải giải bài toán Tháp Hà Nội với n = 3 để chuyển từ trạng thái ban đầu sang trạng thái thứ hai.

+ Giai đoạn 2: Chuyển đĩa có đường kính lớn nhất từ cọc A sang cọc C. Giai đoạn này chỉ cần 1 bước.

+ Giai đoạn 3: Tất cả các bước mà HS vừa liệt kê (loại trừ bước đầu đã tương ứng với giai đoạn 2) thực hiện công việc chuyển ba đĩa ở cọc B sang cọc C

→ Giai đoạn này phải giải bài toán với n = 3.

Nhiệm vụ 3 – câu c:

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

- GV yêu cầu HS dựa vào những phân tích đã nêu ở câu a) và b) kết hợp với sơ đồ chung đã học ở Bài 2 viết hàm đệ quy: HanoiTower(n, ten_coc_xuat_phat, ten_coc_dich, ten_coc_trung_gian)

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

- HS dựa vào kiến thức đã học, trả lời câu c trang 22 sách CĐHT.

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

- HS giơ tay phát biểu.

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

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

- GV nhận xét kết quả trả lời câu hỏi của HS.

- GV tổng quát lại kiến thức.

Câu c.

- Hàm HanoiTower(n, A, C, B)

- Giai đoạn 1 được thực hiện bằng câu lệnh:

HanoiTower(n-1, A, B, C)

- Giai đoạn 2 được thực hiện bằng câu lệnh:

print("Chuyển đĩa", n, "từ cọc A sang cọc C")

- Giai đoạn 3 được thực hiện bằng câu lệnh:

HanoiTower(n-1, B, C, A)

- Trường hợp cơ sở của bài toán được xác định khi không còn đĩa nào, tương ứng với n = 0.

Nhiệm vụ 4 – câu d:

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

- GV yêu cầu HS trả lời câu d trang 22 sách CĐHT, hoàn thiện chương trình giải bài toán Tháp Hà Nội.

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

- HS dựa vào kiến thức đã học, viết chương trình giải bài toán Tháp Hà Nội với số lượng đĩa n.

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

- HS giơ tay trả lời câu hỏi.

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

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

- GV nhận xét kết quả trả lời câu hỏi của HS.

- GV tổng quát lại kiến thức.

Câu d.

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–1, 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")

Kết luận: Các bước thực hiện khi giải bài toán Tháp Hà Nội trong trường hợp n đĩa được chia làm 3 giai đoạn:

- Giai đoạn 1 có thể gồm nhiều bước: Thực hiện giải bài toán Tháp Hà Nội cho trường hợp n – 1 để chuyển n – 1 đĩa trên cùng (gồm các đĩa 1, 2… n – 1) từ cọc A sang cọc B. Trong quá trình di chuyển sẽ dùng cọc C làm trung gian để thỏa mãn các quy tắc di chuyển đã nêu.

- Giai đoạn 2 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.

- Giai đoạn 3 có thể gồm nhiều bước: Thực hiện giải bài toán Tháp Hà Nội cho trường hợp n – 1 để chuyển toàn bộ n – 1 đĩa đang ở cọc B (gồm các đĩa 1, 2… n – 1) sang cọc C. Trong quá trình di chuyển sẽ dùng cọc A làm trung gian để thỏa mãn các quy tắc di chuyển đã nêu.

---------------------Còn tiếp---------------------

Đăng nhập để xem đáp án