Giáo án tin học 7 chân trời sáng tạo bài 14: thuật toán sắp xếp (tiết 2)

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

* Hoạt động 1: Đọc (và quan sát)

Nhiệm vụ: Mô phỏng thuật toán sắp xếp chọn (áp dụng để sắp xếp dãy thẻ số ở Hình 6 theo thứ tự tăng dần)

- GV yêu cầu HS hoạt động cá nhóm, quan sát Hình 6 – 10 và các hình liên quan, đọc nội dung mục 2. Thuật toán sắp xếp chọn SGK tr.79 – 82.

- GV yêu cầu HS lên bảng thực hiện sắp xếp dãy thẻ ở Hình 6 SGK tr.79 (được ghim trên bảng) theo cách được mô phỏng ở Hình 7 – 10  (HS tự gợi nhớ, không xem SGK); mỗi HS thực hiện 1 vòng lặp; kết quả sau mỗi vòng được thay bởi thẻ số tương ứng nhưng khác nhau.

- GV đặt câu hỏi: Từ nội dung mục 2. Thuật toán sắp xếp chọn và hoạt động thực hành sắp xếp, em hãy mô tả các bước thuật toán sắp xếp chọn.

- GV cho HS thảo luận nhóm và trả lời câu hỏi:

+ Em có nhận xét gì về số bước thực hiện ở mỗi vòng lặp của hai thuật toán sắp xếp vừa học (nhất là trong trường hợp số phần tử của dãy cần sắp xếp đủ lớn)? Vì sao?

à Gợi ý: Ở mỗi vòng lặp, do đã xác định được số nhỏ nhất của dãy chưa sắp xếp nên công việc chỉ là so sánh và quyết định đổi chỗ số nhỏ nhất lên vị trí đầu tiên.

+ Thuật toán này có thực hiện chia một bài toán thành những bài toán nhỏ hơn không? Vì sao?

à Gợi ý: GV hướng dẫn HS để thấy được, ngoài việc chia bài toán thành những bài toán tương tự có kích thước nhỏ hơn như ở thuật toán sắp xếp nổi bọt, thuật toán còn sử dụng một bài toán nhỏ độc lập ở mỗi vòng lặp, đó là bài toán Tìm số nhỏ nhất,

- GV lưu ý cho HS: Có thể sử dụng các đồ dùng, thiết bị dạy học khác như đã hướng dẫn ở trên để triển khai các phương án dạy và học phù hợp.

* Hoạt động 2: Làm

- GV cho HS nghiên cứu kiến thức vừa học và thực hiện nhiệm vụ của Hoạt động làm SGK tr.82:

+ GV tổ chức cho HS làm việc theo nhóm, thảo luận mô tả thuật toán, lập mô phỏng thuật toán sắp xếp chọn để sắp xếp 5 chữ cái ở Hình 5 SGK tr.79.

+ GV ghim các thẻ ở Hình 5 SGK tr.79 theo hàng ngang và ghi số thứ tự từ trái qua phải (sau khi HS đã làm việc dưới lớp) để HS lên bảng trình bày.

1. Em hãy sắp xếp dãy chữ cái ở Hình 5 theo hàng ngang rồi sử dụng thuật toán sắp xếp chọn (mô phỏng quá trình thực hiện bằng hình vẽ như các Hình 7, Hình 8, Hình 9) thực hiện sắp xếp dãy theo thứ tự tăng dần.

+ GV cho HS thảo luận, chọn phương án đúng:

2. Thuật toán sắp xếp chọn thực hiện sắp xếp dãy số không giảm bằng cách nào dưới đây?

A. Đổi chỗ 2 số liền kề nhau nếu chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp.

B. Lặp lại quá trình chọn số nhỏ nhất trong dãy chưa sắp xếp và đưa số này về vị trí đầu tiên của dãy đó.

* Hoạt động 3: Ghi nhớ - SGK tr.82

- GV gọi HS đọc nội dung Ghi nhớ SGK tr.82:

Bước 2: HS thực hiện nhiệm vụ học tập

- HS hoạt động cá nhóm, quan sát Hình 6 – 10 và các hình liên quan, đọc nội dung mục 2. Thuật toán sắp xếp chọn SGK tr.79 – 82.

- HS thực hiện sắp xếp dãy thẻ ở Hình 6 SGK tr.79.

- HS mô phỏng các bước của thuật toán sắp xếp chọn.

- HS nghiên cứu kiến thức vừa học và thực hiện nhiệm vụ của Hoạt động làm SGK tr.82.

- HS đọc nội dung Ghi nhớ SGK tr.82.

- GV hướng dẫn, theo dõi, hỗ trợ HS nếu cần thiết.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời HS lên bảng thực hiện sắp xếp dãy thẻ ở Hình 6 SGK tr.79.

- GV cho HS mô phỏng các bước của thuật toán sắp xếp chọn.

- GV lưu ý cho HS.

- GV mời HS thực hiện nhiệm vụ của Hoạt động làm SGK tr.82.

- GV mời HS đọc nội dung Ghi nhớ SGK tr.82.

- GV mời đại diện HS khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV đánh giá, nhận xét, chuẩn kiến thức.

- GV chuyển sang nội dung mới.

2. Thuật toán sắp xếp chọn

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

+ Thực hiện chọn phần tử nhỏ nhất trong dãy chưa được sắp xếp và đưa phần tử này về vị trí đầu tiên của dãy chưa được sắp xếp.

+ Lặp lại quá trình này cho đến khi dãy chưa sắp xếp chỉ còn một phần tử.

* Hoạt động 1: Đọc (và quan sát)

Mô phỏng thuật toán sắp xếp chọn (áp dụng để sắp xếp dãy thẻ số ở Hình 6 theo thứ tự tăng dần)

- Đầu vào: Dãy thẻ ghi các số xếp từ trái qua phải là 20, 21, 17, 19.

- Đầu ra: Dãy thẻ ghi các số được sắp xếp tăng dần là 17, 19, 20, 21.

à Lưu ý: Để tìm số nhỏ nhất trong dãy số, ví dụ: dãy 20, 21, 17, 19 ta thực hiện như sau:

+ Bước 1. Coi số đầu tiên của dãy số (vị trí 1) là số nhỏ nhất (MIN).

+ Bước 2. So sánh MIN với số thứ 2.

+ Bước 3. So sánh MIN với số thứ 3.

+ Bước 4. So sánh MIN với số thứ 4.

+ Sau bước 4. dãy số đã được duyệt xong, ta có MIN = 17, vị trí là 3. Do vậy số nhỏ nhất là 17, là số thứ 3 trong dãy số.

à Với thuật toán sắp xếp chọn, bài toán sắp xếp dãy số ban đầu cũng được chia thành những bài toán nhỏ để giải quyết. Các bài toán nhỏ là di chuyển số nhỏ nhất (hoặc lớn nhất) về vị trí đầu tiên của dãy chưa sắp xếp. Phạm vi của dãy chưa sắp xếp hẹp dần sau mỗi lần lặp.

* Hoạt động 2: Làm

1. HS thực hành sắp xếp.

2. B. Lặp lại quá trình chọn số nhỏ nhất trong dãy chưa sắp xếp và đưa số này về vị trí đầu tiên của dãy đó.

* Hoạt động 3: Ghi nhớ - SGK tr.82