Slide bài giảng Khoa học máy tính 11 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

Slide điện tử 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. Trình bày với các hiệu ứng hiện đại, hấp dẫn. Giúp học sinh hứng thú học bài. Học nhanh, nhớ lâu. Có tài liệu này, hiệu quả học tập của học môn Khoa học máy tính 11 Cánh diều sẽ khác biệt

Bạn chưa đủ điều kiện để xem được slide bài này. => Xem slide bài mẫu

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

 

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

GV đặt câu hỏi: Khi lập trình để giải quyết một bài toán theo thuật toán đã cho, em sẽ bắt đầu như thế nào? Theo em, phương pháp này có đúng hay không?

NỘI DUNG BÀI HỌC GỒM

  • Mã giả và mô tả thuật toán bằng mã giả
  • Làm mịn dần các bước mô tả thuật toán
  • Thực hành
  • Luyện tập
  • Vận dụ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: 

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

Nội dung gợi ý:

- 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 để cải tiến và làm rõ các bước mô tả thuật toán là gì?

Nội dung gợi ý:

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) Hãy đọc mã lệnh của thuật toán Eratosthenes trong Hình 5, sau đó mô tả thuật toán bằng cách liệt kê các bước và viết mã giả cho nó.

NỘI DUNG BÀI HỌC GỒM

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

Nội dung gợi ý:

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

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

Câu 1: Quá trình giải bài toán trên máy tính gồm mấy bước?

   A. 2

  B. 3

  C. 4

  D. 5

Câu 2:Thứ tự các bước giải bài toán trên máy tính:

   A. Xác định bài toán → Viết chương trình → Mô tả thuật toán

   B. Xác định bài toán → Mô tả thuật toán → Viết chương trình

   C. Mô tả thuật toán → Xác định bài toán → Viết chương trình

   D. Viết chương trình → Xác định bài toán → Mô tả thuật toán

Câu 3:Hãy cho biết kết quả sau khi thực hiện thuật toán sau:

   Bước 1. Tam←x;

   Bước 2. x←y;

   Bước 3. y← tam;

   A. Giá trị của biến x bằng giá trị của biến y

   B. Hoán đổi giá trị hai biến x và y

   C. Giá trị của biến y bằng giá trị của biến x

   D. Khác

Câu 4:Hãy xác đinh bài toán sau: "Tìm số lớn nhất trong dãy n số tự nhiên cho trước"?

   A. INPUT: Dãy n số tự nhiên. OUTPUT: Số lớn nhất trong dãy n số.

   B. INPUT: Dãy n số tự nhiên. OUTPUT: Số các số lớn nhất trong dãy n số.

   C. INPUT: Số lớn nhất trong dãy n số. OUTPUT: Dãy n số tự nhiên.

   D. INPUT: Số các số lớn nhất trong dãy n số. OUTPUT: Dãy n số tự nhiên.

Câu 5:Hãy chọn phát biểu Đúng:

   A. Các bước giải bài toán trên máy tính là: Mô tả thuật toán → Xác định bài toán → Viết chương trình

   B. Cần phải xác định bài toán trước khi giải bài toán trên máy tính

   C. Máy tính có hiểu được chương trình viết bằng ngôn ngữ tự nhiên

   D. Với mỗi bài toán cụ thể, phải lựa chọn ngôn ngữ lập trình phù hợp rồi mới xây dựng thuật toán giải bài toán đó

Đáp án gợi ý:

Câu 1

Câu 2

Câu 3

Câu 4

Câu 5

B

B

B

A

B

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. 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 phải là số chính phương”.

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