Giáo án Khoa học máy tính 11 kết nối 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.