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

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. 

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

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.

Trả lời:

Đáp án đúng:

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

26.2. Phương pháp thiết kế làm mịn dần chính là tên gọi khác của phương pháp thiết kế từ trên xuống. Đúng hay sai?

Trả lời:

Phương pháp thiết kế làm mịn dần chính là tên gọi khác của phương pháp thiết kế từ trên xuống. Đây là ý kiến ĐÚNG.

26.3. Phát biểu sau về phương pháp làm mịn dần là đúng hay sai?

Phương pháp thiết kế làm mịn dần sẽ chia bài toán gốc thành các bài toán con, mỗi bài toán con sẽ lại được phân tích và chia thành các bài toán vấn đề con nhỏ hơn nữa. Quá trình phân rã thành các bài toán con đó sẽ còn tiếp tục cho đến khi nhận được bài toán đủ đơn giản để có thể giải ngay bằng các câu lệnh lập trình. Quá trình thiết kế đó sẽ kết thúc khi tất cả các bài toán con được giải quyết hoàn toàn.

Trả lời:

Phát biểu trên về phương pháp làm mịn dần là ĐÚNG.

26.4. Với một bài toán, chỉ có một phương pháp thiết kế làm mịn dần duy nhất. Đúng hay sai?

Trả lời:

Với một bài toán, chỉ có một phương pháp thiết kế làm mịn dần duy nhất. Đây là ý kiến SAI

26.5. Hãy trình bày thuật toán tìm kiếm tuần tự theo phương pháp làm mịn dần. 

Trả lời:

Một cách trình bày theo phương pháp làm mịn dần có thể như sau:

Bài toán: Cho trước mảng A (Có n phần tử) và giá trị K. Cần tìm phần tử của A có giá trị bằng K. Nếu tìm thấy trả lại chỉ số của phần tử này (chỉ cần tìm một nghiệm), ngược lại trả về -1.

Bước 1: Thiết lập ý tưởng thiết kế.

Duyệt các phần tử của mảng A từ trái sang phải

Giả sử chỉ số đang duyệt là i, kiểm tra A[i] = K hay không,

nếu đúng thì dừng lại, trả về i

Cuối cùng trả về -1.

Bước 2: Chi tiết hóa dòng 1 ở trên.

Bước 3: Chi tiết hóa dòng 2 của ý tưởng thiết kế ban đầu.

Bước 4: Chi tiết hóa dòng 3 của ý tưởng thiết kế ban đầu.

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

26.6. Hãy trình bày thuật toán sắp xếp chọn theo phương pháp làm mịn dần. 

Trả lời:

Một cách trình bày theo phương pháp làm mịn dần có thể như sau:

Bài toán: Cho trước dãy A có n phần tử. Cần sắp xếp dãy A theo thứ tự tăng dần theo thuật toán chọn.

Bước 1: Phân tích và thiết lập ý tưởng thiết kế ban đầu

Duyệt chỉ số i từ đầu đến vị trí gần cuối

Tìm phần tử bé nhất trong dãy các phần tử bên phải và

đổi chỗ với phần tử hiện thời

Bước 2: Chi tiết hóa dòng 1 ở trên.

Bước 3: Chi tiết hóa dòng 2 của ý tưởng thiết kế ban đầu.

Bước 4: Đổi chỗ với phần tử hiện thời.

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

26.7.* Hãy trình bày thuật toán sắp xếp nổi bọt theo phương pháp làm mịn dần.

Trả lời:

Một cách trình bày theo phương pháp làm mịn dần có thể như sau:

Bài toán: Cho trước dãy A có n phần tử. Cần sắp xếp dãy A theo thứ tự tăng dần theo thuật toán nổi bọt.

Bước 1: Phân tích và thiết lập ý tưởng thiết kế ban đầu

Lặp cho đến khi dãy ban đầu đã được sắp xếp đúng

Duyệt 1 lượt phần tử từ trái sang phải

Nếu 2 phần tử cạnh nhau sắp xếp không đúng

Đổi chỗ 2 phần tử này

Bước 2: Chi tiết hóa công việc trong dòng 2 của ý tưởng thiết kế ban đầu.

Bước 3: : Chi tiết hóa công việc trong dòng 3 của ý tưởng thiết kế ban đầu.

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