Soạn giáo án Khoa học máy tính 11 cánh diều Chủ đề F(CS) Bài 4: Làm mịn dần từng bước từ thuật toán đến chương trình máy tính

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu đọc hiểu thông tin mục 1 trang 101 - 102 SGK, thảo luận cặp đôi trả lời các câu hỏi sau:

1. Thế nào là mã giả?

2. Quy ước cụ thể khi viết mã giả là gì?

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc và tìm hiểu thông tin mục 1 SGK trang 101 - 102, thực hiện các nhiệm vụ được giao.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện một số nhóm trình bày kết quả thảo luận.

- GV mời HS nhóm khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- 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 kết luận và yêu cầu HS ghi chép đầy đủ vào vở.

1. Mã giả và mô tả thuật toán bằng mã giả

- Mã giả là một cách mô tả thuật toán độc lập với ngôn ngữ lập trình và tạo thuận lợi cho việc chuyển thuật toán thành chương trình máy tính.

➢ Quy ước cụ thể khi viết mã giả

- Lời chú thích bắt đầu bằng dấu “#” cho đến hết dòng.

- Cấu trúc rẽ nhánh (phép lựa chọn) dùng mẫu câu lệnh if…else.

- Cấu trúc lặp (phép lặp):

+ Số lần lặp biết trước: Phỏng theo mẫu lệnh for của Python nhưng mô tả danh sách giá trị theo kiểu toán học.

Ví dụ: for biến in { i | i chẵn, j + 1  ≤ i ≤ n – 1}:...

+ Số lần lặp chưa biết trước: Phỏng theo lệnh while của Python.

Ví dụ: while điều kiện :...

- Sử dụng các mức thụt lùi đầu dòng để đánh dấu kết thúc dãy lệnh tuần tự trong mỗi nhánh rẽ của phép lựa chọn hay trong thân vòng lặp của phép lặp.

- Các phép toán gồm:

+ Phép toán số học, phép so sánh.

Ví dụ: +, –, *, /, >, <, = , ≥, ≤, ≠…

+ Phép gán dùng dấu mũi tên trái.

Ví dụ: x ← 5 nghĩa là gán x nhận giá trị bằng 5. Không viết “x = 5” vì nó có nghĩa là phép so sánh x có bằng 5 hay không, cho kết quả là “đúng” (True) hoặc “sai” (False).

- Một số thành phần khác:

+ Các lời gọi hàm thư viện hay hàm do người lập trình định nghĩa có thể mô tả ngắn gọn bằng cách viết toán học.

Ví dụ: min { a_i | j + 1  ≤ i ≤ n – 1}.

+ Có thể định nghĩa thêm các kí hiệu phép toán để chỉ một việc cụ thể nào đó.

Ví dụ: Khi mô tả các thuật toán sắp xếp, người ta thương viết phép đổi chỗ hai phần tử x, y trong dãy số một cách ngắn gọn là swap (x, y).

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Nhiệm vụ 1. Hoạt động

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS đọc hiểu thông tin mục 2 tr.102 SGK, thảo luận cặp đôi trả lời câu hỏi Hoạt động: Mô tả thuật toán bằng liệt kê các bước còn chứa nhiều cụm từ của ngôn ngữ tự nhiên, mỗi cụm từ nêu một việc phải làm. Để lập trình thực hiện thuật toán, cần làm chi tiết dần từng bước. Theo em, đây có phải làm “chia để trị” hay không? Vì sao?

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc hiểu thông tin mục 2 SGK trang 102 và thực hiện nhiệm vụ 1.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

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

Gợi ý trả lời:

+ “Chia để trị” là một chiến lược phổ quát để giải quyết vấn đề. Tự một cụm từ nêu một việc phải làm, phân tích chi tiết dần thành thao tác đơn giản, chuyển được thành một vài câu lệnh cũng là một cách vận dụng chiến lược “chia để trị”.

- Các HS còn lại nhận xét, bổ sung (nếu có).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

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

- GV tổng quát kiến thức và yêu cầu HS ghi chép đầy đủ vào vở.

2. Làm mịn dần các bước mô tả thuật toán

- Cách thức chung: Chuyển các cụm từ mô tả một “việc cần làm” thành các đoạn mã giả, tiến gần hơn một bước đến các câu lệnh của chương trình chi tiết.

Nhiệm vụ 2. Ví dụ 1: Thuật toán kiểm tra một số n là số nguyên tố

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV hướng dẫn Ví dụ 1 tr.102 - 104 SGK, yêu cầu HS quan sát hướng dẫn, đọc hiểu thông tin, Hình 1 - Hình 3, thực hành theo cặp đôi, ghép nối các đoạn mã lệnh và chạy thử kiểm tra

Ví dụ 1. Thuật toán kiểm tra một số n là số nguyên tố.

- Đầu vào: Một số nguyên dương n.

- Đầu ra: Nếu n là số nguyên tố trả về True, ngược lại trả về False.

Thuật toán khởi đầu đơn giản nhất là làm theo định nghĩa số nguyên tố.

Bước 1. Nếu n = 1 thì n không là số nguyên tố;

Bước 2. Nếu n = 2 thì n là số nguyên tố;

Bước 3. Nếu n > 2 thì kiểm tra tính nguyên tố của n; trả kết quả kiểm tra True/False.

Bước 4. Kết thúc.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc hiểu thông tin Ví dụ 1 SGK trang 102 và thực hiện nhiệm vụ 2.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

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

- Các HS còn lại nhận xét, bổ sung (nếu có).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

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

- GV tổng quát kiến thức và yêu cầu HS ghi chép đầy đủ vào vở.

Ví dụ 1. Thuật toán kiểm tra mộ số n là số nguyên tố.

Theo nhận xét 1 ta có thuật toán:

def is_prime(n):

    if (n == 1):

        return False

    if (n == 2):

        return True

    else:

      for k in range(2,n):

         if (n%k == 0):

             return False

      return True

Theo nhận xét 2 ta có thuật toán:

def is_prime(n):

    if (n == 1):

        return False

    if (n == 2):

        return True

    else:

 for k in range(2,int(math.sqr(n))+1):

         if (n%k == 0):

             return False

Theo nhận xét 3 ta có thuật toán:

def is_prime(n):

    if (n == 1):

        return False

    if n > 2 and n%2 == 0:

        return False

    else:

 for k in range(3,int(math.sqr(n))+1,2):

         if (n%k == 0):

             return False

Nhiệm vụ 3. Ví dụ 2: Bài toán sàng số nguyên tố

Bước 1: GV chuyển giao nhiệm vụ học tập

Ví dụ 2. Bài toán sàng số nguyên tố