Giáo án và PPT Khoa học máy tính 11 kết nối Bài 27: Thực hành thiết kế chương trình theo phương pháp làm mịn dần

BÀI 27: THỰC HÀNH THIẾT KẾ CHƯƠNG TRÌNH THEO PHƯƠNG PHÁP LÀM MỊN DẦN

A. KHỞI ĐỘNG

- GV dẫn dắt, đặt vấn đề cho HS: Phương pháp làm mịn dần là một trong các cách tiếp cận tổng quát khi giải quyết các bài toán cụ thể. 

- GV đặt câu hỏi yêu cầu HS trả lời: Em có thể sử dụng sơ đồ cây để mô tả phương pháp này không?

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

Bài toán gốc: Cho trước dãy số A gồm n phần tử, cần kiểm tra xem A có phải là một hoán vị của dãy số 1, 2,..., n hay không.

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

Bước 1. Thiết lập ý tưởng thiết kế ban đầu

Sơ đồ khung ban đầu của lời giải như sau:

1 Sắp xếp dãy A theo thứ tự tăng dần

2 Kiểm tra A có phải là dãy 1, 2, …, n hay không

Bước 2. Sắp xếp dãy A

- Việc sắp xếp dãy A theo thứ tự tăng dần được mô tả bằng hàm sapxep(A) theo một trong các thuật toán sắp xếp mà chúng ta đã biết.

- Ví dụ bằng thuật toán sau:

1 def sapxep(A):

2     for i in range(len(A)):

3       j = i

4       while j > 0 and A[j] < A[j-1]:

5           A[j],A[j-1] = A[j-1],A[j]

6           j = j – 1

Bước 3. Với dãy A đã được sắp xếp, kiểm tra A có phải là dãy [1, 2, …, n]?

- Việc kiểm tra này có thể được thực hiện đơn giản như sau:

Kiểm tra lần lượt các phần tử của A với các phần tử tương ứng của dãy 1, 2, …, n. Nếu tất cả các so sánh đều bằng nhau thì trả về kết quả True, ngược lại trả về False.

- Sử dụng biến kq để trả lại kết quả của việc so sánh A và dãy các số 1, 2, …, n, ta có thể viết đoạn chương trình chi tiết thực hiện công việc được mô tả trên như sau:

1      sapxep(A)

2      kq = True

3      for i in range(len(A)):

4           if A[i] != i+1:

5              kq = False

6              break

7      return kq

- Kết quả của toàn bộ bước này có thể viết dưới dạng hàm kt_hoanvi(A), trong đó A là dãy số ban đầu. Hàm sẽ trả về True nếu A là hoán vị của [1, 2, …, n] ngược lại trả về False.

1 def kt_hoanvi(A):

2     sapxep(A)

3     kq = True

4     for i in range(len(A)):

5         if A[i] != i+1:

6            kq = False

7            break

8      return kq

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

- GV tổ chức cho HS làm Bài 1, 2 phần Luyện tập trang 126 SGK:

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

- GV yêu cầu nhóm HS (3 - 4 HS) hoàn thành bài tập phần Vận dụng trang 126 SGK.