Giáo án và PPT Khoa học máy tính 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

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

HOẠT ĐỘNG KHỞI ĐỘNG

GV đặt câu hỏi: 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?

HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1: Mã giả và mô tả thuật toán bằng mã giả

GV yêu cầu học sinh trao đổi: 

Thế nào là mã giả?

Quy ước cụ thể khi viết mã giả là gì?

Sản phẩm dự kiến:

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

Hoạt động 2: Làm mịn dần các bước mô tả thuật toán

Cách thức chung làm mịn dần các bước mô tả thuật toán

Sản phẩm dự kiến:

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. 

Hoạt động 3: Thực hành

a) Đọc mã lệnh của thuật toán Eratosthenes cho ở Hình 5 sau đó mô tả thuật toán bằng liệt kê các bước và bằng mã giả.

b) Em hãy viết chương trình thực hiện sàng số nguyên tố sử dụng thuật toán thô và sử dụng thuật toán Eratosthenes. Sau đó chạy thử và so sánh kết quả.

Sản phẩm dự kiến:

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ố

       ifprime[p]:

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

           fori 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

HOẠT ĐỘNG LUYỆN TẬP

Câu 1. Mô tả bằng mã giả câu lệnh m += 1 là

A. m = 1               B. m ≥ 1                C. m ← 1              D. m ← m + 1

Câu 2. Câu lệnh Python của mã giả for i in {i|i lẻ, 3 ≤ i  ≤ } là 

A. for i in range (3, int (math.sqrt(n))+1, 2)

B. for i in range (3, int (math.sqrt(n)+1, 2)

C. for i in range (3, (math.sqrt(n))+1, 2)

D. for i in range (3, int (math.(n))+1, 2)

Câu 3. Mã giả: if n = 1: 

                             Trả về False

Chuyển sang câu lệnh Python là

A. if (n = 1):                                                C. if (n == 1):

return False                                                 return False

B. if (n ← 1):                                                        D. if (n > 1):

          return False                                                 return False

Câu 4. Thuật toán sàng Eratosthenes là

A. một thuật toán cổ để tìm tất cả các số nguyên dương n nhỏ hơn hay bằng n.

B. một thuật toán cổ để tìm tất cả các số nguyên tố n nhỏ hơn hay bằng n.

C. một thuật toán cổ để tìm tất cả các số nguyên n nhỏ hơn hay bằng n.

D. một thuật toán cổ để tìm tất cả các số nguyên tố n nhỏ hơn n.

Câu 5. Cho thuật toán sau:

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 == 2

          prime[m] = False

     m += 1

prime[0]= False

prime[1]= False

return prime

Cho biết câu lệnh nào không đúng?

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

B.  m += 1

C.  prime[m] = False                                                                

D. if m % i == 2

Đáp án gợi ý:

HOẠT ĐỘNG VẬN DỤNG

GV yêu cầu HS hoàn thành Vận dụng SGK trang 106:

Câu 1. Em hãy nêu một điều kiện sàng khác cho bài toán sàng số: In ra danh sách các số nguyên dương nhỏ hơn n và thỏa mãn điều kiện sàng mới.

Gợi ý: Ví dụ “không là số chính phương”.

Câu 2. Viết mô tả mã giả cho thuật toán tương ứng với Câu 1.