Bài toán sắp xếp chọn diễn ra như thế nào? Khi thực hiện bài toán ta cần xác định rõ các yếu tố nào? Để trả lời các câu hỏi này các em hãy tham khỏa nội dung bài giảng của Bài 3: Sắp xếp chọn trong chủ đề F của chương trình Tin học 7 Cánh diều do DapAnHay tổng hợp và biên soạn dưới đây!
- 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:
Minh họa ý tưởng sắp xếp bằng cách chọn dần
- Giải thích:
+ Bước 1. Số lớn nhất trong dãy số (94) cần được chuyển về vị trí thứ nhất trong dãy, do đó đổi chỗ 94 và 55, dãy còn lại là: 19, 42, 55, 18, 67.
+ Bước 2. Số lớn nhất trong dãy là 67 chuyển về đầu dãy này, do đó đổi chỗ 67 với 19, dãy còn lại chưa được sắp xếp là 42, 55, 18, 19.
+ Tiếp tục lặp lại việc “Chọn số lớn nhất và đổi chỗ cho nói với số đứng đầu dãy”, cho đến khi hết dãy ban đầu.
- Minh họa:
+ Lượt 1. Xét a1; Tìm số lớn nhất trong dãy a1 đến a6 rồi đổi chỗ với a1.
+ Lượt 2. Xét a2; Tìm số lớn nhất trong dãy a2 đến a6 rồi đổi chỗ với a2.
+ Lượt 3. Xét a3; Tìm số lớn nhất trong dãy a3 đến a6 rồi đổi chỗ với a3.
+ Lượt 4. Xét a4; Tìm số lớn nhất trong dãy a4 đến a6 rồi đổi chỗ với a4.
+ Lượt 5. Xét a5; Tìm số lớn nhất trong dãy a5 đến a6 rồi đổi chỗ với a5.
+ Lượt 6. Xét a6; Đã xét xong dãy
→ Ta thu được dãy sắp xếp theo chiều giảm dần
Bài toán sắp xếp đặt ra như sau:
- Đầu vào: Dãy số a1, a2, …, an gọi là dãy (a).
- Đầu ra: Dãy số gồm các dãy số (a) những thứ tự giảm dần.
Thuật toán gồm một vòng lặp n – 1 lần, mỗi lần lặp nhằm đưa số của dãy vào đúng vị trí mong muốn.
Lặp với i từ 1 đến n – 1:
a) Tìm số lớn nhất trong dãy số ai, ai+1, …, an gọi là am
b) Đổi chỗ am và ai cho nhau
Hết lặp
Trong các bước trên có yêu cầu tìm số lớn nhất 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.
Minh họa cách tìm số lớn nhất trong dãy số
- Bước 2. So sánh a2 với số lớn nhất, nếu a2 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 an với số lớn nhất và ghi nhận lại vị trí của số lớn nhất thì số lớn nhất chính là số lớn nhất trong toàn bộ dãy và tìm được vị trí m của số lớn nhất trong dãy.
Sắp xếp là bài toán cơ sở trong 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?
Ví dụ: Sắp xếp danh sách kết quả điểm kiểm tra môn Tin học theo thứ tự từ cao xuống thấp là bài toán sắp xếp. Tiêu chí là điểm kiểm tra theo thứ tự giảm dần.
- Bài toán sắp xếp có mô hình chung là: Đổi chỗ các phân tử trong dãy để dãy có thứ tự tăng dần (không giảm) hoặc giảm dần (không tăng). - Sắp xếp chọn dần là một thuật toán mô phỏng cách sắp xếp: 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 đó. |
---|
Bài tập 1: Sắp xếp chọn dần là gì?
Hướng dẫn giải:
Sắp xếp chọn dần là: 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 đó.
Bài tập 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ử nào?
Hướng dẫn giải:
Số lớn nhất trong dãy số (80) cần đươc chuyền về vị trí thứ nhất trong dãy, do đó đổi chỗ 80 với 11.
Bài tập 3: Khi phát biểu bài toán sắp xếp cần xác định rõ các yếu tố nào?
Hướng dẫn giải:
Khi phát biểu bài toán sắp xếp 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?
Qua bài học các em có thể:
- Biết được bài toán sắp xếp là gì?
- Biết được ý tưởng sắp xếp chọn
- Mô phỏng được hoạt động của thuật toán sắp xếp chọn bằng các bước thủ công trên một bộ dữ liệu có kích thước nhỏ
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 Cánh diều Chủ đề F Bài 3 cực hay có đáp án và lời giải chi tiết.
Sắp xếp chọn dần là gì?
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ử nào?
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ố nào?
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 Cánh diều Chủ đề F Bài 3để 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 84 SGK Tin học 7 Cánh diều - CD
Hoạt động trang 85 SGK Tin học 7 Cánh diều - CD
Luyện tập trang 86 SGK Tin học 7 Cánh diều - CD
Vận dụng trang 86 SGK Tin học 7 Cánh diều - CD
Câu hỏi tự kiểm tra 1 trang 86 SGK Tin học 7 Cánh diều - CD
Câu hỏi tự kiểm tra 2 trang 86 SGK Tin học 7 Cánh diều - CD
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
Sắp xếp chọn dần là gì?
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ử nào?
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ố nào?
Cho dãy số 3, 5, 2, 8, 9. Sắp xếp dãy theo chiều giảm dần bằng cách chọn dần gồm một vòng lặp có số lần lặp là bao nhiêu?
Để tìm vị trí số lớn nhất của dãy 3, 7, 9, 2 ta có bao nhiêu bước so sánh?
Bài toán sắp xếp cần xác định rõ những gì?
Khi dùng thuật toán sắp xếp chọn để sắp dãy theo thứ tự giảm dần khi nào không cần thực hiện thao tác “Đôi chỗ am cho aiˆ mà kết quả sắp xếp vẫn đúng?
Thế nào là sắp xếp chọn?
Bài toán sắp xếp có mô hình chung là gì?
Nhận định nào đúng về sắp xếp chọn?
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?
Bài toán sắp xếp ở mục 1 trên đây 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?
Bài toán khởi động | Bài toán mục 1 |
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. | Giả sử 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. |
Trình bày diễn biến từng bước của thuật toán sắp xếp chọn cho dãy số 11, 70, 18, 39, 63, 52, 41, 5 theo mẫu ở Hình 1.
Trong thuật toán sắp xếp chọn:
1) Khi nào không cần thực hiện thao tác "Đổi chỗ am và a1 cho nhau" mà kết quả sắp xếp vẫn đúng?
2) Nếu thay "Tìm giá trị lớn nhất" bằng "Tìm giá trị nhỏ nhất" thì kết quả nhận được là dãy số có thứ tự ra sao?
Hãy nêu vài ví dụ bài toán sắp xếp trong thực tế và nói rõ tiêu chi sắp xếp?
Hãy tóm tắt bằng một câu trả lời cho câu hỏi: Thế nào là sắp xếp chọn?
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 *