Bài giảng Tin học 10 - Tuần 5, Bài 4: Bài toán và thuật toán (Tt)

Nội dung tài liệu: Bài giảng Tin học 10 - Tuần 5, Bài 4: Bài toán và thuật toán (Tt)

1. Bài 4. Bài toán và thuật Toán (tt) Thuật toỏn sắp xếp trỏo đổi Bài toỏn: Cho dóy A gồm N số nguyờn dương a1, a2, , aN sắp xếp dóy khụng giảm * Xỏc định bài toỏn INPUT: Dóy gồm N số nguyờn a1, a2, , aN. OUTPUT: Dóy A sắp xếp thành dóy khụng giảm * í 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 đi lặp lại cho đến khi khụng cú sự đổi chổ nào xảy ra nữa.
2. Mụ phỏng thuật toỏn sắp xếp trỏo đổi  Với N = 6 và dóy gồm 6 số như sau: 3 5 9 8 1 7  Lượt 1:  Lượt 2 3 5 9 8 1 7 3 5 8 1 7 9 3 5 8 9 1 7 3 5 1 8 7 9 3 5 1 7 8 9 3 5 8 1 9 7  Lượt 3: 3 5 8 1 7 9  Lượt 4 3 1 5 7 8 9 3 5 1 7 8 9 3 1 5 7 8 9 1 3 5 7 8 9
3. * Thuật toỏn B1: Nhập N, cỏc số a1, a2, , aN; B2: M  N; B3: Nếu M<2 thỡ đưa ra dóy A đó được sắp xếp rồi kết thỳc; B4: M  M – 1; i  0; B5: i  i +1; B6: Nếu i>M thỡ quay lại bước 3; B7: Nếu ai > ai+1 thỡ trỏo đổi a i và ai+1 cho nhau; B8: Quay lại B5.