Câu hỏi 1: Có hai chất lỏng khác màu là xanh và đỏ, lần lượt được chứa trong hai chiếc cốc A và B (Hình 16.1a). Chúng ta cần đổi chỗ hai chất lỏng này, sao cho cốc A đựng chất lỏng màu đỏ, còn cốc B đựng chất lỏng màu xanh. Để thực hiện công việc này, chúng ta sử dụng thêm một chiếc cốc thứ ba (cốc C) không đựng gì. Em hãy quan sát Hình 16.1b, Hình 16. 1c, Hình 16.1d để biết cách thực hiện.
1. THUẬT TOÁN SẮP XẾP NỔI BỌT
Hoạt động 1:
Em hãy thực hiện thuật toán sắp xếp nổi bọt để sắp xếp 5 số sau đây theo thứ tự tăng dần. Hãy mô phỏng các bước sắp xếp bằng hình vẽ minh họa tương tự như Hình 16.2, Hình 16.3, Hình 16.4.
Câu hỏi 1: Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách
A. Chọn phần tử có giá trị bé nhất đặt vào đầu danh sách.
B. Chọn phần tử có giá trị lớn nhất đặt vào đầu danh sách.
C. Hoán đổi nhiều lần các phần tử liền kề nếu giá trị của chúng không đúng thứ tự.
D. Chèn phần tử vào vị trí thích hợp để đảm bảo danh sách sắp xếp theo đúng thứ tự.
2. THUẬT TOÁN SẮP XẾP CHỌN
Hoạt động 2:
1. Chọn năm học sinh, mỗi học sinh viết ra tờ giấy một con số mà mình yêu thích. Các em đứng thành một hàng ngang và cầm tớ giấy có ghi con số để cả lớp có thể quan sát được.
Ví dụ:
Học sinh thứ sau thực hiện thuật toán sắp xếp chọn để sắp xếp các con số của năm bạn theo thứ tự tăng dần.
Câu hỏi 1: Em hãy viết vào vở cụ thể các bước của vòng lặp thứ 2, 3, 4 được mô tả trong hình 16.5.
3. CHIA BÀI TOÁN THÀNH NHỮNG BÀI TOÁN NHỎ HƠN
Câu hỏi 1: Tại sao chúng ta chia bài toán thành những bài toán nhỏ hơn?
A. Để thay đổi đầu vào của bài toán.
B. Để thay đổi yêu cầu đầu ra của bài toán.
C. Để bài toán dề giải quyết hơn.
D. Để bài toán khó giải quyết hơn.
LUYỆN TẬP
Luyện tập 1: Em hãy liệt kê các bước của thuật toán sắp xếp nổi bọt để sắp xếp các số 3, 2, 4, 1, 5, theo thứ tự tăng dần.
Luyện tập 2: Em hãy liệt kê các bước của thuật toán sắp xếp chọn để sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.
VẬN DỤNG
Em hãy ghi lại kết quả điểm học tập môn Tin học của các bạn trong tổ. Thực hiện thuật toán sắp xếp chọn hoặc sắp xếp nổi bọt để sắp xếp điểm theo thứ tự giảm dần. Dựa trên kết quả sắp xếp, hãy cho biết danh sách tên các bạn tương ứng theo kết quả sắp xếp đó.
PHẦN II .Lời giải tham khảo
KHỞI ĐỘNG
Câu hỏi 1: Đổi chỗ hai chất lỏng trong hai chiếc cốc A và B bằng cốc trung gian C
Để thực hiện việc đổi chỗ hai chất lỏng trong cốc A và cốc B, chúng ta sử dụng cốc C như một trung gian. Quy trình như sau:
Rót chất lỏng màu xanh từ cốc A vào cốc C. Lúc này cốc A trống, cốc C chứa chất lỏng màu xanh, còn cốc B vẫn chứa chất lỏng màu đỏ.
Rót chất lỏng màu đỏ từ cốc B vào cốc A. Lúc này cốc A chứa chất lỏng màu đỏ, cốc C chứa chất lỏng màu xanh, và cốc B trống.
Rót chất lỏng màu xanh từ cốc C vào cốc B. Kết quả: cốc A chứa chất lỏng màu đỏ, cốc B chứa chất lỏng màu xanh, đúng yêu cầu bài toán.
1. THUẬT TOÁN SẮP XẾP NỔI BỌT
Hoạt động 1: Mô phỏng thuật toán sắp xếp nổi bọt
Dãy số cần sắp xếp: 5, 3, 4, 1, 2. Chúng ta sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy số này theo thứ tự tăng dần. Quy trình như sau:
Bước 1: So sánh hai phần tử liền kề và hoán đổi nếu phần tử trước lớn hơn phần tử sau. Sau mỗi vòng lặp, phần tử lớn nhất "nổi" lên vị trí cuối dãy.
Lần lặp 1:
So sánh 5 và 3, hoán đổi → dãy: 3, 5, 4, 1, 2.
So sánh 5 và 4, hoán đổi → dãy: 3, 4, 5, 1, 2.
So sánh 5 và 1, hoán đổi → dãy: 3, 4, 1, 5, 2.
So sánh 5 và 2, hoán đổi → dãy: 3, 4, 1, 2, 5.
Lần lặp 2:
So sánh 3 và 4, giữ nguyên → dãy: 3, 4, 1, 2, 5.S
o sánh 4 và 1, hoán đổi → dãy: 3, 1, 4, 2, 5.
So sánh 4 và 2, hoán đổi → dãy: 3, 1, 2, 4, 5.
Lần lặp 3:
So sánh 3 và 1, hoán đổi → dãy: 1, 3, 2, 4, 5.
So sánh 3 và 2, hoán đổi → dãy: 1, 2, 3, 4, 5.
Lần lặp 4:
Không có hoán đổi nào xảy ra, dãy đã được sắp xếp: 1, 2, 3, 4, 5.
Câu hỏi 1: Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách nào?
Đáp án đúng là: C. Hoán đổi nhiều lần các phần tử liền kề nếu giá trị của chúng không đúng thứ tự.
2. THUẬT TOÁN SẮP XẾP CHỌN
Hoạt động 2: Mô phỏng thuật toán sắp xếp chọn
Ví dụ dãy số: 5, 3, 4, 1, 2. Quy trình như sau:
Bước 1: Tìm phần tử nhỏ nhất trong dãy và hoán đổi với phần tử đầu tiên.
Bước 2: Lặp lại thao tác trên cho phần còn lại của dãy (bỏ qua phần đã sắp xếp).
Lần lặp 1:Tìm phần tử nhỏ nhất trong dãy 5, 3, 4, 1, 2 là 1.
Hoán đổi 1 và 5 → dãy: 1, 3, 4, 5, 2.
Lần lặp 2:Tìm phần tử nhỏ nhất trong dãy 3, 4, 5, 2 là 2.
Hoán đổi 2 và 3 → dãy: 1, 2, 4, 5, 3.
Lần lặp 3:Tìm phần tử nhỏ nhất trong dãy 4, 5, 3 là 3.
Hoán đổi 3 và 4 → dãy: 1, 2, 3, 5, 4.
Lần lặp 4:Tìm phần tử nhỏ nhất trong dãy 5, 4 là 4.
Hoán đổi 4 và 5 → dãy: 1, 2, 3, 4, 5.
Câu hỏi 1: Các bước của vòng lặp thứ 2, 3, 4 được mô tả như trên.
3. CHIA BÀI TOÁN THÀNH NHỮNG BÀI TOÁN NHỎ HƠN
Câu hỏi 1: Tại sao chúng ta chia bài toán thành những bài toán nhỏ hơn?
Đáp án đúng là: C. Để bài toán dễ giải quyết hơn.
LUYỆN TẬP
Luyện tập 1: Thuật toán sắp xếp nổi bọt cho dãy 3, 2, 4, 1, 5
Các bước tương tự như đã mô tả ở phần "Hoạt động 1". Kết quả cuối cùng là: 1, 2, 3, 4, 5.
Luyện tập 2: Thuật toán sắp xếp chọn cho dãy 3, 2, 4, 1, 5
Các bước tương tự như đã mô tả ở phần "Hoạt động 2". Kết quả cuối cùng là: 1, 2, 3, 4, 5.
VẬN DỤNG
Sắp xếp điểm học tập theo thứ tự giảm dần
Ghi lại điểm học tập của các bạn trong tổ.
Áp dụng thuật toán sắp xếp nổi bọt hoặc chọn như đã học.
Kết quả là danh sách điểm giảm dần kèm theo tên của các bạn, giúp sắp xếp danh sách theo thứ tự xếp hạng từ cao xuống thấp.
