1 of 46

2 of 46

KHỞI ĐỘNG

Em đã biết thiết kế một số thuật toán và chương trình: tìm kiếm tuần tự, tìm kiếm nhị phân, sắp xếp chèn, sắp xếp nổi bọt.

Thảo luận nhóm 3 - 4 HS

  • Tất cả các thiết kế chương trình đó có điểm nào chung?
  • Theo em, để thiết kế một thuật toán đúng giải một bài toán cho trước cần trải qua các bước như thế nào? Nêu quan điểm của riêng em và trao đổi với các bạn.

3 of 46

Các thuật toán và chương trình như tìm kiếm tuần tự, tìm kiếm nhị phân, sắp xếp chèn, sắp xếp nổi bọt trên đều là các thuật toán cơ bản trong lập trình và giải quyết các vấn đề thông thường. Điểm chung của các bài toán đó là có tính đơn giản và độ phức tạp thấp.

4 of 46

Để thiết kế một thuật toán đúng giải một bài toán cho trước cần trải qua các bước:

1. Xác định bài toán

2. Tìm cấu trúc dữ liệu biểu diễn thuật toán

3. Tìm thuật toán

4. Lập trình

5. Kiểm thử chương trình

6. Tối ưu chương trình

5 of 46

BÀI 26:

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

6 of 46

NỘI DUNG BÀI HỌC

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

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

7 of 46

1.

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

8 of 46

Thảo luận nhóm 3 - 5 HS

Hoạt động 1:

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?

9 of 46

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

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.

10 of 46

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

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

11 of 46

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í"

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

12 of 46

Bước 3:

Nhấc A[i] lên.

Thao tác này đượ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.

1 j = i – 1

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

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

4 j = j – 1

13 of 46

Bước 5:

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

Thao tác chèn A[i] vào đúng vị trí có thể được thực hiện bằng các câu lệnh chương trình như sau:

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

14 of 46

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

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

15 of 46

MỞ RỘNG

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.

16 of 46

Phương pháp thiết kế top-down có thể mô tả bằng sơ đồ ý tưởng sau:

17 of 46

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

18 of 46

Câu 1 (SGK - tr.120). 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?

Câu hỏi củng cố kiến thức

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 một lệnh: value = A[i].
  • Bước 5 được thực hiện bằng 1 lệnh: A[j+1] = value.

19 of 46

Câu hỏi củng cố kiến thức

Câu 2 (SGK - tr.120). 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?

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.

20 of 46

2.

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

21 of 46

Hoạt động 2:

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

22 of 46

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.

23 of 46

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

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

24 of 46

Bước 2:

Tìm tất cả các cặp chỉ số (i, j)

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

25 of 46

Bước 3:

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

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

26 of 46

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

27 of 46

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.

28 of 46

Câu 1 (SGK - tr.122).

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?

Câu hỏi củng cố kiến thức

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

29 of 46

Câu hỏi củng cố kiến thức

Câu 1 (SGK - tr.122).

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?

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)

30 of 46

Câu hỏi củng cố kiến thức

Câu 2 (SGK - tr.122).

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

31 of 46

BÀI TẬP TRẮC NGHIỆM

Câu 1: Mệnh đề nào sau đây mô tả đúng về phương pháp thiết kế làm mịn dần?

B. Thiết kế được chia làm nhiều bước, bước sau thường là chi tiết hơn, làm mịn hơn một bước ở trước đó.

A. Thiết kế được chia làm nhiều bước, các bước đều độc lập hoàn toàn với nhau.

C. Thiết kế được chia làm nhiều bước, bước sau thường là tổ hợp, kết hợp các kết quả của các bước trước đó.

D. Thiết kế được chia làm nhiều bước, mỗi bước sẽ tương ứng với một hàm hoặc chương trình con nào đó của bước trước.

32 of 46

Câu 2: Cho các nội dung sau:

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

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

3. Thiết lập ý tưởng thiết kế ban đầu.

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

5. Nhấc A[i] lên.

Thao tác thiết kế chương trình giải bài toán đúng là

D. 3 → 2 → 5 → 1 → 4

A. 1 → 2 → 3 → 4 → 5

B. 5 → 4 → 3 → 2 → 1

C. 4 → 3 → 5 → 1 → 2

33 of 46

Câu 3: Trong dãy [5, 8, 6, 9, 7] có cặp nghịch đảo là

A. (8, 7)

B. (7, 6)

C. (9, 8)

D. (7, 5)

34 of 46

Câu 4: Phương pháp thiết kế làm mịn dần còn được gọi là

C. phương pháp thiết kế từ trên xuống

A. phương pháp thiết kế từ phải sang trái

B. phương pháp thiết kế từ trái sang phải

D. phương pháp thiết kế từ dưới lên

35 of 46

Câu 5: Có bao nhiêu nguyên tắc khi sử dụng phương pháp làm mịn dần trong thiết kế chương trình?

A. 3

B. 4

C. 5

D. 6

36 of 46

LUYỆN TẬP

Bài 1 (SGK-tr.122). Phát biểu sau đúng hay sai?

Khi thiết kế chương trình thì việc đầu tiên là tìm hiểu yêu cầu chung của bài toán, xác định đầu vào, đầu ra của bài toán, sau đó mới đi cụ thể vào chi tiết.

Phát biểu đúng

37 of 46

Bài 2 (SGK-tr.122). Sử dụng thiết kế của Bài toán ở Hoạt động 2, tìm tất cả các cặp nghịch đảo của dãy: 3, 2, 1, 5, 4.

Hướng dẫn

  • Bước 1: Giống như đã làm trong SGK.
  • Bước 2: Liệt kê tất cả các cặp chỉ số (i,j) với i < j. Các cặp số tương ứng sẽ như sau:

(3,2), (3,1), (3,5), (3,4)

(2,1), (2,5), (2,4)

(1,5), (1,4)

(5,4)

38 of 46

  • Bước 3: Kiểm tra xem trong các cặp trên, cặp số nào là nghịch đảo. Các cặp nghịch đảo thu được như sau, đánh dấu bằng in đậm.

(3,2), (3,1), (3,5), (3,4)

(2,1), (2,5), (2,4)

(1,5), (1,4)

(5,4)

Kết quả thu được 4 cặp nghịch đảo: (3,2), (3,1), (2,1), (5,4).

39 of 46

VẬN DỤNG

Bài 1 (SGK - tr.122). Sử dụng phương pháp làm mịn dần để giải bài toán sau: Cho trước số tự nhiên không âm n, viết chương trình kiểm tra xem số n có phải là số nguyên tố hay không. Chương trình cần thông báo "CÓ" nếu n là số nguyên tố, ngược lại thông báo "KHÔNG".

40 of 46

Hướng dẫn

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

Input: n số tự nhiên cho trước. Output: "CÓ" nếu n là nguyên tố, ngược lại thông báo "KHÔNG".

41 of 46

b) Các bước thiết kế chi tiết

Bước 1:

Thiết lập ý tưởng thiết kế ban đầu

Số tự nhiên là số nguyên tố nếu nó lớn hơn 1 và chỉ có ước số là 1 và chính nó. Chúng ta sẽ thiết lập hàm prime(n), hàm này trả về True nếu n là nguyên tố, ngược lại trả về False.

1. Nếu n ≤ 1 thì trả về False

2. Nếu n > 1 thì đi tìm các ước số thực sự của n bắt đầu từ 2. Nếu có ước như vậy thì trả vé False

3. Trả về True.

42 of 46

Bước 2:

Chi tiết hoá yêu cầu mức 1.

if n <= 1:

return False

Bước 3:

Chi tiết hoá yêu cầu mức 2.

for k in range(2, n):

if n % k == 0:

return False

Bước 4:

Chi tiết hoá yêu cầu mức 3.

return True.

43 of 46

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

1 def prime(n):

2 if n <= 1:

3 return False

4 else:

5 for k in range(2,n):

6 if n%k == 0:

7 return False

8 return True

9 n = 5

10 if prime(n):

11 print("CÓ")

12 else:

13 print("KHÔNG")

44 of 46

Bài 2 (SGK - tr.122). Với thuật toán sắp xếp chèn, chứng minh rằng nếu thay toàn bộ phần <Chèn A[i] vào vị trí đúng của dãy con A[e], A[1], ..., A[i − 1]> bằng các lệnh sau thì chương trình vẫn đúng:

1 j = i

2 while j > 0 and A[j] < A[j-1]:

3 Đổi chỗ A[j] và A[j-1]

4 j = j – 1

Đây chính là phương án 2 của thuật toán sắp xếp.

GỢI Ý

45 of 46

HƯỚNG DẪN VỀ NHÀ

01

03

02

Ghi nhớ kiến thức đã học trong bài

Hoàn thành bài tập trong SBT

Chuẩn bị bài sau - Bài 27: Thực hành

46 of 46