Giáo án điện tử 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

NHIỆT LIỆT CHÀO MỪNG
CÁC EM ĐẾN VỚI TIẾT HỌC MỚI!

KHỞI ĐỘNG

Khi lập trình giải bài toán theo một thuật toán đã cho, em sẽ bắt đầu như thế nào? Theo em cách làm như thế có đúng phương pháp không?

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

NỘI DUNG BÀI HỌC

1. Mã giả và mô tả thuật toán bằng mã giả
2. Làm mịn dần các bước mô tả thuật toán
3. Thực hành

MÃ GIẢ VÀ MÔ TẢ THUẬT TOÁN BẰNG MÃ GIẢ

Thảo luận nhóm đôi

Đọc hiểu thông tin mục 1 tr.101 - 102 SGK, 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ì?

Khái niệm:

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

LÀM MỊN DẦN
CÁC BƯỚC MÔ TẢ THUẬT TOÁN

Thảo luận nhóm đô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?

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á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.

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.