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

Mục lục (5 phần)

Đâ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

Thuật toán	Ý tưởng	Điều kiện	Tốt nhất	Xấu nhất
Tìm kiếm tuần tự	Duyệt lần lượt từ đầu tới khi gặp	Không cần sắp xếp	$O(1)$	$O(n)$
Tìm kiếm nhị phân	So với phần tử giữa, bỏ một nửa	Dãy đã sắp xếp	$O(1)$	$O(\log n)$
Sắp xếp chọn	Mỗi lượt chọn phần tử nhỏ nhất đưa lên đầu đoạn chưa xếp		$O(n^2)$	$O(n^2)$
Sắp xếp nổi bọt	Đổi chỗ cặp kề nhau sai thứ tự, phần tử lớn "nổi" về cuối		$O(n)$ nếu có dừng sớm	$O(n^2)$
Sắp xếp chèn	Chèn từng phần tử vào đúng chỗ trong đoạn đầu đã xếp		$O(n)$ khi dãy đã tăng	$O(n^2)$

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:

trai	phai	giua	a[giua]	So sánh với 10
0	8	4	20	lớn hơn → phai = 3
0	3	1	5	nhỏ hơn → trai = 2
2	3	2	9	nhỏ hơn → trai = 3
3	3	3	14	lớn hơn → phai = 2
3	2			trai > phai → dừng, trả về −1

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:

Sau lượt	Chọn	Nổi bọt	Chèn
1	`2 3 8 6 5` (đổi 6 và 2)	`3 6 2 5 8` (8 về cuối)	`3 6 8 2 5` (chèn 3)
2	`2 3 8 6 5` (3 đã đúng chỗ)	`3 2 5 6 8`	`3 6 8 2 5` (8 giữ nguyên)
3	`2 3 5 6 8` (đổi 8 và 5)	`2 3 5 6 8`	`2 3 6 8 5` (chèn 2 lên đầu)
4	`2 3 5 6 8`	`2 3 5 6 8`	`2 3 5 6 8` (chèn 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)$ ⁠.

Độ phức tạp	Tên gọi	Ví dụ
$O(1)$	Hằng số	Truy cập `a[i]`, hoán đổi hai biến
$O(\log n)$	Lôgarit	Tìm kiếm nhị phân
$O(n)$	Tuyến tính	Tìm tuần tự, tính tổng dãy
$O(n^2)$	Bình phương	Sắp xếp chọn, nổi bọt, chèn

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

Ví dụ

Hàm sau định tìm giá trị lớn nhất của danh sách:

def lon_nhat(a):
    m = 0
    for x in a:
        if x > m:
            m = x
    return m

print(lon_nhat([3, 9, 4]), lon_nhat([-5, -2, -9]))

Bộ dữ liệu nào phát hiện được lỗi của hàm?

Xem lời giải

Chương trình in 9 0. Với [3, 9, 4] kết quả đúng, nhưng với dãy toàn số âm [-5, -2, -9] hàm trả về 0 (giá trị khởi tạo) thay vì −2. Lỗi: khởi tạo m = 0. Sửa: m = a[0]. Bộ dữ liệu đặc biệt (toàn số âm) mới lộ ra lỗi này.

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

Ví dụ

Cho chương trình (Python và C++ tương đương):

def noi_bot(a):
    n = len(a)
    for i in range(n - 1):
        doi = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                doi = True
        for x in a:
            print(x, end=" ")
        print()
        if not doi:
            break

noi_bot([2, 1, 3, 5, 4])

#include <iostream>
#include <vector>
using namespace std;
void noi_bot(vector<int> a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        bool doi = false;
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                doi = true;
            }
        for (int x : a) cout << x << " ";
        cout << endl;
        if (!doi)
            break;
    }
}
int main() {
    noi_bot({2, 1, 3, 5, 4});
    return 0;
}

a) Sau lượt thứ nhất, dãy đã được sắp xếp tăng dần.

b) Chương trình in ra 4 dòng.

c) Tổng số phép so sánh a[j] > a[j + 1] được thực hiện là 7.

d) Nếu bỏ biến doi và lệnh dừng vòng lặp thì dòng cuối cùng in ra sẽ khác.

Xem lời giải

a) Đúng. Lượt 1 (j = 0…3): đổi (2, 1) → 1 2 3 5 4; (2, 3), (3, 5) giữ nguyên; đổi (5, 4) → 1 2 3 4 5.
b) Sai. Lượt 2 (j = 0…2) không đổi chỗ lần nào nên doi vẫn là False; chương trình in dòng thứ hai rồi dừng → 2 dòng.
c) Đúng. Lượt 1 có 4 phép so sánh, lượt 2 có 3 → $4 + 3 = 7$ ⁠.
d) Sai. Không dừng sớm thì chạy đủ 4 lượt (in 4 dòng), nhưng dãy đã tăng dần nên dòng cuối vẫn là 1 2 3 4 5. Dừng sớm chỉ giúp chạy nhanh hơn: trường hợp tốt nhất còn $O(n)$ ⁠.

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

Xem lời giải

Phần 1: $O(n^2)$ ⁠. Phần 2: m lần, mỗi lần $O(\log n)$ → $O(m \log n)$ ⁠. Hai phần nối tiếp nên tổng là $O(n^2 + m \log n)$ ⁠; nếu m không vượt quá n thì $m \log n \le n^2$ ⁠, độ phức tạp là $O(n^2)$ ⁠.

Dạng 4: Vết sắp xếp chọn (đưa phần tử lớn nhất về cuối) và đếm số lần đổi chỗ

Ví dụ

Chương trình sau là một cách viết khác của sắp xếp chọn: mỗi lượt tìm phần tử lớn nhất trong đoạn chưa xếp a[0..cuoi] rồi đổi chỗ nó với a[cuoi] (Python và C++ tương đương; bản C++ truyền dãy bằng tham chiếu & để hàm sửa được dãy của chương trình chính):

def sap_xep(a):
    doi = 0
    n = len(a)
    for cuoi in range(n - 1, 0, -1):
        vt = 0
        for j in range(1, cuoi + 1):
            if a[j] > a[vt]:
                vt = j
        if vt != cuoi:
            a[vt], a[cuoi] = a[cuoi], a[vt]
            doi = doi + 1
    return doi

a = [5, 2, 4, 6, 1, 3]
print(sap_xep(a))
for x in a:
    print(x, end=" ")

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

Dòng thứ nhất chương trình in ra là

A. 5
B. 3
C. 15
D. 2

Xem lời giải

Mỗi lượt tìm vị trí vt của số lớn nhất trong a[0..cuoi]; chỉ khi số đó chưa nằm ở cuoi mới đổi chỗ và tăng doi:

Lượt (cuoi)	Lớn nhất trong đoạn	Đổi chỗ?	Dãy sau lượt	`doi`
5	6 ở vị trí 3	có (6 ↔ 3)	`5 2 4 3 1 6`	1
4	5 ở vị trí 0	có (5 ↔ 1)	`1 2 4 3 5 6`	2
3	4 ở vị trí 2	có (4 ↔ 3)	`1 2 3 4 5 6`	3
2	3 ở vị trí 2	không, đã đúng chỗ	`1 2 3 4 5 6`	3
1	2 ở vị trí 1	không	`1 2 3 4 5 6`	3

Chương trình in 3, dòng sau là 1 2 3 4 5 6 → B (chạy thật cả Python và C++).

A là số lượt của vòng ngoài (đếm cả hai lượt không đổi chỗ, tức bỏ quên điều kiện vt != cuoi).
C là số phép so sánh a[j] > a[vt]: $5 + 4 + 3 + 2 + 1 = 15$ — luôn bằng $\dfrac{n(n-1)}{2}$ dù dãy ban đầu thế nào, nên sắp xếp chọn có độ phức tạp $O(n^2)$ cả trong trường hợp tốt nhất.
D là quên lượt đầu tiên (cho cuoi bắt đầu từ n - 2).
Mỗi lượt đổi chỗ nhiều nhất một lần, nên số lần đổi chỗ không vượt quá $n - 1$ ⁠.

Dạng 5: Duyệt mảng hai chiều

Ví dụ

Bảng điểm của 4 học sinh, mỗi người 3 bài kiểm tra, lưu trong mảng hai chiều (Python và C++ tương đương):

diem = [[7, 8, 6],
        [9, 5, 8],
        [6, 9, 9],
        [9, 7, 8]]
tot = -1
vt = -1
for i in range(len(diem)):
    s = 0
    for x in diem[i]:
        s = s + x
    if s > tot:
        tot = s
        vt = i
print(vt, tot)

#include <iostream>
using namespace std;
int main() {
    int diem[4][3] = {{7, 8, 6},
                      {9, 5, 8},
                      {6, 9, 9},
                      {9, 7, 8}};
    int tot = -1, vt = -1;
    for (int i = 0; i < 4; i++) {
        int s = 0;
        for (int j = 0; j < 3; j++)
            s = s + diem[i][j];
        if (s > tot) {
            tot = s;
            vt = i;
        }
    }
    cout << vt << " " << tot;
    return 0;
}

a) Chương trình in ra 2 24.

b) Vòng lặp ngoài chạy 3 lần.

c) Nếu đổi s > tot thành s >= tot thì chương trình in ra 3 24.

d) Nếu khởi tạo tot = 0 thay cho tot = -1 thì kết quả in ra thay đổi.

Xem lời giải

Vòng ngoài duyệt từng hàng (từng học sinh), vòng trong cộng 3 điểm của hàng đó:

i	Hàng `diem[i]`	s	tot, vt sau lượt
0	7 8 6	21	21, 0
1	9 5 8	22	22, 1
2	6 9 9	24	24, 2
3	9 7 8	24	24, 2 (24 > 24 sai)

a) Đúng. Học sinh ở hàng chỉ số 2 (hàng thứ ba) có tổng cao nhất 24.
b) Sai. Có 4 hàng nên vòng ngoài chạy 4 lần; vòng trong chạy 3 lần mỗi hàng, tổng cộng $4 \cdot 3 = 12$ lần cộng.
c) Đúng. Với >=, hàng 3 có tổng bằng 24 cũng được ghi nhận nên vt = 3. Dùng > giữ hàng đầu tiên đạt giá trị lớn nhất, dùng >= giữ hàng cuối cùng.
d) Sai. Mọi tổng đều dương nên ở lượt đầu $21 > 0$ vẫn cập nhật; kết quả vẫn là 2 24.

Mảng m hàng, n cột được duyệt hết bằng hai vòng lồng nhau: độ phức tạp $O(m \cdot n)$ ⁠.

Dạng 6 (bẫy): Tìm kiếm nhị phân sai điều kiện lặp

Ví dụ

Bạn H viết hàm tìm kiếm nhị phân, thử với 17 và 31 đều đúng nên cho rằng hàm không có lỗi:

def tim(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 = [3, 8, 12, 17, 25, 31, 40]
print(tim(a, 17), tim(a, 31), tim(a, 40))

Chương trình in ra

A. 3 5 6
B. 3 -1 -1
C. 3 5 -1
D. -1 5 6

Xem lời giải

Tìm 17: giua = 3, gặp ngay → 3. Tìm 31: giua = 3 (17 < 31, trai = 4), rồi giua = 5 → 5. Vết khi tìm 40:

trai	phai	giua	Xử lí
0	6	3	17 < 40 → trai = 4
4	6	5	31 < 40 → trai = 6
6	6		`6 < 6` sai → dừng, trả về −1

Chương trình in 3 5 -1 → C. A là kết quả mong đợi của hàm đúng.

Lỗi: khi đoạn tìm còn đúng một phần tử (trai = phai), điều kiện trai < phai đã sai nên phần tử đó không bao giờ được so sánh. Thử cả 7 phần tử, hàm trả về −1 với 3, 12, 25, 40 (các vị trí 0, 2, 4, 6). Sửa: while trai <= phai.

Bài học kiểm thử: hai bộ dữ liệu "tình cờ đúng" không chứng minh được gì; phải thử các giá trị biên như phần tử đầu dãy, cuối dãy.

Lỗi thường gặp

Mẹo làm bài

Tự kiểm tra nhanh

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?

Xem đáp án

20 (giua = 4) → 33 (giua = 6) → 41 (giua = 7) → 48 (giua = 8): 4 lần, trả về vị trí 8.

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í)?

Xem đáp án

2 lần: lượt 1 đổi 6 và 2, lượt 3 đổi 8 và 5. Lượt 2 và lượt 4 phần tử nhỏ nhất đã ở đúng chỗ.

Dãy đã tăng dần gồm n phần tử. Chương trình sap_xep_chon ở trên thực hiện bao nhiêu phép so sánh a[j] < a[vt]?

Xem đáp án

Vẫn đủ $(n-1) + (n-2) + \dots + 1 = \dfrac{n(n-1)}{2}$ phép: mỗi lượt sắp xếp chọn đều duyệt hết đoạn chưa xếp để tìm phần tử nhỏ nhất, không dừng sớm được → kể cả khi dãy đã tăng dần, độ phức tạp vẫn là $O(n^2)$ ⁠.

Đ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?

Xem đáp án

$O(n^2)$ ⁠. Vòng trong chạy 5 lần cố định → tổng $5n$ lần → $O(n)$ ⁠.

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?

Xem đáp án

Kiểm thử chỉ kiểm tra các trường hợp đã chọn; có thể còn trường hợp chưa thử (biên, đặc biệt) làm chương trình sai.

Kiểm tra lại kiến thức vừa ôn

Làm 10 câu luyện tập về kĩ thuật lập trình và thuật toán (định hướng cs) và xem lời giải ngay sau mỗi câu.

Luyện tập ngay

Đề có câu hỏi về chủ đề này

Đề ôn luyện số 1

50 phút · Trung bình

Làm thử miễn phí

Đề ôn luyện số 2

50 phút · Cơ bản

Làm thử miễn phí

Đề ôn luyện số 3

50 phút · Nâng cao

Làm thử miễn phí