Video 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

Xin chào các em học sinh thân mến, chúng ta lại gặp nhau trong bài học ngày hôm nay rồi!

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:

• Thực hành thiết kế chương trình theo phương pháp làm mịn dần.
• Biết thiết kế và cài đặt chương trình theo phương pháp làm mịn dầ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 cho cô câu hỏi: 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ể. Em có thể sử dụng sơ đồ cây để mô tả phương pháp này không?

HOẠT ĐỘNG KHÁM PHÁ

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.

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

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

………..

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