[Lý thuyết] Phương pháp làm mịn dần trong thiết kế chương trình. SVIP

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

Phương pháp làm mịn dần gồm ba bước: 

• Bước 1: Phân tích bài toán và đề xuất ý tưởng dưới dạng các bước.
• Bước 2: Chi tiết hóa ý tưởng của các bước trước thành hành động cụ thể.
• Bước 3: Chuyển hóa từ hành động cụ thể thành chương trình.

❓Ví dụ: 

Thực hiện phương pháp cho bài toán sắp xếp dãy theo thứ tự tăng dần.

• Đầu vào: Dãy số A: A[0], A[1],..., A[n-1].
• Đầu ra: Dãy số A sau sắp xếp: A[0] ≤ A[1] ≤ ... ≤ A[n-1].

Ta có thể xây dựng tóm tắt thông qua sơ đồ sau.

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

Xét 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[i] đượ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).

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

Chi tiết hóa khung chính của chương trình.

Bước 2: Chi tiết hóa các hành động.

Làm mịn hành động 2. Tìm tất cả các cặp chỉ số (i, j).

Như vậy cần 2 vòng lặp theo i và j, để tiết kiện thời gian ta có:

• Chỉ số i: 0 → n-2.
• Chỉ số j: i+1 → n-1.

Làm mịn hành động 3. Kiểm tra tính nghịch đảo của (i, j).

Cặp (i, j) nghịch đảo khi và chỉ khi i < j và A[i] > A[j], vì bước 2 đã thiết lập các cặp (i,j) với điều kiện i < j do đó chỉ còn một điều kiện A[i] > A[j].

 Bước 3: Hoàn thiện chương trình.

Tổng kết kiến thức

Các quy trình và nguyên tắc:

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