Giải Tin Học 7 trang 79
Lời giải chi tiết SGK Lớp 7 · Môn Tin Há»c · Trang 79–80
Tổng quan nội dung
Trang 79 – 80 thuộc Bài 16: Thuật toán sắp xếp. Đây chủ yếu là phần lý thuyết giới thiệu về thuật toán sắp xếp nổi bọt (Bubble Sort), không có bài tập dạng câu hỏi trực tiếp.
Tuy nhiên, có 1 hoạt động khởi động yêu cầu học sinh quan sát và suy nghĩ. Mình sẽ giải thích chi tiết hoạt động này.
Hoạt động khởi động: Bài toán hoán đổi chất lỏng
Đề bài:
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.
Cách giải — Phân tích các bước hoán đổi
Bước 1: Trạng thái ban đầu (Hình 16.1a)
- Cốc A: chứa chất lỏng màu xanh
- Cốc B: chứa chất lỏng màu đỏ
- Cốc C: rỗng (không chứa gì)
Bước 2: Đổ cốc A vào cốc C (Hình 16.1b)
- Cốc A: rỗng
- Cốc B: chứa chất lỏng màu đỏ
- Cốc C: chứa chất lỏng màu xanh
Bước 3: Đổ cốc B vào cốc A (Hình 16.1c)
- Cốc A: chứa chất lỏng màu đỏ
- Cốc B: rỗng
- Cốc C: chứa chất lỏng màu xanh
Bước 4: Đổ cốc C vào cốc B (Hình 16.1d)
- Cốc A: chứa chất lỏng màu đỏ
- Cốc B: chứa chất lỏng màu xanh
- Cốc C: rỗng
Kết quả: Hai chất lỏng đã được hoán đổi vị trí thành công!
💡 Mẹo nhớ: Khi hoán đổi giá trị của 2 biến trong lập trình, ta cần dùng biến trung gian (giống như cốc C). Quy trình: A → C, B → A, C → B
Tóm tắt lý thuyết: Thuật toán sắp xếp nổi bọt
Ý tưởng chính:
Thuật toán sắp xếp nổi bọt xét từng vị trí từ đầu đến cuối dãy. Tại mỗi vị trí, thuật toán tìm phần tử nhỏ nhất trong những phần tử phía sau để đưa vào vị trí đó.
Ví dụ minh họa:
Sắp xếp dãy số 4, 2, 3, 1 theo thứ tự tăng dần.
Vòng lặp thứ nhất (xét vị trí đầu tiên):
- So sánh 1 và 3 → 1 < 3 → hoán đổi → [4, 2, 1, 3]
- So sánh 1 và 2 → 1 < 2 → hoán đổi → [4, 1, 2, 3]
- So sánh 1 và 4 → 1 < 4 → hoán đổi → [1, 4, 2, 3]
- Kết quả: Số nhỏ nhất (1) "nổi" lên vị trí đầu tiên
Vòng lặp thứ hai (xét vị trí thứ hai):
- So sánh 3 và 2 → 3 > 2 → KHÔNG hoán đổi
- So sánh 2 và 4 → 2 < 4 → hoán đổi → [1, 2, 4, 3]
- Kết quả: Số nhỏ thứ hai (2) "nổi" lên vị trí thứ hai
Vòng lặp thứ ba (xét vị trí thứ ba):
- So sánh 3 và 4 → 3 < 4 → hoán đổi → [1, 2, 3, 4]
- Kết quả: Dãy đã được sắp xếp xong
Đầu ra: 1, 2, 3, 4
🎯 Ghi nhớ: - Thuật toán sắp xếp nổi bọt hoạt động bằng cách so sánh từng cặp phần tử cạnh nhau và hoán đổi nếu chúng sai thứ tự. - Phần tử nhỏ sẽ dần "nổi" lên đầu dãy (giống bọt khí nổi lên mặt nước) → đó là lý do có tên "sắp xếp nổi bọt". - Để hoán đổi 2 giá trị, ta cần dùng biến trung gian.