Soạn mới giáo án Khoa học máy tính 11 kết nối tri thức bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

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, mỗi nhóm 3 - 5 HS.

- GV chiếu lại bài toán sắp xếp chèn:

Bài toán gốc. Cho trước dãy số A: A[0], A[1],..., A[n–1]. Cần tiến hành sắp xếp dãy trên theo thứ tự tăng dần. Kết quả phải nhận được:

A[0] ≤ A[1] ≤  … ≤  A[n-1]

Ví dụ với bộ dữ liệu vào là dãy [2, 1, 7, 10, 4] thì kết quả thu được dãy [1, 2, 4, 7, 10].

- GV yêu cầu các nhóm HS thực hiện Hoạt động 1 tr.118 SGK: Cùng trao đổi, thảo luận các bước thiết kế chương trình theo thuật toán sắp xếp chèn, từ đó đưa ra phương pháp chính khi thiết kế chương trình. Sau mỗi bước thiết kế cần trao đổi và trả lời các câu hỏi sau:

1. Bước này đã thực hiện công việc gì?

2. Kết quả vừa thực hiện với kết quả của bước trước đó khác nhau như thế nào?

- GV yêu cầu các nhóm rút ra kết luận về phương pháp thiết kế làm mịn dần.

- GV yêu cầu HS trả lời câu hỏi củng cố tr.120 SGK:

1. Trong các bước đã thực hiện của bài toán sắp xếp chèn ở trên, bước nào là đơn giản nhất theo nghĩa có thể thực hiện ngay bằng các lệnh lập trình?

2. Nếu bài toán đặt ra là sắp xếp dãy A theo thứ tự giảm dần thì các bước thiết kế như trên có cần thay đổi không? Thay đổi như thế nào?

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

- HS thảo luận nhóm, đọc SGK và thực hiện nhiệm vụ được giao.

- GV quan sát, hướng dẫn (nếu cần).

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

- Đại diện nhóm HS trình bày.

- HS xung phong trả lời câu hỏi:

*Câu hỏi củng cố tr.120 SGK:

1. Các bước đơn giản nhất của cách thiết kế trên là bước 3 và 5.

+ Bước 3 được thực hiện bằng 1 lệnh: value = A[i].

+ Bước 5 được thực hiện bằng 1 lệnh: A[j+1] = value.

2. Không cần thay đổi gì, chỉ thay đổi một từ trong cách mô tả tại bước 4 như sau: Chuyển các phần tử bên trái A[i] và nhỏ hơn A[i] sang phải.

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

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

- GV nhận xét, đánh giá kết quả thảo luận của HS.

- GV mở rộng kiến thức: Phương pháp thiết kế làm mịn dần (stepwise refinement) trong khoa học máy tính còn có tên gọi là phương pháp thiết kế từ trên xuống (top-down design) là một trong những phương pháp thiết kế lâu đời nhất và được coi là phương pháp tổng quát nhất, chung nhất cho cách lập trình cấu trúc. Phương pháp thiết kế top-down này có thể mô tả bằng sơ đồ ý tưởng sau.

- GV chốt kiến thức và gọi phương pháp thiết kế vừa nêu chính là phương pháp thiết kế làm mịn dần.

1. Phương pháp thiết kế làm mịn dần

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

Bài toán gốc là cho trước dãy A, cần sắp xếp lại dãy này theo thứ tự tăng dần.

b) Thiết kế chương trình giải bài toán

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

- Cần duyệt một lượt từ phần tử thứ hai đến phần tử cuối của dãy sao cho khi kết thúc thì dãy cũng được được sắp xếp xong.

→ Phần chính: một vòng lặp với biến i chạy từ chỉ số 1 đến n – 1.

- Với mỗi giá trị i, cần thực hiện một số thao tác để bổ sung A[i] vào dãy các phần tử đã được sắp xếp A[0], A[1],... A[i-1] sao cho dãy mới thu được từ A[0] đến A[i] được sắp xếp đúng.

⇒ Thuật toán ban đầu có thể được mô tả như sau:

1  for i in range (1,n):

2      <Đặt A[i] vào đúng vị trí của dãy A[0],A[1}, …, A[i-1]>

- Tại dòng 2 của sơ đồ trên, bài toán được đặt ra là: "Chèn phần tử A[i] vào đúng vị trí của dãy A[0], A[1], …, A[i-1]".

Bước 2. Làm chi tiết hơn, thực hiện việc "Chèn A[i] vào đúng vị trí"

- Vì các phần tử bên trái của A[i] là A[0], A[1],...,A[i-1] đã được sắp xếp đúng nên thao tác "chèn" phần tử A[i] sẽ được thực hiện như sau:

<Lấy phần tử A[i] ra và lần lượt chuyển các phần tử bên trái A[i]  nhưng có giá trị lớn hơn A[i] sang phải. Sau đó đặt A[i] vào vị trí trống>

Theo mô tả trên, việc "Chèn A[i] vào đúng vị trí" có thể thực hiện như sau:

Chèn A[i] vào đúng vị trí

1  Nhấc phần tử A[i] lên.

2  Chuyển các phần tử bên trái A[i] và lớn hơn A[i] sang phải.

3  Chèn A[i] vào vị trí trống.

Các bước tiếp theo sẽ làm mịn hơn, chi tiết hơn thao tác trên.

Bước 3. Nhấc A[i] lên.

Thao tác này sẽ được thực hiện đơn giản bằng việc tạo ra một biến mới value để lưu trữ giá trị A[i].

value = A[i]

Bước 4. Chuyển các phần tử bên trái A[i] và lớn hơn A[i] sang phải.

Thao tác này có thể được thực hiện như sau

- Thiết lập biến j = i – 1 là chỉ số của phần tử ngay bên trái A[i].

- Liên tục so sánh A[j] với value:

nếu A[j] > value thì chuyển A[j] sang phải một vị trí bằng lệnh A[j+1] = A[j] và giảm j = j – 1.

- Quá trình sẽ kết thúc khi đi hết bên trái của dãy hoặc A[j] <= value.

Tất cả công việc này được thể hiện bằng đoạn chương trình sau:

1 j = i – 1

2 while j >= 0 and A[j] > value:

3     A[j+1] = A[j]

4     j = j – 1

Bước 5. Chèn A[i] vào đúng vị trí trống

- Từ bước 4 chúng ta đã biết quá trình chuyển sang phải của các phần tử A[j] sẽ kết thúc khi A[j] <= A[i], do đó vị trí j + 1 chính là vị trí trống cần chèn.

- Việc chèn phần tử A[i] (giá trị được lưu trong value) vào vị trí j + 1 được thực hiện bằng câu lệnh:

A[j+1] = value

Như vậy, ba thao tác đã nêu ở bước 2 trên có thể được thực hiện bằng các câu lệnh chương trình như sau:

Chèn A[i] vào đúng vị trí

1 value A[i]

2 j = i – 1

3 while j >= 0 and A[j] > value:

4        A[j+1] = A[j]

5        j = j – 1

6 A[j+1] = value

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

- Chương trình giải bài toán đặt ra được thiết kế hoàn chỉnh dưới dạng hàm InsertionSort(A).

- Tổng hợp các bước trên chúng ta có chương trình hoàn chỉnh như sau:

1 def InsertionSort(A):

2     n = len(A)

3     for i in range(1,n):

4         value = A[i]

5         j = i-1

6       while j >= 0 and A[j] > value:

7          A[j+1] = A[j]

8          j = j - 1

9       A[j+1] = value

⇨ Kết luận:

- Các bước thiết kế sắp xếp chèn được mô tả như sau:

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

2) Thiết kế chương trình giải bài toán

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

Bước 2. Làm chi tiết hơn, thực hiện việc "Chèn A[i] vào đúng vị trí".

Bước 3. Nhấc A[i] lên.

Bước 4. Chuyển các phần tử bên trái A[i] và lớn hơn A[i] sang phải.

Bước 5. Chèn A[i] vào đúng vị trí trống.

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

- Phương pháp làm mịn dần trong thiết kế chương trình là quá trình chi tiết hóa từ ý tưởng của các bước trước thành những hành động cụ thể hơn ở các bước sau. Ở bước cuối cùng, các hành động tương ứng với các câu lệnh của ngôn ngữ lập trình để viết chương trình hoàn chỉnh.

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 tổ chức cho HS tiếp tục hoạt động nhóm thực hiện Hoạt động 2 SGK tr.120: Thực hiện thiết kế thuật toán và chương trình bằng phương pháp làm mịn dần theo các bài toán sau. Trao đổi, thảo luận với bạn bè để thiết lập được lời giải tốt hơn.

Bài toán. Cho trước dãy số A: A[0], A[1], …, A[n-1]. Cặp phần tử A[i], A[j] được gọi là nghịch đảo nếu i < j nhưng A[i] > A[j]. Cần viết chương trình đếm số các cặp nghịch đảo của dãy A. Ví dụ dãy 3, 4, 2, 1 sẽ có 5 cặp nghịch đảo là (3,2), (3,1), (4,2), (4,1), (2,1).

- GV yêu cầu mỗi nhóm thiết kế thuật toán cho bài toán trên theo hướng dẫn của SGK, ghi lại các bước thiết kế cụ thể và nộp bài thiết kế cùng chương trình.

- GV yêu cầu HS trả lời câu hỏi Củng cố tr.122 SGK:

1. Với bài toán ở Hoạt động 1, có thể tách các dòng lệnh từ 4 đến 9 thành một hàm con độc lập được không?

2. Trong thiết kế bài toán tìm các cặp phần tử nghịch đảo, các bước sau đã thực hiện những thay đổi quan trọng nào so với bước trước đó?

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

- HS thảo luận nhóm, đọc SGK và thực hiện nhiệm vụ được giao.

- GV quan sát, hướng dẫn (nếu cần).

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

- GV mời 1 - 2 nhóm trình bày kết quả thảo luận.

- HS xung phong trả lời câu hỏi củng cố:

1. Các dòng lệnh từ dòng 4 đến 9 có thể tách thành hàm con có dạng Chen(A,j,value) như sau:

1 def chen(A,j,value):

2    while j >= 0 and A[j] > value:

3       A[j+1] = A[j]

4       j = j - 1

5     A[j+1] = value

Khi đó thuật toán sắp xếp chèn có thể viết lại như sau:

1 def InsertionSort(A):

2     n = len(A)

3     for i in range(1,n):

4         value = A[i]

5         j = i-1

6         chen(A,j,value)

2. Bước 2 đã chi tiết hóa yêu cầu tại dòng 2 của lược đồ ban đầu được vạch ra tại bước 1.

- Bước 3 đã chi tiết hóa phần mô tả tại dòng 4, 5 của chương trình đã nêu trong bước 2.

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

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

- GV nhận xét, đánh giá kết quả thảo luận của HS.

- GV tổng kết và chốt kiến thức.

2. Thiết kế chương trình bằng phương pháp làm mịn dần

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

Bài toán gốc là cho trước dãy số A có n phần tử, cần đếm số các cặp phần tử nghịch đảo của A.

b) Thiết kế chương trình giải bài toán

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

- Phần khung chính của chương trình sẽ là:

<Đếm số lượng các cặp số nghịch đảo (A[i], A[j]) của dãy A, trả về giá trị này>

- Công việc cần thực hiện:

+ Tìm tất cả các cặp chỉ số (i,j) có thể tạo cặp nghịch đảo A[i], A[j].

+ Kiểm tra xem cặp này có là nghịch đảo không, nếu có thì tăng biến đếm lên 1 đơn vị.

- Lược đồ thuật toán ban đầu có thể được mô tả như sau:

1 count = 0

2 Tìm tất cả các cặp chỉ số (i,j) có thể tạo ra cặp phần tử nghịch đảo

3 Kiểm tra nếu cặp A[i], A[j] là nghịch đảo thì tăng count lên 1 đơn vị.

4 return count

Bước 2. Tìm tất cả các cặp chỉ số (i,j)

- Thiết lập hai vòng lặp theo i, j để tìm.

- Chú ý để tiết kiệm thời gian chúng ta sẽ chỉ tìm các chỉ số i chạy từ 0 đến n – 2, chỉ số j tính từ i + 1 đến n – 1.

- Kết quả bước làm mịn này là đoạn chương trình sau:

for i in range(n – 1):

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

Như vậy tới bước này, thuật toán gốc có thể được mô tả như sau:

1 count = 0

2 for i in range(n-1):

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

4       if <cặp (i,j) là nghịch đảo>:

5         tăng count lên 1 đơn vị

6 return count

Bước 3. Kiểm tra tính nghịch đảo của cặp (i,j)

- Cặp (i,j) sẽ là nghịch đảo khi và chỉ khi i < j và A[i] > A[j], tuy nhiên tại bước 2 đã thiết lập được tất cả các cặp (i,j) với điều kiện i < j do đó việc kiểm tra nghịch đảo chỉ còn một điều kiện là A[i] > A[j].

- Kết quả làm mịn của bước 3 như sau:

if A[i] > A[j]:

     count = count + 1

- Thao tác chi tiết cần thực hiện để giải bài toán đã gần hoàn thành như sau:

1 count = 0

2 for i in range(n-1):

3     for j in range(1,n):

4         if A[i] > A[j]:

5             count = count + 1

6 return count

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

1 def Nghichdao(A):

2     n = len(A)

3     count = 0

4     for i in range(n-1):

5        for j in range(1,n):

6          if A[i] > A[j]:

7             count = count + 1

8     return count

⇨ Kết luận: Phương pháp làm mịn dần trong thiết kế chương trình phải tuân thủ các quy trình và nguyên tắc sau:

- Chia việc thiết kế thành từng bước và thực hiện lần lượt các bước.

- Mỗi bước lớn có thể được chia thành nhiều bước nhỏ hơn để giải quyết độc lập.

- Tiếp cận bài toán từ tổng quan đến chi tiết, mỗi bước tiếp theo sẽ phải là thiết kế chi tiết hơn bước trước đó. Quá trình như vậy sẽ tiếp tục cho đến khi  viết xong toàn bộ các câu lệnh của chương trình giải bài toán đã cho.