Sắp xếp dãy số, tìm min, max | Tin học trẻ

Bài viết này sẽ hướng dẫn giải dạng bài danh sách (chuỗi) trong kỳ thi tin học trẻ bằng Scratch 3.0 ví dụ như tính tìm số lớn nhất, nhỏ nhất, sắp xếp dãy số tăng dần, giảm dần theo thuật toán nổi bọt.

Trước khi bắt tay làm các dạng bài tập về dãy số phần 2, các bạn cần phải nắm chắc kỹ thuật duyệt phần tử trong dãy. Các bạn có thể xem lại phần kiến thức này trong bài viết này.

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

Các bước thực hiện:

Tạo biến tên là max để lưu giá trị của số lớn nhất.
Ban đầu, ta 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 sẽ bắt đầu từ phần tử thứ 2 trong dãy cho đến hết.
Khi duyệt hết phần tử trong dãy, ta có max chính là giá trị lớn nhất của dãy số.

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

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

Làm tương tự như bài 6. Các bước thực hiện như sau:

Tạo biến tên là min để lưu giá trị của số nhỏ nhất.
Ban đầu, ta 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 sẽ bắt đầu từ phần tử thứ 2 trong dãy cho đến hết.
Khi duyệt hết phần tử trong dãy, ta có 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 cách (thuật toán) để sắp xếp dãy số. Trên thực tế, lập trình trình viên sẽ lựa chọn những thuật toán nhanh nhất giúp tối ưu chương trình. Tuy nhiên, trong trường hợp này, chúng ta sẽ chọn thuật toán đơn giản nhất để giới thiệu về thuật toán sắp xếp. Đó là thuật toán sắp xếp nổi bọt (Bubble Sort)

Thuật toán sắp xếp nổi bọt (Bubble Sort) 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 tăng dần cho dãy số [5, 3, 8, 4, 6]

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.

Đầu tiên chúng ta sẽ 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, chúng ta bắt cặp 5 với 8. 5 bé hơn nên chúng ta không làm gì.
Tiếp theo, chúng ta 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, chúng ta 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]

Đầu tiên chúng ta sẽ bắt cặp 3 với 5. 3 bé hơn 5 nên chúng ta không làm gì.
Tiếp theo, chúng ta 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, chúng ta bắt cặp 5 với 6. 5 bé hơn 6 nên chúng 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]

Đầu tiên chúng ta sẽ bắt cặp 3 với 4. 3 bé hơn 4 nên chúng ta không làm gì.
Tiếp theo, chúng ta bắt cặp 4 với 5. 4 bé hơn 5 nên chúng 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]

Chúng ta sẽ bắt cặp 3 với 4. 3 bé hơn 4 nên chúng 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 chúng 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ả [3, 4, 5, 6, 8]

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

Làm tương tự như bài 7. Chỉ cần thay điều kiện so sánh hai số để đổi chỗ các phần tử là được.

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/