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 SVIP

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

Mã giả độc lập với ngôn ngữ lập trình, môi trường lập trình thực hiện thuật toán là cách mô tả thuật toán rất gần với văn bản mã lệnh chương trình.

Không có một quy ước thống nhất chính thức nào về mã giả.

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. 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 mẫu lệnh while. 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.
• 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 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 đó. 

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.

🔵Ví dụ. 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:

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

Nhận thấy Bước 1 và Bước 2 có thể chuyển thành câu lệnh Python dễ dàng. Bước 3 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 > 2 thì với k (2 ≤ k < n) là số nguyên dương bất kì mà n chia hết cho k thì n không là số nguyên tố.

• Nếu n chia hết cho k thì n không là số nguyên tố.
• Các số k được biểu diễn qua hàm range bằng câu lệnh: range(2,n)

🔻Nhận xét 2. Nếu n chia hết cho k nghĩa là n = k*m (hoặc k ≤ \(\sqrt{n}\) hoặc \(m\le\sqrt{n}\)) → kiểm tra với k không lớn hơn \(\sqrt{n}\):

• Với k \(\left(2\le k\le\sqrt{n}\right)\): Nếu n chia hết cho k thì n không là số nguyên tố.
• Các số \(\left(2\le k\le\sqrt{n}\right)\) được biểu diễn qua hàm range bằng câu lệnh: range (2, int (math.sqrt(n))+1)

🔻Nhận xét 3. Số chẵn lớn hơn 2 không là số nguyên tố. Như vậy chỉ cần kiểm tra với k lẻ và không lớn hơn \(\sqrt{n}\):

• Nếu n chẵn và n > 2 thì n không là số nguyên tố. Trái lại, kiểm tra n chia hết cho k với k lẻ và \(3\le k\le\sqrt{n}\).
• Các số k lẻ (\(3\le k\le\sqrt{n}\)) được biểu diễn qua hàm range bằng câu lệnh: range(3, int (math.sqrt(n)) +1,2)