Kĩ thuật lập trình và thuật toán (định hướng CS)

Đây là trọng tâm của định hướng Khoa học máy tính (CS): phần II thường có một câu đúng/sai cho một chương trình sắp xếp hoặc tìm kiếm in song song Python và C++, hỏi trạng thái dãy sau từng lượt, số lần so sánh, đổi chỗ và độ phức tạp. Phần I cũng có thể hỏi độ phức tạp của một đoạn chương trình. Kĩ năng cốt lõi: chạy tay thuật toán chính xác.

Kiến thức trọng tâm

Bảng tổng hợp thuật toán

Tìm kiếm nhị phân

def nhi_phan(a, x):
    trai, phai = 0, len(a) - 1
    while trai <= phai:
        giua = (trai + phai) // 2
        if a[giua] == x:
            return giua
        if a[giua] < x:
            trai = giua + 1
        else:
            phai = giua - 1
    return -1

a = [2, 5, 9, 14, 20, 27, 33, 41, 48]
print(nhi_phan(a, 33), nhi_phan(a, 10))

#include <iostream>
#include <vector>
using namespace std;
int nhi_phan(vector<int>& a, int x) {
    int trai = 0, phai = a.size() - 1;
    while (trai <= phai) {
        int giua = (trai + phai) / 2;
        if (a[giua] == x)
            return giua;
        if (a[giua] < x)
            trai = giua + 1;
        else
            phai = giua - 1;
    }
    return -1;
}
int main() {
    vector<int> a = {2, 5, 9, 14, 20, 27, 33, 41, 48};
    cout << nhi_phan(a, 33) << " " << nhi_phan(a, 10);
    return 0;
}

Chương trình in 6 -1. Vết khi tìm x = 10:

Tìm x = 33 chỉ cần 2 bước (gặp 20 rồi 33). Với n phần tử, số bước tối đa khoảng $\log_2 n + 1$: 1000 phần tử chỉ cần tối đa 10 bước, trong khi tìm tuần tự có thể phải so sánh cả 1000 phần tử.

Ba thuật toán sắp xếp đơn giản

Cả ba chương trình in dãy sau mỗi lượt của vòng lặp ngoài, chạy với dãy 6 3 8 2 5.

Sắp xếp chọn

def sap_xep_chon(a):
    n = len(a)
    for i in range(n - 1):
        vt = i
        for j in range(i + 1, n):
            if a[j] < a[vt]:
                vt = j
        a[i], a[vt] = a[vt], a[i]
        for x in a:
            print(x, end=" ")
        print()

sap_xep_chon([6, 3, 8, 2, 5])

#include <iostream>
#include <vector>
using namespace std;
void sap_xep_chon(vector<int> a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        int vt = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[vt])
                vt = j;
        swap(a[i], a[vt]);
        for (int x : a) cout << x << " ";
        cout << endl;
    }
}
int main() {
    sap_xep_chon({6, 3, 8, 2, 5});
    return 0;
}

Sắp xếp chèn

def sap_xep_chen(a):
    for i in range(1, len(a)):
        k = a[i]
        j = i - 1
        while j >= 0 and a[j] > k:
            a[j + 1] = a[j]
            j = j - 1
        a[j + 1] = k
        for x in a:
            print(x, end=" ")
        print()

sap_xep_chen([6, 3, 8, 2, 5])

#include <iostream>
#include <vector>
using namespace std;
void sap_xep_chen(vector<int> a) {
    for (int i = 1; i < (int)a.size(); i++) {
        int k = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > k) {
            a[j + 1] = a[j];
            j = j - 1;
        }
        a[j + 1] = k;
        for (int x : a) cout << x << " ";
        cout << endl;
    }
}
int main() {
    sap_xep_chen({6, 3, 8, 2, 5});
    return 0;
}

Sắp xếp nổi bọt xem ở Dạng 2. Vết của cả ba thuật toán trên dãy 6 3 8 2 5:

Độ phức tạp thời gian

Độ phức tạp đánh giá số phép toán cơ bản theo kích thước dữ liệu n, viết dạng $O(\cdot)$: bỏ hằng số, giữ số hạng bậc cao nhất. Hai vòng lặp lồng nhau → nhân; hai đoạn nối tiếp → lấy đoạn lớn hơn.

n = 8
s = 0
for i in range(n):
    for j in range(i, n):
        s = s + 1
d = 0
k = 1
while k < n:
    k = k * 2
    d = d + 1
print(s, d)

In 36 3. Vòng lồng chạy $n + (n-1) + \dots + 1 = \dfrac{n(n+1)}{2}$ lần → $O(n^2)$. Vòng while nhân đôi k nên chạy khoảng $\log_2 n$ lần → $O(\log n)$. Cả đoạn: $O(n^2)$.

Kiểm thử và lập trình có cấu trúc

• Kiểm thử bằng nhiều bộ dữ liệu: trường hợp thông thường, biên (phần tử ở đầu, ở cuối, dãy một phần tử, dãy rỗng), đặc biệt (số âm, các giá trị bằng nhau, dãy đã sắp xếp). Kiểm thử phát hiện lỗi nhưng không chứng minh chương trình hết lỗi.
• Làm mịn dần: chia bài toán lớn thành các bước nhỏ, chi tiết hóa từng bước cho tới khi viết được thành lệnh.
• Mô đun hóa: tách mỗi nhiệm vụ thành một hàm (nhập, xử lí, in kết quả) → dễ đọc, dễ kiểm thử, dùng lại được; gom các hàm hay dùng thành thư viện.

Dạng bài thường gặp trong đề thi

Dạng 1: Chọn bộ dữ liệu kiểm thử phát hiện lỗi

Dạng 2: Câu đúng/sai về sắp xếp nổi bọt có dừng sớm

Dạng 3: Xác định độ phức tạp

Lỗi thường gặp

Mẹo làm bài

Tự kiểm tra nhanh

1. Với dãy đã sắp xếp gồm 9 phần tử ở trên, tìm x = 48 bằng hàm nhi_phan cần so sánh với những phần tử nào?

2. Sắp xếp chọn dãy 6 3 8 2 5 (tăng dần) thực hiện bao nhiêu lần đổi chỗ thực sự (hai phần tử khác vị trí)?

3. Dãy đã tăng dần gồm n phần tử. Sắp xếp chèn thực hiện bao nhiêu phép so sánh a[j] > k?

4. Đoạn for i in range(n): for j in range(n): ... lồng nhau có độ phức tạp gì? Nếu thay vòng trong bằng for j in range(5) thì sao?

5. Vì sao "chạy thử 10 bộ dữ liệu đều đúng" chưa chứng minh được chương trình không có lỗi?