Nội dung chính tin học 11 theo định hướng khoa học máy tính 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

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

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

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

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

- Thuật toán sàng Eratosthenes: Sàng Eratosthenes là một thuật toán cổ để tìm tất cả các số nguyên tố nhỏ hơn hay bằng n.

-  Ý tưởng: Đục bỏ dần các số không nguyên tố bằng cách đánh dấu là “là hợp số” (không phải số nguyên tố) mỗi khi biết số đó là bội số của một số nguyên tố.

3. THỰC HÀNH

a) Thuật toán sàng Eratosthenes: Đục bỏ dần các số không nguyên tố bằng cách đánh dấu “là hợp số” (không phải số nguyên tố) mỗi khi biết số đó là bội số của một số nguyên tố.

Mô tả thuật toán bằng liệt kê

Bước 1: Tạo danh sách prime gồm n + 1 giá trị logic True.

Bước 2: Giả sử tất cả các số trong danh sách đều là số nguyên tố. Trong đó, p = 2 là số nguyên tố đầu tiên.

Bước 3: Tất cả các bội số của p bị đánh dấu vì không phải là số nguyên tố.

Bước 4:

- Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn p.

- Nếu không có số nào, dừng tìm kiếm.

- Ngược lại, gán cho p giá trị bằng số nguyên tố tiếp theo và quay lại bước 3.

- Gán prime [0] = False; prime[1] = False

Mô tả thuật toán bằng mã giả

Khai báo hàm SieveOfEratosthenes(n)

# Tạo mảng biến Boolean “prime [0..n]; gán giá trị ban đầu tất cả là True.

# Kết cục prime[i] sẽ là False nếu i không là số nguyên tố

#Còn lại là số nguyên tố

prime ← for i in {i| 0 ≤ i  ≤ n} đúng

p ← 2

while p*p ≤ n:

    #Nếu prime[p] không bị sửa thành False thì p là số nguyên tố

       if prime[p]:

           # Đục bỏ các bội số của p

           for i in {i|p, p*p ≤ i  ≤ n}:

           prime[i] ← False

       p ← p + 1

prime[0] ← False

prime[1] ← False

Trả về prime

b) Chương trình thuật toán thô:

def sangTho(n)

 prime = [True for i in range(n + 1)]

  m = 3

  while (m <= n):

      for i in range (2,m)

        if m % i == 0:

          prime[m] = False

     m += 1

prime[0]= False

prime[1]= False

return prime