Giáo án điện tử tin học 7 kết nối bài 16: Thuật toán sắp xếp

CHÀO MỪNG CẢ LỚP ĐẾN VỚI TIẾT HỌC

BÀI 16: THUẬT TOÁN SẮP XẾP

NỘI DUNG BÀI HỌC

KHỞI ĐỘNG

KHÁM PHÁ

LUYỆN TẬP

VẬN DỤNG

1. KHỞI ĐỘNG

                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. 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ì.

CÁCH THỰC HIỆN HOÁN ĐỔI CHẤT LỎNG Ở HAI CỐC A, B

• Đầu vào: A đựng chất lỏng màu xanh, B đựng chất lỏng màu đỏ.
• Bước thực hiện:

                Đổ chất lỏng màu xanh từ cốc A sang cốc C.

                Đổ chất lỏng màu đỏ từ cốc B sang cốc A.

                Đổ chất lỏng màu xanh từ cốc C sang cốc B.

• Đầu ra: A đựng chất lỏng màu đỏ, B đựng chất lỏng màu xanh.

2. KHÁM PHÁ

                HOẠT ĐỘNG NHÓM

Em hãy diễn giải hoạt động của thuật toán sắp xếp nổi bọt với bốn giá trị qua hình 16.2 – 16.4.

Em hãy trình bày các bước mô tả thuật toán sắp xếp nổi bọt bằng ngôn ngữ tự nhiên.

Sắp xếp dãy số theo thứ tự tăng dần bằng thuật toán sắp xếp nổi bọt.

Bước 1. Với vị trí đầu tiên, em thực hiện một vòng lặp như sau:

• So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí đầu tiên.
• Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau.
• Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ nhất nổi lên vị trí đầu tiên.
• - Bước 2. Với vị trí thứ hai, em thực hiện một vòng lặp tương tự như trên.
• - Bước 3. Tương tư như trên các vị trí thứ ba, thứ tư,… đến vị trí trước vị trí cuối cùng.
• - Bước 4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn.
• Hoạt động 1. Mô phỏng thuật toán sắp xếp nổi bọt
• 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 lặp sắp xếp bằng hình vẽ minh họa tương tự như hình 16.2, 16.3, 16.4.

Em hãy diễn giải hoạt động của thuật toán sắp xếp chọn trên cơ sở mô phỏng vòng lặp thứ nhất qua hình 16.5.

Mô tả thuật toán sắp xếp chọn bằng ngôn ngữ tự nhiên SGK tr.81  và thực hiện nhiệm vụ: Em hãy trình bày các bước mô tả thuật toán sắp xếp chọn bằng ngôn ngữ tự nhiên.

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.

KẾT LUẬN

Thuật toán sắp xếp chọn theo từng vị trí từ đầu đến cuối dãy, so sánh trực tiếp phần từ ở vị trí được xét với những phân tử ở phía sau nó và hoán đổi nếu chúng chưa đúng vị trí.

Chia bài toán thành những bài toán nhỏ hơn SGK tr.82 và trả lời câu hỏi:

Em hãy diễn giải và nêu ý nghĩa của việc chia bài toán thành những bài toán nhỏ hơn ở thuật toán sắp xếp và thuật toán tìm kiếm nhị phân.