Ví dụ: Chương 4: Ôn thi tốt nghiệp

Giới thiệu bài học

Chương 4 là chương ôn thi tốt nghiệp môn Tin học lớp 12, giúp các em hệ thống lại kiến thức trọng tâm đã học trong suốt năm học. Bài học hôm nay sẽ đi vào một ví dụ cụ thể để minh họa cách vận dụng kiến thức về cấu trúc dữ liệu mảng và thuật toán sắp xếp trong ngôn ngữ lập trình Python. Đây là dạng bài thường gặp trong đề thi tốt nghiệp, yêu cầu các em không chỉ nhớ lý thuyết mà còn biết phân tích bài toán và viết chương trình từng bước.

Lý thuyết cần nhớ

Trước khi đi vào ví dụ, các em hãy ôn lại một số kiến thức quan trọng:

• Mảng (list) trong Python: Là cấu trúc dữ liệu có thứ tự, cho phép chứa nhiều phần tử cùng loại (ví dụ: số nguyên). Các phần tử được đánh chỉ số từ 0.
• Thuật toán sắp xếp nổi bọt (Bubble Sort): Là thuật toán sắp xếp đơn giản, hoạt động bằng cách lặp đi lặp lại việc so sánh hai phần tử liền kề và đổi chỗ nếu chúng sai thứ tự.
• Cách nhập dữ liệu: Dùng hàm input() để nhập chuỗi, sau đó dùng split() và map() để chuyển thành danh sách số nguyên.
• Vòng lặp for và if: Công cụ cơ bản để duyệt mảng và thực hiện các bước so sánh.

Ví dụ minh họa từng bước

Đề bài:

Nhập vào từ bàn phím một dãy số nguyên gồm n phần tử (n <= 10). Hãy sắp xếp dãy số theo thứ tự tăng dần bằng thuật toán sắp xếp nổi bọt. In ra dãy số sau khi sắp xếp.

Phân tích bài toán (bước 1):

• Input: Số n (số lượng phần tử) và n số nguyên.
• Output: Dãy số đã được sắp xếp tăng dần.
• Giải thuật: Sử dụng Bubble Sort. Ý tưởng: Với mỗi lượt đi từ đầu đến cuối mảng, so sánh hai phần tử liền kề, nếu phần tử trước lớn hơn phần tử sau thì đổi chỗ. Lặp lại cho đến khi mảng được sắp xếp.

Viết chương trình (bước 2):

# Bước 1: Nhập dữ liệu
n = int(input("Nhập số lượng phần tử n: "))
list_so = list(map(int, input("Nhập các số nguyên, cách nhau bởi dấu cách: ").split()))

# Bước 2: Thực hiện sắp xếp nổi bọt
for i in range(n - 1):               # Số lượt cần duyệt
    for j in range(n - 1 - i):       # Mỗi lượt xét các cặp liền kề
        if list_so[j] > list_so[j + 1]:   # Nếu sai thứ tự thì đổi chỗ
            # Hoán đổi giá trị
            tam = list_so[j]
            list_so[j] = list_so[j + 1]
            list_so[j + 1] = tam

# Bước 3: In kết quả
print("Dãy số sau khi sắp xếp tăng dần:")
for so in list_so:
    print(so, end=" ")

Giải thích từng bước (bước 3):

1. Nhập dữ liệu: Dòng n = int(input(...)) yêu cầu nhập số phần tử. Dòng list_so = list(map(int, ...)) nhập chuỗi các số, tách bằng split(), chuyển mỗi chuỗi thành số nguyên rồi đưa vào list.
2. Vòng lặp ngoài: for i in range(n - 1): – vì sau mỗi lượt, phần tử lớn nhất đã "nổi" lên cuối, nên chỉ cần duyệt n-1 lượt.
3. Vòng lặp trong: for j in range(n - 1 - i): – giảm dần số lần so sánh vì các phần tử cuối đã đúng vị trí.
4. So sánh và đổi chỗ: Nếu list_so[j] > list_so[j+1], ta dùng biến tam để hoán đổi giá trị hai phần tử này.
5. In kết quả: Dùng vòng lặp for để in từng số trên cùng một dòng, cách nhau bởi dấu cách.

Kết quả chạy thử (bước 4):

Giả sử em nhập:

Nhập số lượng phần tử n: 5
Nhập các số nguyên, cách nhau bởi dấu cách: 7 2 9 1 5

Chương trình sẽ in ra:

Dãy số sau khi sắp xếp tăng dần:
1 2 5 7 9

Ghi nhớ

• Khi viết chương trình, luôn xác định rõ input và output trước tiên.
• Thuật toán Bubble Sort tuy đơn giản nhưng dễ triển khai và kiểm tra từng bước bằng tay.
• Có thể dùng biến flag để tối ưu: nếu trong một lượt không có đổi chỗ nào thì mảng đã sắp xếp xong, dừng sớm.
• Trong đề thi, các em nhớ ghi chú giải (comment) để giải thích ý tưởng, giúp bài làm rõ ràng hơn.

Bài tập gợi ý

1. Hãy sửa lại chương trình trên để sắp xếp dãy số theo thứ tự giảm dần.
2. Viết chương trình nhập danh sách điểm thi của 10 học sinh (là số thực), sau đó sắp xếp tăng dần và in ra kết quả.
3. Áp dụng thuật toán Selection Sort (sắp xếp chọn) để giải lại bài toán trên, so sánh số lần đổi chỗ với Bubble Sort.