Sử dụng List (danh sách) trong Scratch – Phần 7
Nội dung bài học ngày hôm nay sẽ khó và nâng cao hơn so với những bài trước, để chuẩn bị thật tốt thì các em hãy ôn tập thật kỹ những kiến thức và những bài tập các em đã học nhé (Phần 1, Phần 2, Phần 3, Phần 4, Phần 5 và Phần 6).
Dạng bài
Sắp xếp danh sách theo chiều tăng dần.
Đề bài
Em hãy nhập vào một dãy số trong Scratch. Lập trình để sắp xếp dãy số vừa nhập theo chiều tăng dần. Hiển thị kết quả ra màn hình.
Phân tích bài toán
Đầu vào (Input)
- Đề bài yêu cầu nhập dữ liệu cho dãy số và sắp xếp dãy số vừa nhập theo chiều tăng dần.
- Dãy số được sắp xếp theo chiều tăng dần là dãy số mà số sau lớn hơn các số đứng trước nó.
- Ví dụ giả sử dãy số là: 6, 10, 1, 7, 4.
Đầu ra (Output)
- Hiển thị ra màn hình dãy số sau khi được sắp xếp tăng dần.
- Ví dụ cho dãy số trên là: 1, 4, 6, 7, 10.
Các bước thực hiện
Các nhà khoa học đã xây dựng ra nhiều giải thuật sắp xếp khác nhau, tuy nhiên để các em dễ nắm bắt và hình dung hơn thì thầy hướng dẫn các em tiếp cận đến giải thuật sắp xếp chọn (thuật ngữ tiếng anh là Selection Sort). Ý tưởng của giải thuật sắp xếp này như sau:
Giả sử ta có dãy số: a[1], a[2], a[3], …, a[n]. Trong đó, a[1] là giá trị phần tử tại vị trí 1, a[2] là giá trị phần tử tại vị trí 2, …, a[n] là giá trị phần tử tại vị trí n, với n là số lượng phần tử.
- Giai đoạn 1: Trong các số từ a[1] đến a[n]
- Tìm số có giá trị nhỏ nhất.
- Đổi chỗ số nhỏ nhất vừa tìm với số đầu tiên a[1].
- Giai đoạn 2: Trong các số từ a[2] đến a[n] (dãy số này là dãy số sau cùng khi kết thúc giai đoạn 1)
- Tìm số có giá trị nhỏ nhất.
- Đổi chỗ số nhỏ nhất vừa tìm với số đầu tiên trong a[2] đến a[n] là a[2].
- …
- Giai đoạn (n – 1): Dãy số còn lại duy nhất một phần tử chưa được sắp xếp, phần tử đó là phần tử lớn nhất trong dãy, ta dừng thuật toán ở đây.
Chương trình tham khảo
Giải thuật sắp xếp chọn – Selection sort
Source code chương trình
Bài tập
Nhập vào một dãy số từ bàn phím …
Bài 1: Tìm phần tử có giá trị nhỏ nhất trong dãy. Phần tử đó nằm ở vị trị nào.
Bài 2: Tìm phần tử có giá trị lớn thứ hai trong dãy.
Bài 3: Sắp xếp dãy số theo chiều giảm dần.
Bài 4: Kiểm tra phần tử có giá trị bằng 10 thuộc dãy số hay không?
Bài 5: Loại bỏ các phần chẵn trong dãy.
