Câu hỏi:
27/11/2023 189Hã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.
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
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à ý tưởng thiết kế ban đầu.
Ý tưởng ban đầu của thuật toán này như sau:
Với mỗi phần tử của dãy, cần thiết lập vị trí chính xác của vị trí này trong dãy sao cho phía bên trái vị trí này bao gồm các phần tử đã đứng đúng vị trí.
Để thực hiện được ý tưởng trên, cách làm ban đầu là chọn ra phần tử đúng đó và đổi chỗ cho phần tử tại vị trí hiện thời. Từ đó dẫn đến việc phân rã bài
toán như sau:
1 Duyệt chỉ số i từ đầu đến vị trí gần cuối.
2 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 hoá dòng 1 trong thiết kế trên.
for i in range(n-1):
Bước 3. Chi tiết hoá công việc tại dòng 2.
Để tìm được phần tử nhỏ nhất bên phải vị trí i và sau đó đổi chỗ cho vị trí i chúng ra sẽ tìm vị trí đó thông qua chỉ số. Kết quả của bước này như sau:
Quảng cáo
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
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.
Câu 2:
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.
Câu 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.
Câu 4:
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.
Câu 5:
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.
Câu 6:
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?
về câu hỏi!