Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. Việc đó được lặp lại cho đến khi không có sự đổi chỗ nào xảy ra nữa. | THUẬT TOÁN SẮP XẾP BẰNG TRÁO ĐỔI Lê Anh Nhật Email: leanhnhat@tuyenquang.edu.vn 1. Xác định bài toán Input Dãy A gồm N số nguyên a1, a2, ., aN. Dãy A được sắp xếp lại thành dãy không giảm. Output 2. Ý tưởng Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. Việc đó được lặp lại cho đến khi không có sự đổi chỗ nào xảy ra nữa. ? 3. Thuật toán liệt kê Bước 1 Nhập N, các số hạng a1, a2, ., aN; Bước 2 M := N; Bước 3 Nếu M 3. Thuật toán liệt kê Bước 5 i := i + 1; Bước 6 Nếu i > M thì quay lại bước 3; Bước 7 Nếu ai > ai+1 thì đổi ai và ai+1 cho nhau; Bước 8 Quay lại bước 5; 4. Thuật toán sơ đồ khối Nhập: N, a1, a2, ., aN M := N M M ai > ai+1 Tráo đổi ai và ai+1 Đ S S Đ 5. Ví dụ mô phỏng 6 2 5 3 7 8 10 7 12 4 Cho dãy số có 10 phần tử: Sắp xếp dãy trên tăng dần theo thật toán tráo đổi? 5. Ví dụ mô phỏng 6 2 5 3 7 8 10 7 12 4 M = 9; 2 6 5 6 6 3 7 10 4 12 5. Ví dụ mô phỏng M = 8; 2 5 3 6 7 8 7 10 4 12 3 5 7 8 4 10 5. Ví dụ mô phỏng M = 7; 2 3 5 6 7 7 8 4 10 12 4 8 5. Ví dụ mô phỏng M = 6; 2 3 5 6 7 7 4 8 10 12 4 7 5. Ví dụ mô phỏng M = 5; 2 3 5 6 7 4 7 8 10 12 4 7 5. Ví dụ mô phỏng M = 4; 2 3 5 6 4 7 7 8 10 12 4 6 5. Ví dụ mô phỏng M = 3; 2 3 5 4 6 7 7 8 10 12 4 5 5. Ví dụ mô phỏng M = 2; 2 3 4 5 6 7 7 8 10 12 5. Ví dụ mô phỏng M = 1; 2 3 4 5 6 7 7 8 10 12 Ta được dãy đã sắp xếp: Kết thúc. 6. Bài tập Cho dãy số có 13 số: 3, 6, 2, 5, 13, 21, 1, 9, 10, 14, 15, 2, 8. Áp dụng thuật toán trên để sắp xếp dãy trên giảm dần? Từ thuật toán trên, sử dụng ngôn ngữ lập trình mà bạn biết để lập trình bài toán tổng quát đó? . | THUẬT TOÁN SẮP XẾP BẰNG TRÁO ĐỔI Lê Anh Nhật Email: leanhnhat@tuyenquang.edu.vn 1. Xác định bài toán Input Dãy A gồm N số nguyên a1, a2, ., aN. Dãy A được sắp xếp lại thành dãy không giảm. Output 2. Ý tưởng Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. Việc đó được lặp lại cho đến khi không có sự đổi chỗ nào xảy ra nữa. ? 3. Thuật toán liệt kê Bước 1 Nhập N, các số hạng a1, a2, ., aN; Bước 2 M := N; Bước 3 Nếu M 3. Thuật toán liệt kê Bước 5 i := i + 1; Bước 6 Nếu i > M thì quay lại bước 3; Bước 7 Nếu ai > ai+1 thì đổi ai và ai+1 cho nhau; Bước 8 Quay lại bước 5; 4. Thuật toán sơ đồ khối Nhập: N, a1, a2, ., aN M := N M M ai > ai+1 Tráo đổi ai và ai+1 Đ S S Đ 5. Ví dụ mô phỏng 6 2 5 3 7 8 10 7 12 4 Cho dãy số có 10 phần tử: Sắp xếp dãy trên tăng dần theo thật toán tráo đổi? 5. Ví dụ mô phỏng 6 2 5 3 7 8 10 7 12 4 M = 9; 2 6 5 6 6 3 7 10 4 12 5. Ví dụ mô phỏng M = 8; 2 5 3 6 7 8 7 10 4 12 3 5 7 8 4 10 5. Ví dụ mô phỏng M = 7; 2 3 5 6 7 7 8 4 10 12 4 8 5. Ví dụ mô phỏng M = 6; 2 3 5 6 7 7 4 8 10 12 4 7 5. Ví dụ mô phỏng M = 5; 2 3 5 6 7 4 7 8 10 12 4 7 5. Ví dụ mô phỏng M = 4; 2 3 5 6 4 7 7 8 10 12 4 6 5. Ví dụ mô phỏng M = 3; 2 3 5 4 6 7 7 8 10 12 4 5 5. Ví dụ mô phỏng M = 2; 2 3 4 5 6 7 7 8 10 12 5. Ví dụ mô phỏng M = 1; 2 3 4 5 6 7 7 8 10 12 Ta được dãy đã sắp xếp: Kết thúc. 6. Bài tập Cho dãy số có 13 số: 3, 6, 2, 5, 13, 21, 1, 9, 10, 14, 15, 2, 8. Áp dụng thuật toán trên để sắp xếp dãy trên giảm dần? Từ thuật toán trên, sử dụng ngôn ngữ lập trình mà bạn biết để lập trình bài toán tổng quát đó?
