DapAnHay xin giới thiệu đến các em nội dung Bài 14: Thuật toán sắp xếp trong chủ đề 5 của chương trình Tin học 7 Chân trời sáng tạo sẽ giúp các em tìm hiểu các kiến thức về thuật toán sắp xếp nổi bọt và sắp xếp chọn. Mời các em cùng tham khảo!
Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy phần tử (tăng dần hay giảm dần) bằng cách thực hiện lặp đi lặp lại việc đổi chỗ 2 phần tử liền kề nếu chúng sai thứ tự. |
---|
* Bài toán:
Có 4 tấm thẻ, mỗi thẻ ghi một số và xếp thành một dãy dọc trên mặt bàn từ trên xuống dưới như Hình 1. Em hãy trao đổi với bạn để chỉ ra cách sắp xếp dãy thẻ theo thứ tự giá trị tăng dần của số ghi trên thẻ, với điều kiện chỉ có thể di chuyển các thẻ bằng cách đổi chỗ các cặp thẻ liền kề.
Các thẻ được ghi số và xếp theo dãy dọc
* Mô tả thuật toán sắp xếp nổi bọt (áp dụng cho bài toán sắp xếp dãy tổng quát)
- Đầu vào: Dãy chưa được sắp xếp.
- Đầu ra: Dãy được sắp xếp không giảm.
Bước 1. Chuyển phần tử nhỏ nhất về vị trí đầu tiên.
+ So sánh từng phần tử của dãy với phần tử liền trước, lần lượt từ phần tử cuối cùng lên phần tử đầu tiên.
+ Nếu nhỏ hơn thì đổi chỗ hai phần tử.
+ Kết thúc vòng lặp, phần từ nhỏ nhất "nổi lên" vị trí đầu tiên của dãy.
Bước 2. Chuyển phần tử nhỏ thứ hai về vị trí thứ hai.
+ So sánh từng phần tử của dãy với phần tử liền trước, lần lượt từ phần tử cuối cùng lên phần tử thứ hai.
+ Nếu nhỏ hơn thì đổi chỗ hai phần tử.
+ Kết thúc vòng, phần tử nhỏ thứ hai "nổi lên" vị trí thứ hai của dãy.
Bước 3. Thực hiện tương tự như trên với phần tử nhỏ thứ ba, thứ tư, ... cho đến phần tử liền trước phần tử cuối cùng.
Bước 4. Kết thúc thuật toán, ta sẽ nhận được dãy số đã được sắp xếp theo thứ tự tăng dần.
Thuật toán sắp xếp chọn thực hiện lặp lại quá trình chọn phần tử nhỏ nhất trong dãy chưa sắp xếp và đưa phần tử này về vị trí đầu tiên của dãy đó. |
---|
* Ví dụ:
- Đầ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.
Dãy số thẻ chưa sắp xếp
* Mô tả thuật toán:
Minh họa thuật toán sắp xếp nổi bọt
Bài tập 1: Bài toán: Em hãy thực hiện sắp xếp các bạn trong tổ em theo thứ tự chiều cao không giảm. Với bài toán này em có thể sử dụng thuật toán sắp xếp nào?
Hướng dẫn giải:
Bài toán sắp xếp các bạn trong tổ em theo thứ tự chiều cao không giảm có thể sử dụng thuật toán sắp xếp nổi bọt hoặc chọn.
Bài tập 2: Cho dãy số xếp từ trái qua phải là; 20, 21, 17, 19. Cho biết với thuật toán sắp xếp chọn thì kết quả sau vòng lặp 1 là bao nhiêu?
Hướng dẫn giải:
Kết quả sau vòng lặp 1. Dãy được sắp xếp là: 17, 21, 20, 19.
Bài tập 3: 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?
Hướng dẫn giải:
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: 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.
Qua bài học các em có thể:
- Giải thích được thuật toán sắp xếp nổi bọt, sắp xếp chọn.
- Biểu diễn và mô phỏng được thuật toán sắp xếp trên bộ dữ liệu đầu vào có kích thước nhỏ.
- Nêu được ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn.
Các em có thể hệ thống lại nội dung kiến thức đã học được thông qua bài kiểm tra Trắc nghiệm Tin học 7 Chân trời sáng tạo Chủ đề 5 Bài 14 cực hay có đáp án và lời giải chi tiết.
Chỉ ra phương án sai? Ý nghĩa của việc chia bài toán thành bài toán nhỏ hơn là gì?
Đặc điểm của thuật toán sắp xếp nỗi bọt là gì?
Đặc điểm của thuật toán sắp xếp chọn là gì?
Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!
Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 7 Chân trời sáng tạo Chủ đề 5 Bài 14để giúp các em nắm vững bài học và các phương pháp giải bài tập.
Khởi động trang 76 SGK Tin học 7 Chân trời sáng tạo - CTST
Khám phá 1 trang 79 SGK Tin học 7 Chân trời sáng tạo - CTST
Khám phá 2 trang 79 SGK Tin học 7 Chân trời sáng tạo - CTST
Khám phá 1 trang 82 SGK Tin học 7 Chân trời sáng tạo - CTST
Khám phá 2 trang 82 SGK Tin học 7 Chân trời sáng tạo - CTST
Luyện tập 1 trang 82 SGK Tin học 7 Chân trời sáng tạo - CTST
Luyện tập 2 trang 82 SGK Tin học 7 Chân trời sáng tạo - CTST
Vận dụng trang 82 SGK Tin học 7 Chân trời sáng tạo - CTST
Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học DapAnHay sẽ hỗ trợ cho các em một cách nhanh chóng!
Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!
-- Mod Tin Học 7 DapAnHay
Chỉ ra phương án sai? Ý nghĩa của việc chia bài toán thành bài toán nhỏ hơn là gì?
Đặc điểm của thuật toán sắp xếp nổi bọt là gì?
Đặc điểm của thuật toán sắp xếp chọn là gì?
Cho dãy số xếp từ trái qua phải là: 20, 21, 17, 19. Cho biết với thuật toán sắp xếp chọn ở vòng lặp số 2 thì số nhỏ nhất được tìm thấy là số nào?
Cho dãy số xếp từ trái qua phải là: 20, 21, 17, 19. Cho biết với thuật toán sắp xếp chọn thì kết quả sau vòng lặp 1 là:
Định nghĩa sau là của thuật toán sắp xếp nào? “Thuật toán thực hiện lặp đi lặp lại việc đổi chỗ 2 số liền kề trong một dãy số nếu chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp"
Sau khi thực hiện vòng lặp thứ nhất của thuật toán sắp xếp nổi bọt cho dãy số sau theo thứ tự tăng dần ta thu được dãy số nào? Dãy số ban đầu: 19, 16, 18, 15
Dãy số sau thực hiện mấy vòng lặp khi thực hiện sắp xếp nổi bọt để sắp xếp dãy theo thứ tự tăng dần? Dãy ban đầu: 13, 14, 8, 9,4, 5
Phát biểu nào không đúng khi nói về thuật toán sắp xếp chọn?
Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy số không giảm bằng cách nào dưới đây?
Có 4 tấm thẻ, mỗi thẻ ghi một số và xếp thành một dãy dọc trên mặt bàn từ trên xuống dưới như Hình 1.
Em hãy trao đổi với bạn để chỉ ra cách sắp xếp dãy thẻ theo thứ tự giá trị tăng dần của số ghi trên thẻ, với điều kiện chỉ có thể di chuyển các thẻ bằng cách đổi chỗ các cặp thẻ liền kề.
Hình 1. Các thẻ được ghi số và xếp theo dãy dọc
Em hãy sắp xếp dãy chữ cái ở Hình 5 theo thứ tự tăng dần bằng thuật toán sắp xếp nổi bọt (mô phỏng quá trình thực hiện bằng hình vẽ tương tự như các Hình 2, 3, 4). Quy ước, trong bảng chữ cái, chữ đứng trước "nhỏ hơn" chữ đứng sau.
Thuật toán sắp xếp nổi bọt 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. Di chuyển số nhỏ nhất về cuối danh sách.
C. Di chuyển số lớn nhất về đầu danh sách.
Em hãy 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.
Thuật toán sắp xếp chọn thực hiện sắp xếp dãy số tăng dần 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 đó.
Liệt kê các vòng lặp của thuật toán sắp xếp nổi bọt, thuật toán sắp xếp chọn để sắp xếp các dãy sau theo thứ tự tăng dần:
a) Dãy số: 9, 6, 11, 3, 7.
b) Dãy chữ cái: H, D, A, B, Y.
Chỉ ra phương án sai. Ý nghĩa của việc chia bài toán thành bài toán nhỏ hơn là:
A. Giúp công việc đơn giản hơn.
B. Giúp công việc dễ giải quyết hơn.
C. Làm cho công việc trở nên phức tạp hơn.
D. Giúp bài toán trở nên dễ hiểu hơn.
Sử dụng một thuật toán đã học để thực hiện sắp xếp các bạn trong tổ em theo thứ tự chiều cao không giảm (ghi chiều cao của các bạn theo cùng đơn vị đo là cm vào bảng theo mẫu Bảng 1 dưới đây).
Họ và tên
Tiêu đề câu hỏi
Nội dung câu hỏi
0 Bình luận
Để lại bình luận
Địa chỉ email của hạn sẽ không được công bố. Các trường bắt buộc được đánh dấu *