Giáo án và PPT Tin học 7 cánh diều Bài 3: Sắp xếp chọn

BÀI 3: SẮP XẾP CHỌN

HOẠT ĐỘNG KHỞI ĐỘNG

GV yêu cầu HS đọc tình huống mở đầu và trả lời câu hỏi:

Có một bó que tính dài ngắn khác nhau, em hãy xếp các que tính thành dãy từ trái sang phải theo thứ tự ngắn dần

HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Tìm hiểu ý tưởng sắp xếp bằng cách chọn dần

- Ví dụ: Cần đổi chỗ các số hạng trong dãy số 55, 19, 42, 94, 18, 67 để tạo ra được dãy có thứ tự giảm dần

- Minh họa ý tưởng

- Giải thích:

          + Bước 1. Số lớn nhất trong dãy (94) cần được chuyển về vị trí thứ 1 trong dãy => đổi chỗ 94 và a₁

                + Bước 2. Số lớn nhất trong dãy còn lại (67) cần được chuyển về vị trí thứ 1 trong dãy còn lại => đổi chỗ 67 và a₂.

          + Tiếp tục lặp lại việc “Chọn lấy số lớn nhất trong dãy số còn lại và đổi chỗ nó với số đứng đầu dãy này” cho đến khi hết dãy ban đầu.

Hoạt động 2. Thực hành định dạng trang tính

Giáo viên đưa ra cí dụ về câu chuyện bó đũa, học sinh thảo luận nhóm và trả lời câu hỏi: “Bài toán sắp xếp ở hoạt động 1 có gì giống và khác với bài toán sắp xếp nêu ở phần khởi động? Ý tưởng sắp xếp ở mục 1 có gì giống và khác với ý tưởng sắp xếp em đã sử dụng ở phân khởi động?”

Sản phẩm dự kiến:

- Đầu vào: Dãy số a₁, a₂, …, a_n gọi là dãy (a)

- Đầu ra: Dãy số a’₁, a’₂, …, a’_n gồm các số của dãy (a) nhưng thứ tự giảm dần

- Thuật toán sắp xếp chọn:

- Trong các bước trên có yêu cầu tìm số lớn nhất (kí hiệu là a_m) trong dãy số cho trước (a)

=> Các bước để tìm được số lớn nhất của một dãy số nằm ở vị trí nào

          + Bước 1. Tạm ghi nhận vị trí của số lớn nhất là 1 

          + Bước 2. So sánh a₂ với số lớn nhất, nếu a₂ lớn hơn số lớn nhất thì ghi nhận lại vị trí số lớn nhất là 2.

          + Cứ tiếp tục như vậy, đến khi so sánh xong a_n với số lớn nhất và ghi nhận lại vị trí của số lớn nhất (nếu cần) thì số lớn nhất chính là số lớn nhất trong toàn bộ dãy và ta đã tìm được vị trí m của số lớn nhất trong dãy

Hoạt động 3. Tìm hiểu bài toán sắp xếp 

- Sắp xếp là bài toán cơ sở của tin học. Duy trì dữ liệu được sắp xếp đúng thứ tự sẽ làm giảm đáng kể thời gian tìm kiếm dữ liệu

- Khi phát biểu bài toán cần xác định rõ:

          + Dãy đầu vào: Sắp xếp những gì?

          + Tiêu chí: Sắp xếp theo cái gì? Thứ tự tăng dần hay giảm dần?

- Thực tế, khi sắp xếp thủ công (không dùng máy tính), thuật toán sắp xếp chọn thường được dùng.

HOẠT ĐỘNG LUYỆN TẬP

Từ nội dung bài học, GV yêu cầu HS hoàn thành các bài tập trắc nghiệm sau:

Câu 1: Sắp xếp chọn dần là:

A. Chọn ra những phần tử chưa sắp xếp còn lại và xếp vào đầu dãy đó.

B.Chọn phần tử lớn nhất trong dãy chưa sắp xếp còn lại và xếp vào đầu dãy đó.

C. Chọn ra các phần tử dương.

D. Chọn ra các phần tử âm.

Câu 2: Trong bài toán sắp xếp giảm dần dãy số 11, 70, 20, 39, 80, 52, 41, 5. Ở bước đầu tiên của sắp xếp chọn ta cần đổi chỗ phần tử 80 cho phần tử:

A. 11

B. 70

C. 5

D. 39

Câu 3: Trong mỗi bước của thuật toán sắp xếp chọn theo thứ tự giảm dần ta cần tìm:

A. Phần tử âm lớn nhất.

B. Phần tử nhỏ nhất.

C. Phần tử lớn nhất.

D. Phần tử bằng 0.

Câu 4: Trong mỗi bước của thuật toán sắp xếp chọn theo thứ tự tăng dần ta cần tìm:

A. Phần tử âm lớn nhất.

B. Phần tử nhỏ nhất

C. Phần tử lớn nhất.

D. Phần tử bằng 0.

Câu 5: Cho dãy số 2,5,4,9,3,7. Sắp xếp dãy số theo thứ tự giảm dần theo cách chọn dần thì sau bước thứ nhất ta được dãy số:

A. 9,5,4,2,3,7

B. 9,7,5,4,3,2

C. 9,5,4,2,3,7

D. 2,5,4,9,3,7

 Sản phẩm dự kiến:

HOẠT ĐỘNG VẬN DỤNG

Vận dụng kiến thức, GV yêu cầu HS trả lời câu hỏi:

Câu 1: Trong thuật toán sắp xếp chọn, khi nào không cần thực hiện thao tác “Đổi chỗa_m cho a_i” mà kết quả sắp xếp vẫn đúng?