Lý thuyết Tin học 11 (Cánh diều) 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

Lý thuyết Tin học 11 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

A. Lý thuyết Làm mịn dần từng bước từ thuật toán đến chương trình máy tính

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.

- 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<n) thì n không là số nguyên tố. Bước 3 có thể được chi tiết như sau:

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

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

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

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

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

B. Bài tập Làm mịn dần từng bước từ thuật toán đến chương trình máy tính

Đang cập nhật…

Xem thêm các bài lý thuyết Tin học 11 sách Cánh diều hay, chi tiết tại: 

Lý thuyết Bài 5: Đánh giá thuật toán

Lý thuyết Bài 6: Kiểm thử và sửa lỗi chương trình

Lý thuyết Bài 7: Lập trình giải bài toán tìm kiếm

Lý thuyết Bài 8: Lập trình một số thuật toán sắp xếp

Lý thuyết Bài 9: Lập trình thuật toán sắp xếp nhanh