Dạng bài ứng dụng list – danh sách (phần 2)

Dạng bài danh sách trong kỳ thi tin học trẻ bằng Scratch 3.0 là một phần rất quan trọng. Bài viết này sẽ tiếp tục hướng dẫn các bạn giải các dạng bài tập về dãy số, bao gồm tìm số lớn nhất, nhỏ nhất, sắp xếp dãy số tăng dần và giảm dần bằng thuật toán nổi bọt.

Dạng 2: Cho dãy số ngẫu nhiên. Yêu cầu tìm số lớn nhất, nhỏ nhất hoặc sắp xếp dãy số theo thứ tự tăng dần hoặc giảm dần.

Bài 6: Tìm số lớn nhất trong dãy

Để tìm số lớn nhất trong dãy số, ta thực hiện các bước sau:

• Tạo biến max để lưu giá trị của số lớn nhất.
• Ban đầu, giả sử phần tử đầu tiên trong dãy có giá trị lớn nhất và đặt giá trị của max là giá trị của phần tử đầu tiên trong dãy.
• So sánh phần tử tiếp theo trong dãy với max. Nếu phần tử đó lớn hơn max, thì đặt giá trị của max là giá trị của phần tử đó. Việc so sánh này được thực hiện từ phần tử thứ 2 trong dãy cho đến hết.
• Khi duyệt hết tất cả phần tử trong dãy, giá trị của max chính là giá trị lớn nhất của dãy số.

Hình ảnh minh họa tìm số lớn nhất trong dãy

Link project mẫu: https://scratch.mit.edu/projects/405441241/

Bài 7: Tìm số nhỏ nhất trong dãy

Quy trình giải bài 7 tương tự như bài 6. Ta thực hiện các bước sau:

• Tạo biến min để lưu giá trị của số nhỏ nhất.
• Ban đầu, giả sử phần tử đầu tiên trong dãy có giá trị nhỏ nhất và đặt giá trị của min là giá trị của phần tử đầu tiên trong dãy.
• So sánh phần tử tiếp theo trong dãy với min. Nếu phần tử đó nhỏ hơn min, thì đặt giá trị của min là giá trị của phần tử đó. Việc so sánh này được thực hiện từ phần tử thứ 2 trong dãy cho đến hết.
• Khi duyệt hết tất cả phần tử trong dãy, giá trị của min chính là giá trị nhỏ nhất của dãy số.

Link project mẫu: https://scratch.mit.edu/projects/405441241/

Bài 8: Sắp xếp dãy số theo thứ tự tăng dần

Có rất nhiều thuật toán để sắp xếp dãy số. Trong bài viết này, chúng ta sẽ giới thiệu thuật toán sắp xếp nổi bọt (Bubble Sort), một thuật toán đơn giản để sắp xếp dãy số theo thứ tự tăng dần.

Thuật toán sắp xếp nổi bọt là kiểu so sánh bắt cặp tất cả các phần tử trong dãy cần sắp xếp và đổi chỗ hai phần tử trong cặp nếu chúng không thỏa điều kiện thứ tự.

Ví dụ, để sắp xếp dãy số [5, 3, 8, 4, 6] theo thứ tự tăng dần, ta thực hiện các bước sau:

Dãy ban đầu [5, 3, 8, 4, 6] gồm 5 phần tử nên độ dài dãy cần sắp xếp là 5.

• Bắt cặp 5 và 3 với nhau. Vì 3 bé hơn nên ta đổi chỗ 2 số này. Dãy mới là [3, 5, 8, 4, 6].
• Tiếp theo, bắt cặp 5 với 8. Vì 5 bé hơn nên ta không làm gì.
• Tiếp theo, bắt cặp 8 với 4. Vì 4 bé hơn nên ta đổi chỗ 2 số này. Dãy mới là [3, 5, 4, 8, 6].
• Tiếp theo, bắt cặp 8 với 6. Vì 6 bé hơn nên ta đổi chỗ 2 số này. Dãy mới là [3, 5, 4, 6, 8].
• Sau 4 lần so sánh, ta đã đặt được số 8 là số lớn nhất xuống cuối dãy.

Số 8 lớn nhất đã được sắp xếp đúng vị trí. Vậy ta bỏ số 8 ra khỏi dãy cần sắp xếp. Do đó, độ dài dãy cần sắp xếp bây giờ là 4. Dãy hiện tại cần sắp xếp là [3, 5, 4, 6].

• Bắt cặp 3 với 5. 3 bé hơn 5 nên ta không làm gì.
• Tiếp theo, bắt cặp 5 với 4. Vì 4 bé hơn nên ta đổi chỗ 2 số này. Dãy mới là [3, 4, 5, 6].
• Tiếp theo, bắt cặp 5 với 6. 5 bé hơn 6 nên ta không làm gì.
• Sau 3 lần so sánh, ta đã đặt được số 6 là số lớn nhất xuống cuối dãy.

Số 6 lớn thứ hai đã được sắp xếp đúng vị trí. Vậy ta bỏ số 6 ra khỏi dãy cần sắp xếp. Do đó, độ dài dãy cần sắp xếp bây giờ là 3. Dãy hiện tại cần sắp xếp là [3, 4, 5].

• Bắt cặp 3 với 4. 3 bé hơn 4 nên ta không làm gì.
• Tiếp theo, bắt cặp 4 với 5. 4 bé hơn 5 nên ta không làm gì.
• Sau 2 lần so sánh, ta đã đặt được số 5 là số lớn nhất xuống cuối dãy.

Số 5 lớn thứ ba đã được sắp xếp đúng vị trí. Vậy ta bỏ số 5 ra khỏi dãy cần sắp xếp. Do đó, độ dài dãy cần sắp xếp bây giờ là 2. Dãy hiện tại cần sắp xếp là [3, 4].

• Bắt cặp 3 với 4. 3 bé hơn 4 nên ta không làm gì.
• Sau 1 lần so sánh, ta đã đặt được số 4 là số lớn nhất xuống cuối dãy.

Số 4 lớn thứ tư đã được sắp xếp đúng vị trí. Vậy ta bỏ số 4 ra khỏi dãy cần sắp xếp. Do đó, độ dài dãy cần sắp xếp bây giờ là 1. Dãy hiện tại cần sắp xếp là [3]. Vì chỉ có 1 số nên ta không cần so sánh gì nữa.

Vậy việc sắp xếp của chúng ta đã hoàn thành! Kết quả là [3, 4, 5, 6, 8].

Hình ảnh minh họa thuật toán sắp xếp nổi bọt tăng dần

Link project mẫu: https://scratch.mit.edu/projects/405441241/

Bài 8: Sắp xếp dãy số theo thứ tự giảm dần

Để sắp xếp dãy số theo thứ tự giảm dần, ta chỉ cần thay đổi điều kiện so sánh hai số để đổi chỗ các phần tử.

Link project mẫu: https://scratch.mit.edu/projects/405441241/

Xem thêm các dạng bài về danh sách (phần 3) tại link sau: https://laptrinhscratch.com/dang-bai-thi-lien-quan-den-danh-sach-phan-3-day-so-tao-boi-quy-luat/