Nội dung chính Tin học 11 theo định hướng khoa học máy tính 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

BÀI 26. PHƯƠNG PHÁP LÀM MỊN DẦN TRONG THIẾT KẾ CHƯƠNG TRÌNH

1. PHƯƠNG PHÁP THIẾT KẾ LÀM MỊN DẦN

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

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

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

2. THIẾT KẾ CHƯƠNG TRÌNH BẰNG PHƯƠNG PHÁP LÀM MỊN DẦN

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

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

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