Slide bài giảng 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

Tóm lược nội dung

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

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?

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

• Thực hành

• Luyện tập

• Vận dụng

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

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

Nội dung gợi ý:

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     fori in range(len(A)):

3       j = i

4       whilej > 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      fori 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     fori in range(len(A)):

5         ifA[i] != i+1:

6            kq = False

7            break

8      return kq

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:

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.