Đăng nhập để tham gia lộ trình luyện tập

LỘ TRÌNH PYTHON 3 CƠ BẢN

PHẦN I. NHẬP MÔN VÀ MÔI TRƯỜNG LẬP TRÌNH

Chương 1. Nhập môn lập trình, tư duy giải quyết vấn đề và Thonny

Chương trình là dãy chỉ dẫn mà máy tính thực hiện theo quy tắc xác định. Thuật toán (algorithm) là các bước hữu hạn, rõ ràng để giải bài toán; mã nguồn (source code) là cách diễn đạt thuật toán bằng ngôn ngữ lập trình. Python thông thường thực thi chương trình qua trình thông dịch và môi trường chạy.

Trước khi viết lệnh, tách bài toán theo mô hình Dữ liệu vào – Xử lý – Dữ liệu ra (Input – Process – Output). Xác định kiểu dữ liệu, giới hạn, trường hợp đặc biệt và điều kiện để kết quả đúng. Với bài toán lớn, chia thành các nhiệm vụ nhỏ rồi nối chúng theo đúng thứ tự.

đọc và xác định dữ liệu vào
xác định kết quả phải xuất
mô tả cách biến dữ liệu vào thành kết quả
thử từng bước bằng một ví dụ nhỏ
viết chương trình Python 3
so sánh kết quả thực tế với kết quả mong đợi
sửa nguyên nhân sai và thử lại trường hợp biên

Truy vết (trace) là ghi lại giá trị biến và nhánh được thực hiện sau mỗi bước. Trong Thonny, Editor dùng để viết tệp .py, Shell hiển thị tương tác và kết quả, Assistant hỗ trợ đọc lỗi. Lưu tệp, chạy, quan sát thông báo lỗi rồi trở lại đúng dòng gây lỗi. Một chương trình chạy được chưa đủ để kết luận chương trình đúng.

Chương 2. Chương trình Python đầu tiên và cơ chế xuất dữ liệu

Python thực thi các câu lệnh tuần tự từ trên xuống, trừ khi có cấu trúc điều khiển khác. print() xuất các giá trị ra luồng xuất chuẩn; mặc định ngăn cách nhiều đối số bằng một khoảng trắng và kết thúc bằng xuống dòng. sep thay dấu phân cách, end thay ký tự kết thúc. Chú thích một dòng bắt đầu bằng #.

print("Xin chào")
print(3, 5, sep=" - ")      # 3 - 5
print("A", end=" ")
print("B")                  # A B
print("Dòng 1\nDòng 2")
print("Cột 1\tCột 2")

Chuỗi có thể dùng nháy đơn, nháy kép hoặc ba dấu nháy cho nhiều dòng. \n là xuống dòng, \t là tab, \\ biểu diễn dấu gạch chéo ngược. Phép + nối các chuỗi, còn print("A", "B") tự chèn dấu cách theo sep. Trên hệ thống chấm tự động, không xuất thêm lời nhắc nhập hoặc chú thích vào kết quả: mọi ký tự thừa có thể làm sai định dạng.

PHẦN II. DỮ LIỆU, BIẾN VÀ BIỂU THỨC

Chương 3. Biến, phép gán và mô hình tham chiếu đối tượng

Phép gán = ràng buộc một tên biến với một đối tượng, không phải phép so sánh. Python có kiểu động (dynamic typing): đối tượng mang kiểu, còn tên có thể được gán lại để tham chiếu đối tượng kiểu khác. Tên biến phân biệt hoa thường, không bắt đầu bằng chữ số và không trùng từ khóa; thông thường dùng snake_case. Tên viết hoa như PI chỉ là quy ước hằng số, không tạo cơ chế bất biến.

so_luong = 3
so_luong = so_luong + 2   # 5
a, b = 4, 9
a, b = b, a             # a = 9, b = 4
PI = 3.14159

Khi truy vết, tính toàn bộ vế phải bằng các giá trị hiện tại rồi mới cập nhật tên ở vế trái. Dùng một tên chưa được định nghĩa gây NameError. Với các kiểu khả biến học về sau, hai tên có thể cùng tham chiếu một đối tượng; phép gán đơn thuần không tạo bản sao.

Chương 4. Kiểu dữ liệu cơ bản và chuyển đổi kiểu

int lưu số nguyên; float lưu số thực dấu phẩy động; bool có True, False; str lưu văn bản; None biểu thị thiếu hoặc chưa có giá trị. type(x) trả về kiểu thực tế, còn isinstance(x, T) kiểm tra một đối tượng có thuộc kiểu T hay không. Chú ý bool là kiểu con của int trong Python.

so = int("42")
pi = float("3.14")
chu = str(42)
print(type(so), isinstance(so, int))
print(bool(0), bool(""), bool(None))  # False False False

input() trả về str, vì vậy muốn tính toán cần chuyển đổi đúng. int("3.5") gây ValueError; có thể dùng float("3.5") nếu dữ liệu cho phép số thực. Phép toán phối hợp int với float thường cho kết quả float. Phân biệt 0, "" và None: cả ba đều là giá trị sai khi chuyển thành bool, nhưng chúng khác kiểu và khác ý nghĩa.

Chương 5. Nhập và chuẩn hóa dữ liệu đầu vào

Chọn cách đọc theo đặc tả dữ liệu vào, không theo cảm giác. input() đọc một dòng, split() không có đối số tách theo các cụm khoảng trắng và bỏ khoảng trắng thừa. map(int, ...) chuyển lần lượt các mảnh chuỗi thành số nguyên; unpacking phân phối các giá trị vào các biến.

n = int(input())
a, b = map(int, input().split())
day = input().strip()
values = list(map(int, input().split()))

Ví dụ d, m, y = map(int, input().split()) yêu cầu đúng ba số trên một dòng. Chỉ trong chương trình tương tác có thể dùng input("Hãy nhập ngày: "); khi gửi bài lên OJ, dùng input() không kèm lời nhắc. Nếu đề cho n rồi n số ở nhiều dòng, phải đọc đủ số thay vì mặc định tất cả nằm cùng một dòng. Dữ liệu của bài thi thường được giả định hợp lệ trong phạm vi đề; ứng dụng thực tế có thể cần xác thực và yêu cầu nhập lại.

Chương 6. Số học và biểu thức tính toán

Các toán tử cơ bản là +, -, *, /, //, %, **. / cho phép chia thực; // lấy thương làm tròn xuống; % là số dư tương ứng với thương đó. Với $b\ne0$, Python thỏa $a=(a//b)b+(a\%b)$. Không nhầm // với phép cắt phần thập phân về 0 khi có số âm.

print(7 / 3)     # 2.333...
print(7 // 3)    # 2
print(7 % 3)     # 1
print(-7 // 3)   # -3
print(-7 % 3)    # 2
print(2 ** 5)    # 32

Dùng ngoặc khi biểu thức nhiều tầng. +=, -=, *=, /=, //=, %=, **= là gán kết hợp. abs, pow, round, min, max và sum hỗ trợ phép toán thường gặp; round() không phải công cụ đảm bảo quy tắc làm tròn thập phân tài chính. Muốn lấy chữ số hàng đơn vị dùng n % 10, bỏ hàng đơn vị dùng n // 10 với số nguyên không âm.

Với tổng $s$ giây không âm, đổi sang giờ–phút–giây:

Chương 7. Số thực, sai số và định dạng số

Phần lớn số thập phân không được biểu diễn chính xác bằng nhị phân hữu hạn, nên phép toán float có sai số. Không mặc định so sánh hai kết quả tính toán bằng == nếu đề yêu cầu so sánh gần đúng. Với sai số tuyệt đối $\varepsilon$, một cách kiểm tra là $|a-b|\le\varepsilon$; math.isclose kết hợp ngưỡng tương đối và tuyệt đối.

import math

a = 0.1 + 0.2
print(a == 0.3)                      # False
print(math.isclose(a, 0.3))          # True
print(f"{a:.2f}")                    # 0.30
print(f"{12345.6:,.1f}")             # 12,345.6

f"{x:.2f}" định dạng khi xuất, không làm thay đổi giá trị trong biến x. Các dạng :>8, :<8, :^8 lần lượt căn phải, trái, giữa; :.1% hiển thị theo phần trăm; :.3e dùng ký pháp khoa học. Chỉ làm tròn tại bước đề yêu cầu, tránh làm tròn trung gian gây sai số cộng dồn.

Chương 8. Kiểu chuỗi và biểu diễn văn bản

str là một dãy ký tự Unicode bất biến (immutable). Có thể ghép chuỗi bằng +, nhân chuỗi với số nguyên không âm bằng *, lấy độ dài bằng len. ord() đổi một ký tự thành mã Unicode, chr() thực hiện chiều ngược lại. So sánh chuỗi theo thứ tự từ điển dựa trên mã ký tự, không tự động bỏ dấu hoặc bỏ phân biệt hoa thường.

s = "Python"
print(len(s), s + " 3", "ab" * 3)
print(ord("A"), chr(65))
print("abc" < "abd")

Không thể viết s[0] = "p": cần tạo chuỗi mới. "Tuổi: " + 12 gây TypeError; dùng str(12) hoặc f-string. Dấu r trước chuỗi giúp giữ nguyên phần lớn dấu \ trong raw string; raw string không thể kết thúc bằng một dấu gạch chéo ngược đơn độc.

PHẦN III. LOGIC VÀ ĐIỀU KHIỂN LUỒNG

Chương 9. Đại số Boolean và biểu thức điều kiện

Phép so sánh ==, !=, <, <=, >, >= trả về bool. and cần hai vế đúng, or cần ít nhất một vế đúng, not phủ định. Thứ tự ưu tiên logic thường là not, and, or; nên dùng ngoặc cho điều kiện phức hợp. Python cho phép 1 <= x <= 10 và kiểm tra thành viên bằng in, not in.

x = 7
print(1 <= x <= 10)
print(x % 2 == 1 and x > 0)
print("py" in "python")

== so sánh giá trị, is kiểm tra cùng một đối tượng; dùng is None, không dùng is thay thế == để so sánh số hay chuỗi. and và or có đánh giá ngắn mạch (short-circuit): nếu đã xác định kết quả, vế còn lại không được tính. Chẳng hạn b != 0 and a / b > 2 tránh chia cho 0. Theo De Morgan, not (A and B) tương đương (not A) or (not B).

Chương 10. Cấu trúc rẽ nhánh

if chỉ thực hiện khối lệnh khi điều kiện đúng. if/elif/else xét từ trên xuống và thực hiện nhánh đúng đầu tiên, còn nhiều lệnh if độc lập có thể cùng chạy. Dấu : mở đầu khối và thụt lề xác định phạm vi; điều kiện bao trùm ở trên có thể khiến nhánh hẹp phía dưới không bao giờ được xét.

if diem >= 8:
    loai = "Gioi"
elif diem >= 6.5:
    loai = "Kha"
elif diem >= 5:
    loai = "Dat"
else:
    loai = "Chua dat"

Nếu cần kiểm tra hai điều kiện đồng thời, ghép bằng and hoặc lồng if tùy cách đọc dễ hơn. Biểu thức a if dieu_kien else b dùng khi chọn một giá trị, không nên thay mọi cấu trúc rẽ nhánh dài. Kiểm thử cả giá trị ngay dưới, bằng và ngay trên ngưỡng.

Chương 11. Các mẫu bài toán sử dụng cấu trúc rẽ nhánh

Chuyển điều kiện bằng lời thành các trường hợp đầy đủ và không chồng chéo. Trước khi tính toán, kiểm tra điều kiện hợp lệ. Chẳng hạn ba cạnh dương tạo tam giác khi tổng của hai cạnh bất kỳ lớn hơn cạnh còn lại; nếu sắp tăng $a\le b\le c$ thì chỉ cần kiểm tra $a+b>c$.

a, b, c = sorted(map(int, input().split()))
if a <= 0 or a + b <= c:
    print("INVALID")
elif a == c:
    print("EQUILATERAL")
elif a == b or b == c:
    print("ISOSCELES")
else:
    print("SCALENE")

Năm nhuận khi chia hết cho $400$, hoặc chia hết cho $4$ nhưng không chia hết cho $100$:

nhuan = (y % 400 == 0) or (y % 4 == 0 and y % 100 != 0)

Bài ngày tháng cần kiểm tra tháng $1..12$, sau đó xác định số ngày của tháng rồi mới kiểm tra ngày. Với phương trình $ax+b=0$, xét $a=0$ trước khi chia. Với biểu thức bậc hai, kiểm tra hệ số đầu khác 0 rồi xét biệt thức $\Delta=b^2-4ac$. Bài tính phí theo bậc và xếp loại theo ngưỡng cần đặc biệt chú ý cận bằng và thứ tự nhánh.

PHẦN IV. VÒNG LẶP VÀ CÁC MẪU XỬ LÝ

Chương 12. Vòng lặp while

while kiểm tra điều kiện trước mỗi lần lặp: phù hợp khi chưa biết trước số lần. Luôn xác định biến khởi tạo, điều kiện tiếp tục và cách cập nhật để vòng lặp tiến tới điểm dừng. Giá trị chặn (sentinel) báo kết thúc luồng dữ liệu; break thoát hẳn vòng lặp, continue chuyển sang lần kiểm tra kế tiếp.

i = 1
while i <= 5:
    print(i)
    i += 1

khởi tạo trạng thái
trong khi điều kiện tiếp tục đúng:
    thực hiện công việc
    cập nhật trạng thái để tiến gần điều kiện dừng

while ... else chỉ chạy nhánh else nếu vòng lặp kết thúc bình thường, không do break. Với continue, đặc biệt chú ý không bỏ qua bước cập nhật biến đếm. Lỗi cận < và <= thường làm dư hoặc thiếu một lần lặp.

Chương 13. Vòng lặp for và range

for duyệt từng phần tử của đối tượng khả duyệt (iterable). range(start, stop, step) bắt đầu tại start, không bao gồm stop và phải có step khác 0. range(n) duyệt $0,1,\ldots,n-1$; range(n-1,-1,-1) duyệt ngược $n-1,\ldots,0$.

for i in range(1, 6):
    print(i)                # 1..5

for i in range(5, 0, -1):
    print(i)                # 5..1

for ky_tu in "ABC":
    print(ky_tu)

Dùng for khi duyệt dãy hoặc có khoảng lặp rõ ràng; dùng while khi điều kiện dừng phụ thuộc trạng thái thay đổi. for ... else hoạt động như while ... else: else chạy nếu không bị break. Với bước dương, số phần tử trong range(start, stop, step) là $\max(0,\lceil(stop-start)/step\rceil)$.

Chương 14. Các mẫu tích lũy, đếm và tìm kiếm bằng vòng lặp

Mỗi mẫu xử lý cần biến trạng thái phù hợp: tổng bắt đầu bằng $0$, tích bằng $1$, bộ đếm bằng $0$. Tìm min hoặc max trên dãy không rỗng nên khởi tạo bằng phần tử đầu, không tự chọn 0 vì toàn bộ dữ liệu có thể âm. Khi tìm vị trí đầu tiên, dừng ngay; muốn vị trí cuối cùng thì tiếp tục cập nhật.

numbers = [4, -2, 7, -2]
tong = 0
dem_am = 0
lon_nhat = numbers[0]
for x in numbers:
    tong += x
    if x < 0:
        dem_am += 1
    if x > lon_nhat:
        lon_nhat = x

Mẫu tồn tại (any) chỉ cần một phần tử thỏa; mẫu mọi phần tử (all) thất bại khi gặp phần tử không thỏa. Muốn tìm hai số lớn nhất phân biệt, chỉ cập nhật giá trị thứ hai khi nhỏ hơn giá trị lớn nhất và lớn hơn giá trị thứ hai hiện tại. Với chữ số số nguyên không âm, lấy lần lượt n % 10 rồi n //= 10; trường hợp n = 0 cần được xử lý riêng nếu đếm chữ số. Bảng tần suất theo miền nhỏ dùng danh sách đếm có chỉ số tương ứng giá trị.

Chương 15. Thuật toán số học cơ bản sử dụng vòng lặp

Kiểm tra số nguyên tố $n\ge2$ bằng cách thử ước từ $2$ đến $\lfloor\sqrt n\rfloor$; nếu không có ước thì là số nguyên tố. Khi liệt kê ước, mỗi $d$ tìm được thường đi kèm $n//d$, tránh đếm đôi khi $d^2=n$. Thuật toán Euclid dùng $\gcd(a,b)=\gcd(b,a\bmod b)$ cho tới khi $b=0$.

def la_nguyen_to(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True


def ucln(a, b):
    while b != 0:
        a, b = b, a % b
    return abs(a)

Với hai số nguyên không đồng thời bằng 0, $\operatorname{lcm}(a,b)=|ab|/\gcd(a,b)$; tính an toàn bằng abs(a // ucln(a, b) * b). Phân tích thừa số nguyên tố: thử ước $d$, chia liên tiếp khi còn chia hết rồi tăng $d$; sau vòng lặp, nếu số còn lại lớn hơn 1 thì đó là một thừa số nguyên tố. Fibonacci được sinh từ hai trạng thái liên tiếp; giai thừa và lũy thừa có thể tích lũy bằng vòng lặp. Với chuỗi số gần đúng, điều kiện dừng phải gắn với sai số hoặc độ lớn của số hạng theo yêu cầu bài toán.

Chương 16. Vòng lặp lồng nhau và mô hình hai chiều

Vòng trong hoàn thành các lần lặp của nó cho mỗi lần lặp vòng ngoài. Duyệt lưới $n$ hàng, $m$ cột thực hiện $nm$ lượt; duyệt mọi cặp chỉ số $i<j$ thực hiện $n(n-1)/2$ lượt. Đây là nền tảng trực quan để nhận ra độ phức tạp $O(nm)$ hay $O(n^2)$.

for i in range(n):
    for j in range(m):
        print(i, j)

for i in range(n):
    for j in range(i + 1, n):
        print(i, j)

Để in hình ký tự, vòng ngoài kiểm soát hàng, vòng trong kiểm soát số ký tự mỗi hàng; hình rỗng cần kiểm tra hàng đầu/cuối và cột đầu/cuối. break chỉ thoát vòng lặp gần nhất; muốn thoát cả hai tầng, có thể dùng biến cờ, hàm với return, hoặc thiết kế lại điều kiện điều khiển.

PHẦN V. HÀM, THIẾT KẾ VÀ KIỂM THỬ

Chương 17. Hàm và phương pháp phân rã chương trình

Hàm (function) gói một nhiệm vụ có tên để có thể gọi lại từ nhiều nơi. Khai báo bằng def, các tham số (parameters) nhận giá trị từ đối số (arguments) khi gọi; return kết thúc lời gọi hiện tại và trả kết quả cho nơi gọi. print() chỉ xuất dữ liệu, không thay thế cho giá trị trả về. Hàm không có return tường minh trả về None.

def dien_tich_hcn(dai, rong):
    return dai * rong

s = dien_tich_hcn(5, 3)
print(s)  # 15

Một hàm Boolean nên trả về kết quả logic để dùng trực tiếp trong điều kiện. Nhiều return có thể biểu diễn những trường hợp loại trừ nhau. Khi phân rã, đặt tên hàm theo hành động rõ nghĩa và tách việc tính toán khỏi việc nhập/xuất, giúp kiểm thử từng phần độc lập.

hàm giải_bài_toán(dữ_liệu):
    kiểm tra hoặc chuẩn hóa dữ liệu cần thiết
    gọi các hàm xử lý nhỏ
    kết hợp các kết quả
    trả về đáp án

Chương 18. Đối số, phạm vi tên và nguyên tắc thiết kế hàm

Đối số vị trí được ghép theo thứ tự tham số; đối số từ khóa chỉ rõ tên. Tham số có giá trị mặc định phải đứng sau tham số bắt buộc trong những dạng khai báo cơ bản. Python truyền tham chiếu tới đối tượng vào hàm: thay đổi một danh sách nhận được có thể làm thay đổi danh sách ở ngoài, còn gán lại một tên cục bộ không tự đổi ràng buộc tên ở nơi gọi.

def them_phan_tu(a, x=0):
    a.append(x)               # thay đổi đối tượng a

values = [1, 2]
them_phan_tu(values, x=5)
print(values)                 # [1, 2, 5]

Tên được tra cứu theo quy tắc LEGB: cục bộ, bao ngoài, toàn cục và built-in. Nên dùng tham số và return thay vì phụ thuộc global. Có thể trả nhiều giá trị dưới dạng tuple rồi unpacking. docstring mô tả nhiệm vụ, dữ liệu vào và dữ liệu ra; type hint ghi kiểu dự kiến nhưng không tự kiểm tra kiểu khi chạy.

def chia_lay_du(a: int, b: int) -> tuple[int, int]:
    """Trả về thương nguyên và số dư; yêu cầu b khác 0."""
    return a // b, a % b

thuong, du = chia_lay_du(17, 5)

Hàm thuần (pure function) chỉ phụ thuộc đối số và không thay đổi trạng thái bên ngoài; kiểu thiết kế này thường dễ thử và tái sử dụng hơn. Tránh tham số mặc định là danh sách rỗng nếu hàm sẽ sửa danh sách đó, vì đối tượng mặc định được tạo một lần khi định nghĩa hàm.

Chương 19. Kiểm thử và gỡ lỗi hàm

Tách dữ liệu kiểm thử, kết quả mong đợi và kết quả thực tế. Chọn trường hợp thường, nhỏ nhất, lớn nhất, rỗng, một phần tử, trùng lặp, số âm hoặc số 0 khi chúng nằm trong miền hợp lệ. assert dieu_kien, "thông báo" hữu ích khi kiểm tra giả định lúc phát triển; không nên dùng assert làm cơ chế xác thực đầu vào của ứng dụng vì có thể bị tắt ở chế độ tối ưu hóa.

def tong_chan(a):
    return sum(x for x in a if x % 2 == 0)

assert tong_chan([]) == 0
assert tong_chan([1]) == 0
assert tong_chan([2, 2, -4]) == 0

Nếu hàm in ra giá trị thay vì trả về, phép so sánh với kết quả thường nhận None; kiểm tra vị trí return và đường đi của từng nhánh. Trong Thonny, bước vào hàm và quan sát call stack để biết lời gọi nào đang hoạt động, tham số nào nhận giá trị gì. Khi sửa, chạy lại toàn bộ ca kiểm thử cũ để phát hiện lỗi phát sinh sau thay đổi (regression).

PHẦN VI. CHUỖI VÀ XỬ LÝ VĂN BẢN

Chương 20. Biểu diễn tuần tự của chuỗi và thao tác theo chỉ số

Chuỗi dài $n$ có chỉ số dương từ $0$ đến $n-1$ và chỉ số âm từ $-n$ đến $-1$. s[start:stop:step] tạo chuỗi con mới; cận stop không được lấy, bước step không được bằng 0. Truy cập s[n] gây IndexError, còn slicing vượt cận thường được tự giới hạn.

s = "PYTHON"
print(s[0], s[-1])       # P N
print(s[1:4])            # YTH
print(s[::2])            # PTO
print(s[::-1])           # NOHTYP

for i, ch in enumerate(s):
    print(i, ch)

Chọn duyệt trực tiếp for ch in s khi chỉ cần ký tự; dùng chỉ số hoặc enumerate() khi cần vị trí. Muốn sửa một ký tự phải tạo chuỗi mới, chẳng hạn s[:i] + moi + s[i+1:]. Để so sánh không phân biệt hoa thường, chuẩn hóa cả hai chuỗi bằng lower() hoặc casefold() theo yêu cầu.

Chương 21. Các phép toán chuỗi và chuẩn hóa văn bản

Các phương thức chuỗi trả về chuỗi mới. lower, upper, capitalize, title đổi dạng chữ; strip, lstrip, rstrip loại khoảng trắng hoặc nhóm ký tự ở mép; removeprefix, removesuffix loại đúng tiền tố/hậu tố nếu có. startswith và endswith kiểm tra đầu/cuối; find trả về -1 khi không có, khác index có thể phát sinh ValueError.

s = "  An   Binh  "
words = s.split()
name = " ".join(words)
print(name)                   # An Binh
print(s.strip().lower())
print("a,b,c".split(","))
print("python".find("th"))     # 2

replace thay chuỗi con, count đếm số lần xuất hiện không chồng lấp, splitlines xử lý dòng, partition tách theo lần gặp dấu phân cách đầu tiên. isdigit, isalpha, isalnum, isspace, islower, isupper kiểm tra đặc tính ký tự; một số kết quả chịu ảnh hưởng Unicode. Khi chuẩn hóa văn bản, xác định rõ cần giữ hay bỏ dấu câu, phân biệt chữ hoa và số khoảng trắng; không áp đặt cùng một quy tắc cho mọi bài.

Chương 22. Thuật toán cơ bản trên chuỗi

Với chuỗi đối xứng (palindrome), so sánh hai đầu và tiến vào giữa; muốn bỏ qua khoảng trắng hoặc không phân biệt hoa thường thì chuẩn hóa trước. Đếm tần suất bằng dictionary, tìm ký tự nhiều nhất cần quy định cách xử lý khi đồng hạng. Với nén theo độ dài loạt liên tiếp (run-length encoding), gom mỗi nhóm ký tự giống nhau đứng kề nhau, không gom các ký tự giống nhau nằm cách xa.

nén chuỗi s:
    nếu s rỗng thì trả chuỗi rỗng
    đặt ký tự hiện tại bằng s[0], số lần bằng 1
    duyệt các ký tự còn lại:
        nếu trùng ký tự hiện tại thì tăng số lần
        ngược lại ghi ký tự và số lần, khởi tạo nhóm mới
    ghi nhóm cuối cùng

def nen(s):
    if not s:
        return ""
    result = []
    current, count = s[0], 1
    for ch in s[1:]:
        if ch == current:
            count += 1
        else:
            result.append(current + str(count))
            current, count = ch, 1
    result.append(current + str(count))
    return "".join(result)

Giải nén chỉ xác định được nếu có quy ước mã rõ ràng, đặc biệt khi số lần có nhiều chữ số hoặc ký tự gốc cũng là chữ số. Kiểm tra anagram có thể so sánh hai bảng tần suất sau chuẩn hóa. Tìm chuỗi con trực tiếp: thử từng vị trí bắt đầu và so từng ký tự, độ phức tạp xấu nhất $O(nm)$ với chuỗi dài $n$ và mẫu dài $m$. Mã Caesar dịch chữ cái trong vòng $26$ vị trí; giải mã thử từng khóa khi không biết khóa. Với dữ liệu key=value, chỉ tách ở dấu = đầu tiên bằng split("=", 1) nếu phần giá trị có thể chứa dấu = khác.

PHẦN VII. CẤU TRÚC DỮ LIỆU CƠ BẢN

Chương 23. Cấu trúc danh sách (list)

list là dãy có thứ tự và khả biến (mutable), cho phép chứa nhiều kiểu dữ liệu. Dùng [] tạo danh sách rỗng, len(a) lấy số phần tử, a[i] truy cập/chỉnh sửa theo chỉ số. append(x) thêm một đối tượng ở cuối; extend(iterable) thêm từng phần tử; insert(i,x) chèn tại vị trí.

a = [3, 5]
a.append(7)          # [3, 5, 7]
a.extend([9, 11])    # [3, 5, 7, 9, 11]
a.insert(1, 4)       # [3, 4, 5, 7, 9, 11]
a.remove(7)          # xóa lần xuất hiện đầu tiên của 7
last = a.pop()       # lấy và xóa phần tử cuối

remove xóa theo giá trị và báo lỗi nếu không có; pop xóa theo vị trí và trả phần tử đã xóa; del a[i] xóa theo chỉ số, clear xóa hết. x in a kiểm tra thành viên, index tìm vị trí lần đầu, count đếm số lần xuất hiện. Việc chèn/xóa ở đầu danh sách thường làm dịch các phần tử phía sau.

Chương 24. Duyệt, cắt lát và sao chép danh sách

Duyệt theo giá trị khi chỉ đọc, theo chỉ số khi cần sửa phần tử, bằng enumerate() khi cần cả vị trí lẫn giá trị. a[l:r] tạo danh sách mới; a[l:r] = values có thể thay đổi cả độ dài danh sách. reverse() sửa tại chỗ và trả None, còn reversed(a) tạo đối tượng duyệt ngược.

a = [1, 2, 3]
b = a              # hai tên cùng trỏ một list
c = a[:]           # danh sách mới, sao chép nông
b[0] = 9
print(a, c)        # [9, 2, 3] [1, 2, 3]

for i, x in enumerate(a):
    a[i] = x * 2

a.copy() cũng là sao chép nông (shallow copy): nếu phần tử là list con, bản sao vẫn tham chiếu list con gốc. Có thể dùng copy.deepcopy khi thực sự cần sao chép dữ liệu lồng nhau độc lập. Phép + nối danh sách, * lặp các phần tử, và unpacking phân rã chúng theo vị trí. Khi truyền list vào hàm, sửa phần tử trong list tác động tới đối tượng gốc; trả về list mới khi không muốn gây tác dụng phụ.

Chương 25. Các mẫu xử lý và thuật toán cơ bản trên danh sách

Mẫu xử lý dãy thường gồm một lượt duyệt, một hoặc nhiều biến trạng thái và điều kiện cập nhật. Với dãy không rỗng, khởi tạo min/max bằng phần tử đầu; với trung bình, cần xử lý riêng trường hợp không có phần tử. Tìm số lớn thứ hai phân biệt phải loại giá trị bằng số lớn nhất; không nhầm với phần tử ở vị trí thứ hai sau sắp xếp.

def lon_thu_hai_phan_biet(a):
    unique = set(a)
    if len(unique) < 2:
        return None
    unique.remove(max(unique))
    return max(unique)

Để lọc và biến đổi, tạo list kết quả mới; để loại trùng mà giữ thứ tự, duyệt trái sang phải và dùng set ghi nhận phần tử đã thấy (với phần tử hashable). Đoạn tăng liên tiếp được mở rộng khi a[i] > a[i-1], ngược lại bắt đầu đoạn mới. Dịch vòng danh sách dài $n$ với $k$ bước phải lấy k %= n sau khi xử lý $n=0$. Tìm hai phần tử có tổng cho trước có thể vét cạn mọi $i<j$; chỉ dùng kỹ thuật nhanh hơn khi kiến thức và giới hạn bài cho phép.

Chương 26. Sắp xếp danh sách và thiết kế khóa sắp xếp

a.sort() sửa list tại chỗ và trả None; sorted(a) tạo list mới. Cả hai chấp nhận reverse và key. key biến phần tử thành khóa so sánh; Python sắp xếp ổn định (stable sort), nên các phần tử có khóa bằng nhau giữ thứ tự tương đối ban đầu.

words = ["Cam", "ổi", "an"]
print(sorted(words, key=str.casefold))
records = [("An", 8), ("Binh", 9), ("Chi", 8)]
records.sort(key=lambda item: (-item[1], item[0]))

Tuple được so sánh lần lượt từ trái sang phải; khóa (-diem, ten) tạo điểm giảm dần rồi tên tăng dần. Nếu muốn nhiều tiêu chí có hướng khác nhau, tạo khóa đúng cho từng tiêu chí hoặc tận dụng tính ổn định bằng các lượt sắp xếp. Không mặc định dữ liệu khác kiểu như 3 và "3" có thể so sánh thứ tự; cần chuẩn hóa trước.

Chương 27. Bộ (tuple) và kỹ thuật phân rã dữ liệu (unpacking)

tuple là dãy có thứ tự nhưng bản thân tuple bất biến. Tuple một phần tử viết (x,); dấu phẩy quyết định việc tạo tuple, không phải cặp ngoặc. Tuple thích hợp cho nhóm giá trị cố định, bản ghi nhỏ và kết quả nhiều thành phần của hàm.

point = (3, 4)
x, y = point
a, b = 1, 2
a, b = b, a
one = (7,)

for name, score in [("An", 8), ("Binh", 9)]:
    print(name, score)

Tuple có thể là khóa dictionary nếu tất cả phần tử của nó đều hashable. Một tuple chứa list vẫn có phần tử list thay đổi được, và toàn bộ tuple đó không hashable. So sánh tuple theo thứ tự từ điển khi các phần tử tương ứng so sánh được.

Chương 28. Cấu trúc tập hợp (set)

set giữ các giá trị phân biệt và hỗ trợ kiểm tra thành viên nhanh trong trường hợp trung bình. set() tạo tập rỗng; {} tạo dictionary rỗng. Phần tử phải hashable; không phụ thuộc thứ tự duyệt của set khi in hoặc xử lý.

a = {1, 2, 3}
b = {3, 4}
print(a | b)       # hợp
print(a & b)       # giao
print(a - b)       # hiệu
print(a ^ b)       # hiệu đối xứng
print(a <= b)      # a có là tập con của b?

add thêm một phần tử; update thêm nhiều phần tử; remove báo KeyError nếu không có, discard thì không. pop lấy một phần tử tùy ý, không phải phần tử cuối. Dùng isdisjoint kiểm tra hai tập không có giao; len(set(a)) đếm số giá trị phân biệt. Nếu đề yêu cầu thứ tự, sắp xếp khi xuất hoặc dùng cấu trúc khác.

Chương 29. Cấu trúc từ điển (dictionary)

dict ánh xạ khóa (key) sang giá trị (value). Khóa phải hashable và duy nhất; truy cập d[key] báo KeyError nếu thiếu, còn d.get(key, default) trả giá trị dự phòng. in đối với dictionary kiểm tra khóa, không kiểm tra giá trị.

scores = {"An": 8, "Binh": 9}
scores["Chi"] = 7
scores["An"] = 10
print(scores.get("Dung", 0))
for name, score in scores.items():
    print(name, score)

keys, values, items lần lượt cung cấp góc nhìn khóa, giá trị và cặp; pop vừa xóa vừa trả giá trị, del xóa khóa có sẵn, clear xóa toàn bộ. Dictionary giữ thứ tự chèn trong Python 3 hiện đại, nhưng nếu kết quả yêu cầu thứ tự số/từ điển thì chủ động sorted(d). copy tạo bản sao nông; update gộp các cặp và ghi đè khi khóa trùng.

Chương 30. Các mẫu tổ chức và xử lý dữ liệu bằng từ điển

Bảng tần suất dùng giá trị làm khóa và số lần xuất hiện làm bộ đếm. Nhóm dữ liệu dùng khóa đặc trưng và list các phần tử cùng nhóm. Nếu cần truy cập mặc định, get, setdefault, collections.Counter và collections.defaultdict giảm mã lặp nhưng phải hiểu quy tắc tạo giá trị mặc định.

freq = {}
for x in [2, 3, 2, 2, 5]:
    freq[x] = freq.get(x, 0) + 1

groups = {}
for name, team in [("An", "A"), ("Binh", "B"), ("Chi", "A")]:
    groups.setdefault(team, []).append(name)

Để kiểm tra hai dãy có cùng tần suất, so sánh các bảng đếm; anagram cũng là ứng dụng của mẫu này sau chuẩn hóa chuỗi. Dictionary lồng nhau biểu diễn hồ sơ có nhiều trường; list các dictionary biểu diễn nhiều bản ghi; dictionary chứa list biểu diễn quan hệ một–nhiều. Đảo ánh xạ key -> value thành value -> key chỉ không mất dữ liệu khi các giá trị gốc duy nhất và hashable; nếu trùng giá trị, cần ánh xạ sang danh sách khóa.

PHẦN VIII. TỆP, NGOẠI LỆ VÀ DỮ LIỆU CÓ CẤU TRÚC

Chương 31. Dữ liệu lồng nhau và ma trận hai chiều

Ma trận có $n$ hàng, $m$ cột có thể biểu diễn bằng list chứa các list; phần tử hàng $i$, cột $j$ là a[i][j]. Phải tạo các hàng độc lập. Biểu thức [[0] * m] * n tạo nhiều tham chiếu tới cùng một hàng, nên sửa một ô có thể khiến các hàng khác đổi theo.

n, m = 3, 4
a = [[0] * m for _ in range(n)]
a[0][0] = 7
for row in a:
    print(*row)

Tính tổng hàng bằng sum(a[i]); tổng cột $j$ bằng duyệt a[i][j] qua các hàng. Với ma trận vuông cấp $n$, đường chéo chính gồm a[i][i], đường chéo phụ gồm a[i][n-1-i]. Phần tử biên thỏa $i=0$ hoặc $i=n-1$ hoặc $j=0$ hoặc $j=m-1$; với kích thước một hàng hoặc một cột không được đếm lặp ô biên.

với mỗi hàng i từ 0 đến n - 1:
    với mỗi cột j từ 0 đến m - 1:
        đọc hoặc xử lý a[i][j]
        cập nhật tổng, min, max hay bộ đếm theo yêu cầu

Chuyển vị ma trận $n\times m$ tạo ma trận $m\times n$, với $b[j][i]=a[i][j]$. Cộng hai ma trận đòi hỏi cùng kích thước. Sao chép a[:] chỉ sao chép lớp list ngoài; muốn các hàng độc lập, dùng [row[:] for row in a] cho ma trận hai chiều chỉ chứa các giá trị đơn giản, hoặc copy.deepcopy với cấu trúc lồng phức tạp.

Chương 32. Biểu thức tạo cấu trúc dữ liệu (comprehension) và công cụ duyệt

Comprehension tạo cấu trúc mới từ biểu thức và phép duyệt, có thể kèm điều kiện lọc. Dạng [f(x) for x in data if condition] giữ phần tử thỏa điều kiện rồi biến đổi; biểu thức điều kiện f(x) if condition else g(x) đặt trước for khi muốn giữ cả hai trường hợp.

a = [1, 2, 3, 4]
evens = [x for x in a if x % 2 == 0]
signs = ["chan" if x % 2 == 0 else "le" for x in a]
squares = {x * x for x in a}
mapping = {x: x * x for x in a}

enumerate cho cặp chỉ số–giá trị; zip duyệt song song và dừng tại dãy ngắn nhất; zip(*pairs) chuyển các cặp thành các dãy tương ứng nếu cấu trúc phù hợp. any và all kiểm tra tồn tại/mọi phần tử; trên dãy rỗng, any([]) là False, all([]) là True. reversed, sorted(key=...), map, filter cung cấp những cách duyệt hoặc biến đổi; ưu tiên vòng lặp thường khi comprehension trở nên khó đọc hay cần nhiều trạng thái.

Chương 33. Tệp văn bản và đường dẫn

Biến trong bộ nhớ mất sau khi chương trình kết thúc; tệp lưu dữ liệu bền vững. Đường dẫn tương đối được diễn giải theo thư mục làm việc hiện tại, còn đường dẫn tuyệt đối chỉ rõ vị trí từ gốc hệ tệp. Khi làm việc với văn bản tiếng Việt, chỉ định encoding="utf-8" để tránh phụ thuộc thiết lập mặc định của môi trường.

from pathlib import Path

path = Path("data.txt")
with path.open("w", encoding="utf-8") as f:
    f.write("Xin chào\n")

with path.open("r", encoding="utf-8") as f:
    for line in f:
        print(line.rstrip("\n"))

Chế độ r đọc; w ghi và xóa nội dung cũ nếu tệp đã tồn tại; a ghi nối tiếp. read() lấy toàn bộ nội dung; readline() lấy một dòng; readlines() tạo list các dòng, thường vẫn chứa ký tự xuống dòng. writelines không tự thêm \n. with quản lý việc đóng tệp kể cả khi phát sinh ngoại lệ; đối tượng tệp có vị trí đọc/ghi hiện tại, có thể tìm hiểu qua tell và seek khi cần.

Chương 34. Xử lý dữ liệu tệp

Quy trình xử lý là đọc đúng định dạng, loại ký tự không cần thiết, chuyển kiểu, tính toán, rồi ghi kết quả. Có thể duyệt từng dòng khi tệp lớn thay vì read() toàn bộ. Dòng trống, tệp rỗng và dữ liệu sai định dạng phải có quy tắc xử lý riêng; không mặc định max() có thể gọi trên danh sách rỗng.

from pathlib import Path

freq = {}
with Path("input.txt").open("r", encoding="utf-8") as f:
    for line in f:
        for word in line.split():
            word = word.casefold()
            freq[word] = freq.get(word, 0) + 1

with Path("output.txt").open("w", encoding="utf-8") as f:
    for word in sorted(freq):
        f.write(f"{word} {freq[word]}\n")

Đếm dòng cần phân biệt số dòng vật lý với số dòng không rỗng; đếm từ phụ thuộc quy tắc tách từ; đếm ký tự có thể bao gồm hoặc loại \n theo đặc tả. Lọc dòng, đánh số dòng, tìm từ khóa, thay thế nội dung và ghép tệp đều nên xử lý theo từng dòng khi có thể. Nếu cần ghi thay thế, ưu tiên tạo tệp mới rồi kiểm tra trước khi ghi đè tệp gốc.

Chương 35. Ngoại lệ và kiểm tra tính hợp lệ

Lỗi cú pháp khiến chương trình không phân tích được; ngoại lệ (exception) phát sinh khi thực thi; lỗi logic khiến kết quả sai dù chương trình vẫn chạy. try/except bắt các ngoại lệ dự kiến như ValueError, FileNotFoundError và ZeroDivisionError. Nhánh else chạy khi try hoàn tất mà không có ngoại lệ, còn finally dùng cho công việc cần thực hiện khi rời cấu trúc.

while True:
    try:
        n = int(input("Nhập số nguyên dương: "))
        if n <= 0:
            raise ValueError("Số phải dương")
    except ValueError as e:
        print("Dữ liệu không hợp lệ:", e)
    else:
        break

Bắt ngoại lệ cụ thể, tránh except: quá rộng làm che lỗi lập trình. Dùng raise ValueError(...) khi dữ liệu vi phạm hợp đồng; assert dùng để kiểm tra giả định nội bộ chứ không thay kiểm tra dữ liệu người dùng. Các lời nhắc và thông báo lỗi ví dụ trên phù hợp chương trình tương tác; không xuất chúng trong lời giải OJ nếu đề chỉ yêu cầu kết quả.

PHẦN IX. MODULE VÀ TỔ CHỨC CHƯƠNG TRÌNH

Chương 36. Dữ liệu CSV và JSON cơ bản

CSV lưu dữ liệu dạng hàng và cột theo một dấu phân cách; không nên tự split(",") nếu trường có dấu phẩy hoặc dấu nháy nằm bên trong. Module csv hỗ trợ đọc/ghi, xử lý trích dẫn và dòng tiêu đề. Giá trị đọc từ CSV thông thường là chuỗi, cần chuyển kiểu nếu muốn tính toán.

import csv

with open("students.csv", newline="", encoding="utf-8") as f:
    for row in csv.DictReader(f):
        name = row["name"]
        score = float(row["score"])
        print(name, score)

csv.reader trả từng hàng dạng list; DictReader ánh xạ tên cột sang giá trị. writer ghi hàng dạng dãy; DictWriter ghi hàng dạng dictionary theo danh sách trường đã khai báo. Khi mở CSV, thường dùng newline="" để module tự xử lý xuống dòng.

JSON biểu diễn đối tượng, mảng, chuỗi, số, Boolean và null; tương ứng phổ biến ở Python là dict, list, str, int/float, bool, None. json.load/dump làm việc với tệp; json.loads/dumps làm việc với chuỗi.

import json

record = {"ten": "An", "diem": 8.5}
with open("record.json", "w", encoding="utf-8") as f:
    json.dump(record, f, ensure_ascii=False, indent=2)

with open("record.json", encoding="utf-8") as f:
    loaded = json.load(f)
print(loaded.get("diem"))

ensure_ascii=False giúp giữ chữ tiếng Việt ở dạng dễ đọc trong tệp UTF-8; indent thêm thụt lề. Khi thiếu khóa, dùng get, kiểm tra in hoặc báo lỗi theo đặc tả. JSON không cho phép tùy ý lưu mọi đối tượng Python, chẳng hạn một instance tự định nghĩa nếu chưa chuyển nó thành dữ liệu tương thích.

Chương 37. Mô-đun (module) và thư viện chuẩn

Module thường là tệp .py chứa hàm, biến và lớp có thể tái sử dụng. import math giữ tên trong không gian tên math; from math import sqrt nhập một tên cụ thể; as đặt bí danh. Ưu tiên cách viết giúp biết tên xuất phát từ đâu và tránh xung đột tên.

import math
from statistics import mean
import random as rnd

print(math.isqrt(25))
print(mean([2, 4, 6]))
print(rnd.randint(1, 6))

Khi chạy trực tiếp một tệp, __name__ thường là "__main__"; khi được import, nó là tên module. Nhờ đó mã thử hoặc điểm vào chương trình chỉ chạy khi chạy trực tiếp:

def main():
    print("Chương trình bắt đầu")

if __name__ == "__main__":
    main()

Các module trọng tâm trong lộ trình gồm math, random, statistics, datetime, pathlib, string, collections. Dùng help() và dir() để tra cứu hoặc xem tài liệu trong Thonny; tên một tệp tự viết như random.py có thể che khuất module chuẩn cùng tên.

PHẦN X. LẬP TRÌNH HƯỚNG ĐỐI TƯỢNG VÀ ĐỆ QUY

Chương 38. Tổ chức chương trình và môi trường dự án

Khi chương trình dài hơn một tệp, tách logic nghiệp vụ, nhập/xuất, cấu hình và kiểm thử. Package tổ chức nhiều module trong một thư mục; __init__.py có thể dùng để đánh dấu package thường gặp và tổ chức giao diện import. Tránh import vòng: hai module phụ thuộc nhau ngay khi khởi tạo có thể khiến tên chưa được định nghĩa đúng lúc.

tệp xử lý:
    định nghĩa các hàm tính toán nhận tham số và trả kết quả

tệp giao diện:
    đọc dữ liệu người dùng
    gọi các hàm xử lý
    hiển thị kết quả

tệp kiểm thử:
    gọi trực tiếp từng hàm xử lý bằng dữ liệu xác định

Điểm vào dùng if __name__ == "__main__": để phân biệt chạy trực tiếp với import. Môi trường ảo (virtual environment) cô lập các gói của dự án; pip cài gói, còn requirements.txt thường ghi tên và phiên bản gói cần thiết. Thư viện chuẩn có sẵn theo bản phân phối Python; thư viện bên thứ ba cần cài thêm. Kiểm tra trình thông dịch đang được Thonny chọn trước khi kết luận gói đã được cài đúng môi trường.

Chương 39. Lập trình hướng đối tượng cơ bản

Lớp (class) mô tả dữ liệu và hành vi chung; đối tượng (instance) là một thực thể cụ thể của lớp. __init__ khởi tạo trạng thái; self tham chiếu instance đang nhận lời gọi. Thuộc tính (attribute) lưu dữ liệu, phương thức (method) biểu diễn hành vi.

class Student:
    school = "Truong A"                 # thuộc tính class

    def __init__(self, name, score):
        self.name = name                 # thuộc tính instance
        self.score = score

    def passed(self):
        return self.score >= 5

    def __str__(self):
        return f"{self.name}: {self.score}"

s = Student("An", 8)
print(s.passed(), s)

Mỗi đối tượng có thể giữ trạng thái riêng. Thuộc tính class được chia sẻ ở cấp lớp nếu instance chưa che khuất bằng thuộc tính cùng tên. __str__ tạo chuỗi thân thiện khi xuất, __repr__ cung cấp biểu diễn dành cho người lập trình ở mức giới thiệu. List đối tượng thích hợp khi duyệt toàn bộ; dictionary ánh xạ mã định danh sang đối tượng khi cần tra cứu theo khóa.

Chương 40. Thiết kế lớp, đóng gói và kế thừa

Thiết kế lớp từ trách nhiệm: gom trạng thái và thao tác liên quan trong cùng một nơi, kiểm tra điều kiện hợp lệ khi khởi tạo hoặc cập nhật. Dấu _name thể hiện quy ước thuộc tính nội bộ, không phải cơ chế bảo mật tuyệt đối. @property cho phép kiểm soát việc đọc và gán một thuộc tính bằng giao diện giống truy cập dữ liệu.

class BankAccount:
    def __init__(self, balance=0):
        self.balance = balance

    @property
    def balance(self):
        return self._balance

    @balance.setter
    def balance(self, value):
        if value < 0:
            raise ValueError("Số dư không được âm")
        self._balance = value

Quan hệ has-a thường dùng composition: một đối tượng chứa đối tượng khác; quan hệ is-a có thể dùng inheritance: lớp con kế thừa từ lớp cha. super().__init__() gọi phần khởi tạo của lớp cha; ghi đè phương thức (override) thay đổi hành vi ở lớp con. Đa hình (polymorphism) cho phép dùng những đối tượng khác lớp thông qua cùng giao diện thao tác. Không dùng kế thừa chỉ để tái sử dụng vài dòng mã khi hai thực thể không có quan hệ kiểu hợp lý; kiểm thử từng phương thức và trường hợp trạng thái không hợp lệ.

PHẦN XI. GỠ LỖI, KIỂM THỬ VÀ HIỆU QUẢ

Chương 41. Đệ quy cơ bản

Đệ quy (recursion) là cách hàm giải bài toán bằng lời gọi chính nó trên bài toán nhỏ hơn. Phải có trường hợp cơ sở (base case) không gọi tiếp và bước đệ quy tiến gần trường hợp cơ sở. Mỗi lời gọi có trạng thái cục bộ trong ngăn xếp lời gọi (call stack); khi quay về, kết quả được ghép theo chiều ngược.

def giai_thua(n):
    if n <= 1:
        return 1
    return n * giai_thua(n - 1)

Truy vết giai_thua(4): lời gọi đi xuống $4\to3\to2\to1$, sau đó kết quả đi lên $1\to2\to6\to24$. Với Fibonacci trực tiếp, nhiều lời gọi lặp lại cùng bài toán nên tốc độ giảm mạnh khi $n$ lớn. Python có giới hạn độ sâu đệ quy; bài có độ sâu rất lớn thường thích hợp với vòng lặp hoặc kỹ thuật khác.

hàm đệ_quy(trạng_thái):
    nếu gặp trường hợp cơ sở:
        trả ngay kết quả cơ sở
    tạo trạng thái nhỏ hơn
    lấy kết quả bằng lời gọi đệ quy
    kết hợp và trả kết quả

Quay lui (backtracking) ở mức nhập môn: thử lần lượt một lựa chọn, gọi đệ quy cho phần còn lại, rồi hoàn tác lựa chọn nếu đã sửa trạng thái chung. Ví dụ sinh chuỗi nhị phân dài $n$: ở mỗi vị trí thử 0 rồi 1, khi đủ $n$ ký tự thì xử lý một chuỗi hoàn chỉnh.

Chương 42. Phương pháp gỡ lỗi có hệ thống

Phân biệt thông báo lỗi với nguyên nhân thật. SyntaxError liên quan cú pháp; IndentationError liên quan khối lệnh; NameError tên không tồn tại; TypeError thao tác sai kiểu; ValueError giá trị không hợp lệ; IndexError, KeyError truy cập thiếu; ZeroDivisionError, FileNotFoundError, RecursionError diễn tả các tình huống tương ứng.

đọc traceback từ dòng thông báo cuối lên vị trí phát sinh
xác định dữ liệu làm lỗi xuất hiện
rút gọn dữ liệu tới ví dụ nhỏ nhất vẫn gây lỗi
kiểm tra trạng thái ngay trước thao tác sai
sửa nguyên nhân, không chỉ che thông báo
chạy lại cả trường hợp lỗi và bộ kiểm thử cũ

Thonny cho phép chạy từng bước, quan sát biến, biểu thức và luồng gọi hàm. print giá trị trung gian chỉ hữu ích khi biết đang kiểm tra giả thuyết nào; không để các dòng debug làm sai dữ liệu ra trên OJ. assert có thể phát hiện giả định bị vi phạm trong quá trình phát triển.

Chương 43. Kiểm thử chương trình

Ca kiểm thử (test case) gồm dữ liệu vào và kết quả mong đợi. Kiểm thử trường hợp bình thường (happy path), cận (boundary), đặc biệt (edge case), rỗng, một phần tử, trùng lặp, số âm/0/dương nếu hợp lệ, dữ liệu đã sắp xếp và đảo ngược. Một bộ kiểm thử tốt nhắm tới nhánh dễ sai, không chỉ tập hợp nhiều ví dụ ngẫu nhiên.

def is_even(n):
    return n % 2 == 0

assert is_even(0)
assert is_even(-2)
assert not is_even(3)

doctest kiểm tra ví dụ nằm trong docstring; unittest tổ chức ca kiểm thử thành phương thức kiểm thử độc lập. Muốn kiểm thử thuận tiện, nên tách hàm tính toán khỏi input() và print(). Với thuật toán tối ưu, có thể tạo test nhỏ, giải bằng cách vét cạn độc lập rồi đối chiếu kết quả; sự khác biệt cho biết ít nhất một cách cài đặt hoặc giả định đang sai.

PHẦN XII. THUẬT TOÁN CƠ BẢN VÀ KỸ THUẬT CHUYỂN TIẾP

Chương 44. Độ phức tạp tính toán và hiệu quả chương trình

Độ phức tạp thời gian mô tả tốc độ tăng của số thao tác theo kích thước dữ liệu $n$, còn độ phức tạp không gian mô tả bộ nhớ bổ sung. Ký hiệu $O(\cdot)$ biểu diễn cận trên tiệm cận; trong đánh giá sơ bộ thường bỏ hằng số và số hạng bậc thấp. Một vòng duyệt là $O(n)$, hai vòng lồng nhau mỗi vòng dài $n$ là $O(n^2)$, mỗi bước chia đôi miền tìm kiếm cho $O(\log n)$.

list.append ở cuối có chi phí khấu hao $O(1)$; truy cập a[i] là $O(1)$; kiểm tra x in list là $O(n)$ trong trường hợp xấu nhất; kiểm tra set hoặc tra cứu dict trung bình thường là $O(1)$, không bảo đảm mọi trường hợp. Việc chèn/xóa ở đầu list cần dịch chuyển phần tử. Đọc giới hạn dữ liệu để biết thuật toán $O(n^2)$ có hợp lý không; đồng thời tính cả bộ nhớ tạo thêm, đặc biệt với ma trận và danh sách trung gian.

Chương 45. Các thuật toán tìm kiếm cơ bản

Tìm kiếm tuyến tính (linear search) kiểm tra lần lượt từng phần tử, không đòi hỏi dữ liệu đã sắp xếp; xấu nhất $O(n)$. Muốn vị trí đầu tiên thì return ngay khi thấy, muốn vị trí cuối cùng thì ghi đè đáp án khi gặp tiếp, muốn tất cả vị trí thì thêm vào danh sách.

def tim_dau(a, x):
    for i, value in enumerate(a):
        if value == x:
            return i
    return -1

Tìm kiếm nhị phân (binary search) cần dữ liệu đã sắp xếp theo thứ tự đang dùng hoặc một điều kiện đơn điệu được chứng minh. Với đoạn chỉ số đóng [left, right], so sánh phần tử giữa mid rồi bỏ nửa chắc chắn không chứa đáp án. Mỗi bước làm giảm khoảng tìm kiếm, độ phức tạp $O(\log n)$.

left = 0; right = n - 1
trong khi left <= right:
    mid = (left + right) // 2
    nếu a[mid] bằng giá trị cần tìm: trả mid
    nếu a[mid] nhỏ hơn giá trị cần tìm: left = mid + 1
    ngược lại: right = mid - 1
trả -1

def tim_nhi_phan(a, x):
    left, right = 0, len(a) - 1
    while left <= right:
        mid = (left + right) // 2
        if a[mid] == x:
            return mid
        if a[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return -1

bisect_left trong module bisect trả vị trí chèn trước các phần tử bằng nhau; bisect_right trả vị trí chèn sau chúng. Không dùng tìm kiếm nhị phân trên dãy chưa sắp xếp mà chưa có tính đơn điệu phù hợp.

Chương 46. Thuật toán sắp xếp cơ bản

Nổi bọt (bubble sort) đổi chỗ các cặp kề nhau sai thứ tự; sau mỗi lượt, một phần tử lớn dần về cuối. Sắp xếp chọn (selection sort) tìm phần tử nhỏ nhất trong đoạn chưa sắp rồi đổi vào đầu đoạn. Sắp xếp chèn (insertion sort) lấy phần tử tiếp theo và chèn vào đúng vị trí trong phần đầu đã sắp. Cả ba có thời gian $O(n^2)$ trong trường hợp xấu nhất; nổi bọt có thể dừng sớm nếu một lượt không có đổi chỗ.

nổi bọt tăng dần:
    với mỗi lượt từ 0 đến n - 2:
        chưa có đổi chỗ
        duyệt từng cặp kề nhau thuộc phần chưa ổn định:
            nếu cặp sai thứ tự thì đổi chỗ
        nếu không có đổi chỗ thì dừng

def bubble_sort(a):
    a = a.copy()
    n = len(a)
    for end in range(n - 1, 0, -1):
        changed = False
        for j in range(end):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                changed = True
        if not changed:
            break
    return a

Sắp xếp trộn (merge sort) chia dãy, sắp mỗi nửa rồi trộn hai nửa đã sắp; thời gian $O(n\log n)$ và thường cần bộ nhớ phụ $O(n)$. Sắp xếp nhanh (quicksort) chia dữ liệu theo phần tử chốt rồi xử lý hai phía; đây là ý tưởng chuyển tiếp, không phải lựa chọn mặc định cho mọi dữ liệu. Khi bài chỉ cần sắp xếp, ưu tiên sorted() hoặc list.sort() của Python thay vì tự cài đặt thuật toán học thuật. Tính ổn định nghĩa là các phần tử có khóa bằng nhau giữ thứ tự tương đối ban đầu.

Chương 47. Các kỹ thuật xử lý dãy ở mức chuyển tiếp

Tổng tiền tố (prefix sum) biến truy vấn tổng đoạn thành hiệu của hai tổng tích lũy. Với mảng $a$ dài $n$, đặt $p[0]=0$ và $p[i+1]=p[i]+a[i]$. Khi đó tổng đoạn gồm cả hai đầu $[l,r]$ là:

a = [3, 1, 4, 1, 5]
p = [0]
for x in a:
    p.append(p[-1] + x)
print(p[4] - p[1])  # tổng a[1..3] = 6

Mảng đếm tiền tố có thể xây tương tự, thay mỗi phần tử bởi 1 nếu thỏa điều kiện, ngược lại 0. Hai con trỏ (two pointers) từ hai đầu hữu ích khi dãy đã sắp và điều kiện cho phép quyết định bỏ đầu nào; hai con trỏ cùng chiều dùng khi mỗi con trỏ chỉ tiến về trước. Gộp hai dãy đã sắp: so sánh hai phần tử hiện tại, lấy phần tử nhỏ hơn rồi tăng con trỏ tương ứng; tổng thời gian $O(n+m)$.

l = 0; r = n - 1
trong khi l < r:
    xét tổng a[l] + a[r]
    nếu đã đạt mục tiêu: xử lý cặp và dừng hoặc tiếp tục theo đề
    nếu tổng quá nhỏ: tăng l
    nếu tổng quá lớn: giảm r

Cửa sổ trượt (sliding window) cố định độ dài $k$: tính tổng $k$ phần tử đầu, sau mỗi bước cộng phần tử mới và trừ phần tử rời cửa sổ. Thời gian $O(n)$ thay vì tính lại từng cửa sổ trong $O(nk)$.

def tong_lon_nhat_k(a, k):
    if not 1 <= k <= len(a):
        raise ValueError("k phải từ 1 đến độ dài danh sách")
    current = sum(a[:k])
    best = current
    for i in range(k, len(a)):
        current += a[i] - a[i - k]
        best = max(best, current)
    return best

Cửa sổ biến đổi chỉ dùng khi có điều kiện cho phép di chuyển cận trái mà không bỏ lỡ lời giải, chẳng hạn tổng các số không âm so với một giới hạn thích hợp. Nếu dãy có số âm, không mặc định áp dụng cùng quy tắc. Đây là phần chuyển tiếp từ vòng lặp cơ bản sang thiết kế thuật toán dựa vào ràng buộc.

PHẦN XIII. LUYỆN TẬP, DỰ ÁN THỰC HÀNH VÀ ĐỒ ÁN

Chương 48. Hệ thống bài tập tổng hợp Python cơ bản

Khi gặp một bài tổng hợp, nhận diện dạng xử lý chính trước khi chọn cấu trúc: nhập–tính–xuất; điều kiện nhiều trường hợp; mô phỏng; đếm/tích lũy; chữ số và số học; chuỗi; danh sách và tần suất; ma trận; tệp và dictionary; tìm kiếm, sắp xếp, tiền tố hoặc hai con trỏ. Một bài có thể cần kết hợp nhiều mẫu, nhưng không nên dùng cấu trúc phức tạp khi vòng lặp đơn giản đã đáp ứng giới hạn.

đọc kỹ định dạng dữ liệu và giới hạn
xác định biến/trạng thái cần duy trì
chọn mẫu xử lý trực tiếp phù hợp
xử lý trường hợp rỗng, một phần tử và giá trị biên
cài đặt phần xử lý thành hàm nếu phù hợp
kiểm tra bằng ví dụ nhỏ và so sánh với kết quả mong đợi

Khi bài dùng nhiều kỹ thuật, xác định thứ tự phụ thuộc giữa các bước: chuẩn hóa trước khi đếm; sắp xếp trước khi dùng hai con trỏ trên dãy đã sắp; tạo prefix sum trước khi trả lời truy vấn; xác thực dữ liệu trước phép chia. Độ phức tạp của toàn chương trình phải tính cả tiền xử lý và các vòng lặp truy vấn.

Chương 49. Dự án thực hành theo tiến trình học tập

Dự án thực hành kết hợp các kiến thức đã học thành chương trình sử dụng được: giao diện dòng lệnh (console), hàm xử lý, cấu trúc dữ liệu, kiểm tra đầu vào và lưu dữ liệu khi cần. Các lĩnh vực trong lộ trình bao gồm phép tính, trò chơi theo quy tắc, phân tích số và chuỗi, mã hóa đơn giản, quản lý bản ghi, phân tích tệp và quản lý đối tượng. Trọng tâm không phải tăng số tính năng bằng mọi giá mà là giữ mỗi nhiệm vụ rõ ràng, có thể kiểm thử.

xác định dữ liệu và các thao tác chương trình cần hỗ trợ
biểu diễn dữ liệu bằng list, dictionary hoặc class cho phù hợp
viết hàm xử lý độc lập với nhập/xuất
xây dựng vòng lặp điều khiển chức năng của ứng dụng
kiểm tra dữ liệu trước khi thay đổi trạng thái
lưu/tải dữ liệu khi bài toán cần duy trì giữa các lần chạy

Nếu dùng dữ liệu ngẫu nhiên, có thể cố định hạt giống trong kiểm thử để tái hiện hành vi. Nếu lưu JSON/CSV, xác định rõ cấu trúc trường và cách xử lý trường bị thiếu. Chức năng quan trọng nên có ca kiểm thử trực tiếp trước khi kết nối với giao diện.

Chương 50. Đồ án cuối khóa và đánh giá chuẩn đầu ra

Đồ án là một chương trình giải quyết bài toán vừa sức, có mục tiêu và đặc tả rõ ràng. Phải mô tả dữ liệu vào, dữ liệu ra, quy tắc hợp lệ, các chức năng và cấu trúc dữ liệu trước khi cài đặt. Làm phiên bản tối thiểu chạy đúng trước, sau đó mới bổ sung giao diện, lưu dữ liệu và cải tiến cấu trúc.

xác định người dùng và mục tiêu chương trình
viết đặc tả dữ liệu và hành vi cho từng chức năng
chia công việc thành module và các hàm độc lập
mô tả thuật toán chính bằng mã giả
cài đặt phiên bản tối thiểu
kiểm thử đơn vị từng phần rồi kiểm thử tích hợp
xử lý đầu vào không hợp lệ và tình huống biên
loại bỏ mã lặp, chuẩn hóa tên, bổ sung docstring cần thiết
kiểm tra tính đúng, chi phí thời gian và bộ nhớ
trình bày được lý do chọn thuật toán và cấu trúc dữ liệu

Kết quả cuối khóa không chỉ là chạy đúng một bộ dữ liệu mẫu. Người học cần đọc hiểu mã đã viết, giải thích biến trạng thái, truy vết luồng xử lý, xác định nguyên nhân lỗi, thiết kế dữ liệu kiểm thử mới và nhận biết khi nào cần nâng cấp từ giải pháp cơ bản sang cấu trúc dữ liệu hoặc thuật toán hiệu quả hơn.