Thông qua nội dung 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, các em sẽ giải thích được sơ bộ phương pháp làm mịn dần trong lập trình và biết được mã giả là gì và sử dụng được mã giả làm mịn dần một số thuật toán đơn giản. HOC247 hy vọng rằng các em sẽ thu thập được những kiến thức hữu ích và thú vị giúp các em nâng cao kiến thức về môn Tin học 11 qua các bài học của chương trình Khoa học máy tính.
Tóm tắt lý thuyết
1.1. Mã giả và mô tả thuật toán bằng mã giả
- Mã giả mô tả thuật toán ngắn gọn, độc lập với ngôn ngữ lập trình.
- Mã giả đảm bảo sự chính xác và rất gần với mã lệnh chương trình.
- Mã giả thường được sử dụng trong sách giáo khoa, giáo trình hay các bài nghiên cứu để mô tả thuật toán.
- Mã giả có thể coi như chương trình khung.
- Không có quy ước thống nhất về các từ khoá, kí hiệu trong mã giả.
- Mã giả phỏng theo câu lệnh rẽ nhánh, câu lệnh lặp của ngôn ngữ lập trình.
- Sử dụng các kí hiệu toán học, dấu phép toán, kí hiệu gợi tả để làm rõ ý tưởng thuật toán.
- Các kí hiệu được chọn và quy ước rõ để tránh nhầm lẫn.
- Có thể sử dụng thêm các từ ngắn gọn sau khi đã định nghĩa rõ ràng.
Quy ước cụ thể khi viết mã giả
Ta sẽ ưu tiên dùng một số yếu tố của ngôn ngữ lập trình Python trong các bài học khi mô tả thuật toán bằng mã giả. Dưới đây là một số quy ước:
- 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.
+ Số lần lặp chưa biết trước: Phỏng theo mẫu lệnh while của Python.
- 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.
+ Phép gán dùng dấu mũi tên trái.
- 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.
+ Có thể định nghĩa thêm kí hiệu phép toán cho các việc cụ thể.
Ví dụ: phép đổi chỗ hai phần tử x, y trong dãy số thường được viết gọn là swap(x,y) trong các thuật toán sắp xếp.
1.2. Làm mịn dần các bước mô tả thuật toán
- Mô tả thuật toán bằng liệt kê các bước cần làm.
- Cần làm chi tiết từng bước tiến gần đến ngôn ngữ lập trình.
- Mã giả là một sự lựa chọn phù hợp để trình bày.
- 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. Sau đây là các ví dụ minh hoạ.
- Ví dụ 1: Kiểm tra số nguyên tố
+ Đầu vào: số nguyên dương n.
+ Đầu ra: True nếu n là số nguyên tố, False nếu ngược lại.
- Thuật toán bao gồm bốn bước:
+ Bước 1: Kiểm tra n = 1, nếu đúng trả về False.
+ Bước 2: Kiểm tra n = 2, nếu đúng trả về True.
+ Bước 3: Kiểm tra tính nguyên tố của n và trả kết quả kiểm tra True hoặc False.
+ Bước 4: Kết thúc.
- Nhận thấy Bước 1 và Bước 2 đã chi tiết và đơn giản nên có thể chuyển thành câu lệnh Python dễ dàng.
- Bước 3 “Kiểm tra tính nguyên tố của n với n>2” cần được chi tiết và “làm mịn dần” lần lượt theo từng nhận xét sau:
+ Nhận xét 1: Nếu n chia hết cho số nguyên dương k (2≤k
* Với mỗi số nguyên dương k trong khoảng 2 ≤ k < n.
* Nếu n chia hết cho k thì n không là số nguyên tố.
* Các số k (2 ≤k< n) được biểu diễn qua hàm range bằng câu lệnh: range(2,n).
- Hình 1 minh hoạ mã giả và các câu lệnh Python kiểm tra số nguyên tố sau khi chỉ tiết Bước 3 theo Nhận xét 1.
Mã giả và các câu lệnh Python sau khi chi tiết Bước 3 theo Nhận xét 1
+ Nhận xét 2: Ta chỉ cần kiểm tra với k không lớn hơn căn bậc hai của n.
+ Cách chi tiết cho Bước 3:
* Với k từ 2 đến căn bậc hai của n.
* Nếu n chia hết cho k thì n không là số nguyên tố.
* Các số k (2 ≤ k ≤ căn bậc hai của n) được biểu diễn qua hàm range bằng câu lệnh: range(2, int(math.sqrt(n))+1).
Hình 2 minh hoạ mã giả và các câu lệnh Python kiểm tra số nguyên tố ở Bước 3 sau khi chi tiết theo Nhận xét 2.
Mã giả và các câu lệnh Python sau khi chi tiết Bước 3 theo Nhận xét 2
+ Nhận xét 3: Số chẵn lớn hơn 2 không là số nguyên tố. Chỉ cần kiểm tra với k lẻ và không lớn hơn √n.
* Nếu n chẵn và n>2 thì n không là số nguyên tố.
* Kiểm tra n chia hết cho k với k lẻ và 3
* Các số k lẻ (3 ≤ k ≤ √n) được biểu diễn qua hàm range bằng câu lệnh: range (3, int (math.sqrt (n)) +1,2).
Hình 3 minh hoạ mã giả và các câu lệnh Python kiểm tra số nguyên tố ở Bước 3 sau khi chi tiết theo Nhận xét 3.
Mã giả và các câu lệnh Python sau khi chi tiết Bước 3 theo nhận xét 3
- Ví dụ 2. Bài toán sàng số nguyên tố: Cho trước số tự nhiên n, hãy sàng lọc chỉ giữ lại những số là số nguyên tố trong dãy {0, 1, 2,..., n}.
+ Đầu vào: một số nguyên dương n
+ Đầu ra: in ra danh sách tương ứng đánh dấu True (là số nguyên tố) hay False (là hợp số).
- Thuật toán thô:
- Bước 1. Tạo danh sách prime gồm n + 1 giá trị logic True;
- Bước 2. Với m ≥ 2, kiểm tra nếu m là một bội số của k (k < m) thì gán prime[m] = False;
- Bước 3. Gán prime[0] = False; prime[1] = False.
- Một cách chi tiết Bước 2 như sau:
+ Bắt đầu với m = 3;
+ Lặp khi m ≤n:
+ Nếu với k nào đó (2 ≤ k ≤ m − 1) mà m chia hết cho k thì m không là số nguyên tố; m ¬ m+1
+ Hết lặp
- Mã giả và các câu lệnh Python tương ứng cho Bước 2 có trong Hình 4.
Mã giả và các câu lệnh Python chi tiết Bước 2
- Thuật toán sàng Eratosthenes tìm tất cả các số nguyên tố nhỏ hơn hay bằng n bằng cách đánh dấu các số không phải số nguyên tố là "hợp số".
- Dựa trên ý tưởng đục bỏ dần các số không nguyên tố được cho là tìm ra bởi nhà toán học Hy Lạp trước Công nguyên Eratosthenes.
1.3. Thực hành
Đọc mã lệnh của thuật toán Eratosthenes ở Hình 5 và mô tả liệt kê các bước của thuật toán và bằng mã giả.
Mã lệnh của thuật toán Eratosthenes
Bài tập minh họa
Hãy cho biết cách viết phép gán bằng mã giả, dấu bằng = có ý nghĩa gì trong mã giả?
Hướng dẫn giải:
Phép gán được sử dụng để gán giá trị cho một biến trong lập trình. Trong mã giả, phép gán được viết bằng dấu bằng "=", với biến ở bên trái dấu bằng và giá trị muốn gán ở bên phải. Dấu bằng "=" trong mã giả chỉ thực hiện phép gán giá trị cho biến, không phải là một mệnh đề so sánh.
3. Luyện tập Bài 4 Chủ đề FCS SGK Tin học 11 Cánh diều
Học xong bài này, em sẽ:
- Giải thích được sơ bộ phương pháp làm mịn dần trong lập trình.
- Biết được mã giả là gì và sử dụng được mã giả làm mịn dần một số thuật toán đơn giản.
3.1. Trắc nghiệm Bài 4 Chủ đề FCS SGK Tin học 11 Cánh diều
Như vậy là các em đã xem qua bài giảng Bài 4 Chủ đề FCS SGK Tin học 11 Cánh diều Khoa học máy tính. Để củng cố kiến thức bài học mời các em tham gia bài tập trắc nghiệm Trắc nghiệm Tin học 11 Cánh Diều Chủ đề FCS Bài 4.
Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!
3.2. Bài tập Bài 4 Chủ đề FCS SGK Tin học 11 Cánh diều
Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 11 Cánh Diều Chủ đề FCS Bài 4 để giúp các em nắm vững bài học và các phương pháp giải bài tập.
Khởi động trang 101 SGK Tin học 11 Cánh diều - CD
Hoạt động trang 102 SGK Tin học 11 Cánh diều - CD
Thực hành trang 105 SGK Tin học 11 Cánh diều - CD
Vận dụng 1 trang 106 SGK Tin học 11 Cánh diều - CD
Vận dụng 2 trang 106 SGK Tin học 11 Cánh diều - CD
Câu hỏi 1 trang 106 SGK Tin học 11 Cánh diều - CD
Câu hỏi 2 trang 106 SGK Tin học 11 Cánh diều - CD
Câu hỏi 3 trang 106 SGK Tin học 11 Cánh diều - CD
4. Hỏi đáp Bài 4 Chủ đề FCS SGK Tin học 11 Cánh diều
Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học của HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!
Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!
-- Mod Tin Học 11 HỌC247
