Video giảng 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ừ các thuật toán đến chương trình máy tính

Tóm lược 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

Thông qua video này, các em sẽ nắm được các kiến thức và kĩ năng như sau:

• 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ải làm mịn dần một số thuật toán đơn giản.

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

Trước khi bước vào bài học ngày hôm nay, các em suy nghĩ và trả lờ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

Nội dung 1: Mã giả và mô tả thuật toán bằng mã giả

Theo em:

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

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

Video trình bày nội dung:

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

Nội dung 2: Làm mịn dần các bước mô tả thuật toán

Em hãy trình bày cách thức chung làm mịn dần các bước mô tả thuật toán.

Video trình bày nội dung:

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. 

Nội dung 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ả.

Video trình bày nội dung:

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

………..

Nội dung video 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òn nhiều phần rất hấp dẫn và thú vị. Hãy cùng đăng kí để tham gia học bài và củng cố kiến thức thông qua hoạt động luyện tập và vận dụng trong video.