Tự chủ và tự học: biết lắng nghe, tự giác học tập và hoàn thành nhiệm vụ; tích cực tham gia các hoạt động học tập trong lớp.
Giao tiếp và hợp tác: có thói quen trao đổi, giúp đỡ nhau trong học tập; biết cùng nhau hoàn thành nhiệm vụ học tập theo sự hướng dẫn của GV.
Giải quyết vấn đề và sáng tạo: ứng dụng các kiến thức đã học vào thực tế, phát triển khả năng giải quyết vấn đề có tính tích hợp liên môn giữa Tin học với các môn học khác.

Năng lực riêng:

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.

3. Phẩm chất

Trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU

1. Đối với giáo viên

SGK, tài liệu giảng dạy, giáo án PPT.
Máy tính, máy chiếu.

2. Đối với học sinh:

SGK, SBT Tin học 11, vở ghi chép.
Tài liệu, thiết bị có liên quan đến nội dung bài học.

III. TIẾN TRÌNH DẠY HỌC

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

a) Mục tiêu: HS nhắc lại các bước để thiết kế thuật toán theo phương pháp làm mịn dần đã học ở bài trước.

b) Nội dung: GV tổ chức trả lời câu hỏi ở phần Mở đầu.

c) Sản phẩm: Dựa vào kiến thức của bản thân, HS thực hiện yêu cầu GV đưa ra.

d) Tổ chức thực hiện:

Bước 1: GV chuyển giao nhiệm vụ:

- 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ước 2: HS thực hiện nhiệm vụ học tập: HS lắng nghe, suy nghĩ câu trả lời.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- GV gọi đại diện một số HS trả lời:

Gợi ý:

+ Phương pháp làm mịn dần, hay còn gọi là phương pháp giảm dần và chinh phục dần là một trong các cách tiếp cận tổng quát để giải quyết các bài toán cụ thể. Sơ đồ hình cây là một công cụ hữu ích để mô tả phương pháp này.

+ Sơ đồ hình cây là một biểu đồ hình cây đơn giản, thường được sử dụng để minh họa quá trình giải quyết bài toán bằng phương pháp làm mịn dần. Nó gồm các nút đại diện cho các bài toán con, và các nhánh đại diện cho các bước giải quyết bài toán con đó. Các nhánh này có thể tiếp tục được chia nhỏ cho đến khi không thể chia nhỏ hơn nữa (đạt được điều kiện dừng), sau đó các kết quả của các bài toán con được tổng hợp lại để đưa ra kết quả cuối cùng cho bài toán gốc.

- HS khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét câu trả lời của HS. Trên cơ sở đó, GV dẫn dắt HS vào bài học mới: Bài học trước chúng ta đã cùng nhau tìm hiểu về phương pháp làm mịn dần trong thiết kế chương trình. Để củng cố kiến thức đã học ở bài trước, chúng ta hãy cùng nhau vào - 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. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1: Thực hiện nhiệm vụ 1

a) Mục tiêu: Giúp HS thực hành được phương pháp làm mịn dần trong thiết kế chương trình kiểm tra hoán vị.

b) Nội dung: GV tổ chức cho HS thực hiện theo các hoạt động trong SGK và thực hành nhiệm vụ được giao.

c) Sản phẩm: Sản phẩm thực hành của HS.

d) Tổ chức thực hiện:

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV chia lớp thành các nhóm từ 2 – 4 HS.

- GV chiếu nhiệm vụ học tập:

Cho trước một dãy n số, các số được kí hiệu A[0], A[1],..., A[n-1]. Cần thiết kế chương trình kiểm tra xem dãy trên có phải là một hoán vị của dãy số 1, 2, …, n hay không. Chương trình cần thông báo kết quả là CÓ hoặc KHÔNG.

- GV mô tả nhiệm vụ và phác thảo các bước thiết kế chính theo phương pháp làm mịn dần:

+ Tìm hiểu bài toán

+ Thiết kế theo phương pháp làm mịn dần

+ Chương trình hoàn chỉnh

Bước 2: HS thực hiện nhiệm vụ học tập:

- HS lắng nghe GV hướng dẫn, đọc theo SGK và thực hiện việc cài đặt thành chương trình hoàn chỉnh, tạo bộ test theo hướng dẫn và kiểm tra xem chương trình đã viết có đúng không.

- GV quan sát và trợ giúp HS.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- HS báo cáo các bộ test theo hướng dẫn.

- HS khác nhận xét, bổ sung cho bạn.

Bước 4: Đánh giá kết quả thực hiện:

- Sau khi HS hoàn thành chương trình, GV nhận xét và tổng kết nội dung nhiệm vụ 1.

- GV chuyển sang hoạt động tiếp theo.

Nhiệm vụ 1. Kiểm tra hoán vị

a) Tìm hiểu bài toán

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.

b) Thiết kế theo phương pháp làm mịn dầ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 inrange(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 inrange(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 inrange(len(A)):

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

6 kq = False

7 break

8 return kq

c) Chương trình hoàn chỉnh

1 def sapxep(A):

2 for i inrange(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

8 def kt_hoanvi(A):

9 sapxep(A)

10 kq = True

11 for i inrange(len(A)):

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

13 kq = False

14 break

15 return kq

17 #Chương trình chính

18 A = [2,1,9,10,8,6,5,2,3,1]

19 if kt_hoanvi(A):

20 print("CÓ")

21 else:

22 print("KHÔNG")

Hoạt động 2: Thực hiện nhiệm vụ 2

a) Mục tiêu: Giúp HS thực hành được phương pháp làm mịn dần trong thiết kế chương trình đếm số lần lặp.

b) Nội dung: GV tổ chức cho HS thực hiện theo các hoạt động trong SGK và thực hành nhiệm vụ được giao.

c) Sản phẩm: Sản phẩm thực hành của HS.

d) Tổ chức thực hiện:

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV chiếu nhiệm vụ học tập:

Thiết kế và việc chương trình trình theo phương pháp làm mịn dần cho bài toán sau: Cho trước dãy số A[0], A[1], ...A[n-1]. Cần tính được mỗi giá trị của các phần tử của dãy trên được lặp lại bao nhiêu lần trong dãy đó. Kết quả cần được đưa ra dãy B. Như vậy dãy B sẽ có ý nghĩa như sau B[k] = số lần lặp của phần tử A[k] trong dãy A. Ví dụ nếu A = [2, 1, 1, 3, 5, 10, 2, 5] thì B = [2, 2, 2, 1, 2, 1, 2, 2]

Bước 2: HS thực hiện nhiệm vụ học tập:

- GV quan sát và trợ giúp HS.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- HS báo cáo các bộ test theo hướng dẫn.

- HS khác nhận xét, bổ sung cho bạn.

Bước 4: Đánh giá kết quả thực hiện:

- Sau khi HS hoàn thành chương trình, GV nhận xét và tổng kết nội dung nhiệm vụ 2.

- GV chuyển sang hoạt động luyện tập.

Nhiệm vụ 2. Đếm số lần lặp

a) Tìm hiểu bài toán

Bài toán gốc: cho trước dãy số A có n phần tử. Cần tạo ra một dãy mới là số các lần lặp của các phần tử tương ứng trong A.

b) Thiết kế theo phương pháp làm mịn dần

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

1 Thiết lập dãy B rỗng

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

3 Tính số lần lặp của A[i] trong dãy A

4 Bổ sung giá trị này vào dãy B

5 Trả về dãy B

Bước 2. Thiết lập dãy B rỗng

Thực hiện bằng lệnh B = [].

Bước 3. Tính số lần lặp của A[i] trong dãy A.

Thực hiện thông qua lời gọi hàm lap(x,A) tính số lần lặp của một giá trị bất kì trong dãy A. Hàm lap(x,A) có thể được viết như sau:

1 def lap(x,A):

2 S = 0

3 for a inA:

4 if a == x:

5 S = S + 1

6 return S

Bước 4. Bổ sung số lần lặp vào dãy B

Tổng hợp kết quả của các bước trên, đoạn chương trình hoàn chỉnh đã nêu ở bước 1 như sau:

1 B = []

2 for i inrange(len(A)):

3 B.append(lap(A[i],A))

4 return B

Bước 5. Trả về dãy B cần tìm của bài toán

Để hoàn thiện toàn bộ chương trình cần thiết lập hàm tinh_lap(A) mô tả đoạn chương trình đã nêu trong bước 4. Hàm tinh_lap(A) trả về dãy B cần tìm:

1 def tinh_lap(A):

2 B = []

3 for a inA:

4 B.append(lap(a,A))

5 return B

c) Chương trình hoàn chỉnh

1 def lap(x,A):

2 S = 0

3 for a inA:

4 if a == x:

5 S = S + 1

6 return S

8 def tinh_lap(A):

9 B = []

10 for a inA:

11 B.append(lap(a,A))

12 return B

13 # Chương trình chính

14 A = [2, 1, 1, 3, 5, 10, 2, 5, 2]

15 B = tinh_lap(A)

16 print(B)

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

a) Mục tiêu: HS củng cố cách xác định độ phức tạp của thuật toán.

b) Nội dung: HS vận dụng các kiến thức đã học để hoàn thành bài tập phần Luyện tập trang 126 SGK.

c) Sản phẩm học tập: Câu trả lời nội dung Luyện tập.

d) Tổ chức thực hiện:

Bước 1: GV chuyển giao nhiệm vụ:

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

Bài 1: Thiết kế thuật toán cho Nhiệm vụ 1 với ý tưởng khác như sau: Dây A là một hoán vị của dãy các số từ 1 đến n khi và chỉ khi dãy A có độ dài n và mọi số i từ 1 đến n đều nằm trong A.

Bài 2: Trong Nhiệm vụ 2, nếu dãy A đã được sắp xếp theo thứ tự tăng dần thì có thể cải tiến thuật toán tốt hơn được không?

Bước 2: HS thực hiện nhiệm vụ học tập:

- HS suy nghĩ, hoàn thành các bài tập GV yêu cầu.

- GV quan sát và hỗ trợ, hướng dẫn.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- HS thực hiện các thao tác.

Bài 1. Thiết kế lại Nhiệm vụ 1 theo ý tưởng khác. Các bước thực hiện như sau:

Bước 1. Thiết lập ý tưởng ban đầu theo cách mới

Thuật toán có thể như sau:

1. Gọi n là độ dài của dãy A.

2. Với mỗi số i chạy từ 1 đến n, kiểm tra xem i có nằm trong A hay không?

Nếu i không nằm trong A thì lập tức thông báo KHÔNG

3. Kết thúc vòng lặp thông báo CÓ

Bước 2. Công việc tại dòng 1 ở trên được thể hiện bằng lệnh:

n = len(A)

Bước 3. Chi tiết công việc tại dòng 2 ở trên.

Dòng 2 là một lệnh duyệt với chỉ số i chạy từ 1 đến n, kiểm tra nếu i không thuộc A thì lập tức dừng chương trình và thông báo "KHÔNG".

for i in range(1, n+1):

if i not in A:

return “KHÔNG”

Bước 4. Dòng 3 chính là lệnh.

return "CÓ"

Tổng hợp lại ta có chương trình hoàn chỉnh

1 def hoanvi(A):

2 n = len(A)

3 for i in range(1,n+1):

4 if i not in A:

5 return "KHÔNG"

6 return "CÓ"

Bài 2. Trường hợp nếu dãy A đã được sắp xếp tăng dần thì Nhiệm vụ 2 có thể cải tiến tốt hơn. Sau đây là một phương án làm tốt hơn bài toán này.

1 def tinlap(A):

2 if len(A) == 0:

3 return []

4 if len(A) == 1:

5 return [1]

6 B = []

7 i = 0

8 for j inrange(len(A)-1):

9 if A[j] < A[j+1]:

10 C = j - i + 1

11 for k in range(i, j+1):

12 B.append(C)

13 i = j+1

14 if j == len(A) - 2:

15 B.append(1)

16 else:

17 if j == len(A) – 2:

18 C = j - i + 2

19 for k in range(i,j+2):

20 B.append(C)

21 return B

Bước 4: Đánh giá kết quả thực hiện:

- GV chữa bài, chốt đáp án, tuyên dương các hoạt động tốt, nhanh và chính xác.

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

a) Mục tiêu: HS thực hiện làm bài tập Vận dụng để nắm vững kiến thức.

b) Nội dung: HS vận dụng kiến thức đã học và hiểu biết của bản thân để làm bài tập Vận dụng trang 126 SGK.

c) Sản phẩm: Câu trả lời nội dung Vận dụng.

d) Tổ chức thực hiện:

Bước 1: GV chuyển giao nhiệm vụ

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

1. Cho dãy số A = A[0], A[1], A[n – 1]. Thiết kế và viết chương trình kiểm tra trong dãy A có hai phần tử nào trùng nhau hay không. Cần đưa ra cầu trả lời là “có” hay “không”. Yêu cầu đưa ra quy trình thiết kế theo phương pháp làm mịn dần.

2. Xâu kí tự được gọi là đối xứng nếu thay đổi thứ tự ngược lại các kí tự của xâu thì vẫn nhận được dãy ban đầu. Ví dụ xâu “abcdcba” là đối xứng, còn xâu “1011” không là đối xứng.

Thiết kế và viết chương trình kiểm tra một xâu kí tự cho trước có là đối xứng hay không. Yêu cầu đưa ra quy trình thiết kế theo phương pháp làm mịn dần

Bước 2: HS thực hiện nhiệm vụ học tập

- Các nhóm HS thảo luận, tìm hiểu và viết chương trình.

- GV điều hành, quan sát, hỗ trợ.

Bước 3: Báo cáo kết quả hoạt động, thảo luận

- Đại diện nhóm trình bày kết quả.

Kết quả:

1. Chương trình kiểm tra xem dãy số A có phần tử lặp hay không.

→ Thiết kế hàm isRepeated(A), hàm sẽ trả lại True nếu dãy A có phần tử lặp, ngược lại sẽ trả về False.

Kết quả thiết kế hàm này như sau:

1 def isRepeated(A):

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

3 if A[i] in A[ :i]

4 return True

5 return False

2. Thiết kế thuật toán và chương trình cho bài toán kiểm tra xâu đối xứng hay không. Hàm palindrome(s) sẽ trả lại True nếu xâu s là đối xứng, ngược lại trả về False.

Chương trình có thể như sau:

1 def palindrome(s):

2 if len(s) == 0:

3 return True

4 m = len(s)//2

5 for i in range(m+1):

6 if S[i] != s[len(s) - 1 - i]:

7 return False

8 return True

Bước 4: Đánh giá kết quả thực hiện

- GV nhận xét, đánh giá, đưa ra một vài ý mà HS còn thiếu, chốt đáp án.

- GV tổng kết tiết học.