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
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.
Để 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
BÀI 26:
PHƯƠNG PHÁP LÀM MỊN DẦN TRONG THIẾT KẾ CHƯƠNG TRÌNH
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
1.
PHƯƠNG PHÁP THIẾT KẾ LÀM MỊN DẦN
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:
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.
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]".
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í"
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.
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
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
c) Chương trình hoàn chỉnh
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
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.
Phương pháp thiết kế top-down có thể mô tả bằng sơ đồ ý tưởng sau:
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.
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.
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.
2.
THIẾT KẾ CHƯƠNG TRÌNH BẰNG PHƯƠNG PHÁP LÀM MỊN DẦN
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).
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
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)
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)
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:
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
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)
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.
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.
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
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)
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
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
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
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
(3,2), (3,1), (3,5), (3,4)
(2,1), (2,5), (2,4)
(1,5), (1,4)
(5,4)
(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).
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".
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".
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.
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.
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")
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 Ý
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