Thuật toán và lập trình Python: máy đọc từng dòng lệnh, năm chặng từ trạng thái đến độ phức tạp | LUKATO AI
Khung năm chặng cho Tin học 11–12: đọc từng dòng lệnh Python qua trạng thái, quyết định, lặp, gọi và đo, với 17 phòng lab, 14 bẫy và 12 bài chọn lọc.
LUKATO AI · TIN HỌC 11–12 · THUẬT TOÁN VÀ LẬP TRÌNH PYTHON
MÁY ĐỌC TỪNG DÒNG LỆNH · NĂM CHẶNG
Một chương trình là danh sách dòng lệnh; máy làm hai việc: đọc một dòng, rồi sửa bảng trạng thái
- Sau dòng tong = tong + 1 , vì sao máy không báo “vô nghiệm” như với một phương trình?
- range(1, 6) chạy mấy vòng, và vì sao số 6 vắng mặt trong dãy?
- Tìm một mã trong danh sách đã sắp xếp gồm một triệu mã, máy cần xét vài trăm nghìn lần hay khoảng hai mươi lần?
Chuyên đề này gom các bài về Python (biến, rẽ nhánh, vòng lặp, chuỗi và danh sách, hàm và đệ quy, tìm kiếm, sắp xếp, độ phức tạp) vào một khung năm chặng : trạng thái, quyết định, lặp, gọi, đo. Em sẽ lần vết từng dòng, đoán kiểu của biểu thức, chia hộp bi, lần theo nhánh if, bắt lỗi, lắp chương trình, cắt chuỗi, tách hai tên khỏi một danh sách, xếp ngăn xếp lời gọi, so sánh hai cách tìm kiếm và xem các thuật toán sắp xếp chạy từng bước. Điều nào vượt ra ngoài chương trình được ghi là kiến thức bổ sung; ngôn ngữ chính là Python, còn C++ được nhắc ở những chỗ cú pháp khác nhau rõ rệt.
- ① 5 CHẶNG: trạng thái, quyết định, lặp, gọi, đo
- ② 3 CÂU HỎI: bảng biến lúc này? dòng nào chạy tiếp? tốn bao nhiêu bước?
- ③ 5 VẬT LIỆU: số, giá trị logic, chuỗi, danh sách, hàm
- ④ QUY ƯỚC: Python 3; số liệu trong ví dụ là số liệu minh họa
17
phòng lab thao tác: lần vết, phân loại, kéo thả, bắt lỗi, lắp ráp, trò chơi, ngăn xếp, tìm kiếm, sắp xếp…
14 bẫy
mỗi bẫy gắn với một chặng và một phòng lab
10 thẻ
thẻ ôn nhanh để lật và tự hỏi lại
12 bài
bài luyện chọn lọc và báo cáo học tập của riêng em
01
Bản đồ chuyên đề
Máy đọc từng dòng lệnh: cuốn sổ trạng thái và năm chặng
Một chương trình Python là danh sách dòng lệnh. Máy không “hiểu” chương trình như con người; nó làm đúng hai việc lặp đi lặp lại: đọc một dòng, rồi sửa một cuốn sổ ghi nhớ. Rẽ nhánh, vòng lặp, hàm và đệ quy đều là những cách quyết định dòng nào được đọc tiếp. Mục này vẽ bản đồ cho cả chuyên đề.
Câu hỏi 1 · TRẠNG THÁI
Bảng biến lúc này ghi gì?
Sau mỗi dòng vừa chạy, mỗi biến có một tên, một kiểu và một giá trị. Lần vết chương trình là viết lại bảng ấy sau từng dòng, không đoán từ kết quả cuối.
Câu hỏi 2 · DÒNG KẾ TIẾP
Dòng nào được đọc tiếp?
Bình thường là dòng ngay bên dưới. Rẽ nhánh nhảy qua một đoạn, vòng lặp quay về phía trên, lời gọi hàm nhảy vào hàm rồi trở lại đúng chỗ đã đi.
Câu hỏi 3 · CHI PHÍ
Tốn bao nhiêu bước khi dữ liệu lớn lên?
Chương trình đúng chưa chắc dùng được. Đếm số lần dòng lệnh quan trọng được đọc theo cỡ dữ liệu n để biết chương trình có chịu nổi dữ liệu lớn hay không.
Năm chặng của máy đọc từng dòng
Hãy tưởng tượng một người đọc rất ngoan, rất chậm, ngồi trước tờ danh sách dòng lệnh. Người ấy có một cuốn sổ ghi giá trị của từng biến và một ngón tay chỉ vào dòng đang đọc. Mỗi lần đọc xong một dòng, người ấy sửa sổ (nếu dòng ấy có gán) rồi quyết định dời ngón tay đi đâu. Các khái niệm của chủ đề này nằm trong hai động tác ấy:
① TRẠNG THÁI Cuốn sổ: tên, kiểu và giá trị của các biến. Phép gán sửa sổ.
② QUYẾT ĐỊNH if–elif–else: ngón tay nhảy qua các nhánh không được chọn.
③ LẶP for, while: ngón tay quay lại phía trên cho đến khi điều kiện dừng.
④ GỌI Hàm, đệ quy: ngón tay nhảy vào hàm, mở một trang sổ mới, xong thì trở về.
⑤ ĐO Đếm số lần ngón tay đã chỉ vào dòng quan trọng khi dữ liệu có n phần tử.
Ba chặng ②③④ là ba cách khác nhau để điều khiển ngón tay ; chặng ① là thứ ngón tay làm thay đổi; chặng ⑤ là phép đếm công sức. Cách chia này là cách phân loại của LUKATO để gom các bài lại; nó không thay thế các tên gọi trong chương trình học (cấu trúc tuần tự, rẽ nhánh, lặp).
↔ Hình rộng hơn màn hình: vuốt ngang để xem đầy đủ.
Hình 1.1. Máy đọc từng dòng: ngón tay chỉ vào dòng đang đọc, cuốn sổ ghi trạng thái. Mũi tên cam là rẽ nhánh, mũi tên xanh lá là vòng lặp quay lại, mũi tên tím là lời gọi hàm rồi trở về.
Bản đồ: năm vật liệu nhân năm chặng
Chương trình thao tác trên năm loại “vật liệu”: số, giá trị logic, chuỗi, danh sách, và hàm (hàm cũng là một thứ được định nghĩa, được gọi và được truyền đi). Mỗi ô của bảng nói vật liệu ấy xuất hiện thế nào ở chặng ấy. Bảng này là bản đồ của cả chuyên đề : mục 2 đi qua chặng trạng thái, mục 3 qua quyết định, mục 4 qua lặp, mục 5 đi sâu vào chuỗi và danh sách, mục 6 qua chặng gọi, mục 7 qua chặng đo.
VẬT LIỆU
① TRẠNG THÁI
② QUYẾT ĐỊNH
③ LẶP
④ GỌI
⑤ ĐO
Số
Giá trị logic
Chuỗi
Danh sách
Hàm
↔ Bảng rộng hơn màn hình: vuốt ngang để xem đủ năm chặng.
Bấm vào một ô để xem ô ấy nói gì, nằm ở bẫy nào và luyện ở phòng lab nào.
Mười thuật ngữ nền
Các thuật ngữ gạch chân chấm trong chuyên đề là thẻ giải nghĩa: bấm hoặc rê chuột để xem. Em thử với các từ dưới đây.
biến phép gán kiểu dữ liệu biểu thức điều kiện vòng lặp hàm đệ quy ngăn xếp lời gọi độ phức tạp
Bắt đầu bằng một cuốn sổ
Ba dòng gán và một dòng in dưới đây nhìn rất giản dị nhưng chứa cả bài học: máy dựa vào những gì cuốn sổ đang ghi, còn giá trị cũ thì máy quên . Lịch sử đã chạy qua không còn nằm đâu ngoài giá trị hiện tại của các biến.
a = 12
b = a + 3
a = 1
print(b)
Chạy đoạn trên, dòng cuối in ra số nào?
Phòng lab 1 · Máy đọc từng dòng DẠNG: LẦN VẾT TỪNG BƯỚC · BẢNG TRẠNG THÁI
Dự đoán, rồi bấm Tiếp. Chọn một chương trình, nhìn dòng đang được tô màu và đoán trước bảng biến sẽ đổi thế nào, rồi bấm “Tiếp” để máy chạy dòng ấy. Có thể bấm “Phát” để máy tự chạy. Lab này gặp bẫy 1 .
Vì sao một khung cho cả chuyên đề
Bề ngoài, các bài tập lập trình rất khác nhau: lần vết một đoạn mã, sửa lỗi vòng lặp, viết hàm đệ quy, chọn thuật toán tìm kiếm. Nhưng bài nào cũng quy về ba câu hỏi ở đầu mục. Khi đọc một đoạn mã, hãy gọi tên chặng đang bị hỏi (trạng thái, quyết định, lặp, gọi hay đo), rồi trả lời câu hỏi tương ứng bằng bảng trạng thái hoặc bằng phép đếm.
Python và C++
Ý tưởng của năm chặng giống nhau ở hai ngôn ngữ; cú pháp khác nhau. Chẳng hạn C++ khai báo kiểu của biến ( int x = 5; ) và đánh dấu khối lệnh bằng cặp ngoặc nhọn, còn Python suy ra kiểu từ giá trị và dùng thụt lề để chia khối. Phần còn lại của chuyên đề dùng Python.
Sau khi chạy xong hai dòng đầu của đoạn “so_kien = 2; so_kien = so_kien * so_kien + 1”, cuốn sổ ghi so_kien bằng bao nhiêu? Em tự trả lời trước rồi mở từng gợi ý.
Gợi ý 1
Sau dòng đầu, so_kien là 2. Khi dòng thứ hai chạy, máy tính vế phải trước bằng giá trị so_kien đang có trong sổ.
Gợi ý 2
Vế phải là 2\cdot2+1=5. Sau khi tính xong, máy mới ghi 5 đè lên giá trị cũ của so_kien.
Kết luận
so_kien bằng 5. Dòng gán không phải phương trình “x=x\cdot x+1” (phương trình ấy vô nghiệm thực); nó là hai động tác nối nhau: tính vế phải, rồi ghi vào ô bên trái.
02
Chặng ① · Trạng thái
Biến, kiểu dữ liệu và phép toán: cuốn sổ của máy
Một chương trình bắt đầu bằng việc ghi nhớ. Biến là tên gắn với một ô nhớ; kiểu cho biết ô ấy chứa loại giá trị gì; phép gán là cách để sửa sổ ở mức bài này. Mục này làm rõ ba điều: dòng gán chạy thế nào, kiểu quyết định phép toán ra sao, và ba phép chia khác nhau ở đâu.
Hãy đứng ở quầy của một bưu cục nhỏ (tình huống minh họa, số liệu minh họa). Nhân viên nhập số kiện của một khách, nhân với giá mỗi kiện rồi in tổng tiền. Ba dòng ấy là “bộ nhớ” mà máy cần cho bài này: một vài biến , mỗi biến có tên , kiểu và giá trị . Hiểu thật chắc ba thứ ấy và cách một dòng lệnh sửa chúng là nền cho các chặng sau.
Biến và phép gán: máy ghi vào sổ, không lập phương trình
Câu lệnh tên = biểu thức làm hai việc theo đúng thứ tự: tính biểu thức ở bên phải bằng các giá trị đang có trong sổ, rồi ghi kết quả vào ô nhớ có tên ở bên trái (nếu ô chưa có thì lập ô mới). Vì thế so_kien = so_kien + 1 hợp lệ: vế phải dùng giá trị cũ, vế trái nhận giá trị mới.
so_kien = 3
phi = 15000
tong = so_kien * phi
so_kien = so_kien + 1
print(tong, so_kien)
In ra
45000 4
↔ Hình rộng hơn màn hình: vuốt ngang để xem đầy đủ.
Hình 2.1. Cuốn sổ sau từng dòng của đoạn mã: ô được tô vàng là ô vừa bị sửa. Dòng thứ tư sửa so_kien nhưng không sửa tong.
Quan sát hình: sau dòng thứ ba, tong là 45000. Dòng thứ tư làm so_kien thành 4, nhưng tong vẫn là 45000 và in ra như vậy. Người đã quen bảng tính (ô tong tự cập nhật khi ô so_kien đổi) dễ thất vọng ở chỗ này. Trong Python, dòng gán là một sự kiện xảy ra một lần, tại lúc dòng ấy được đọc; nó không tạo ra một mối liên hệ kéo dài.
Bẫy 1 · gán là một sự kiện, không phải đẳng thức
Đọc y = x là “y nhận giá trị hiện tại của x”, không phải “y đi theo x”. Muốn hỏi hai giá trị có bằng nhau không, dùng == (hai dấu bằng) và nhận về True hoặc False. Nhầm hai dấu này là một trong những lỗi gặp nhiều nhất khi mới học lập trình.
Gặp ở: Lab 1 và 5 · Bài 1
x = 6
y = x
x = x + 5
y = y * 2
print(x, y)
In ra
11 12
Lần vết đoạn trên: x là 6; y nhận 6; x thành 6+5=11; y thành 6\cdot2=12. In ra 11 12 . Hai ô nhớ sống riêng từ khi dòng thứ hai chạy xong. Phòng lab 1 cho em xem đúng kiểu lần vết này với bốn chương trình nhỏ.
Bốn kiểu dữ liệu cơ bản
Kiểu dữ liệu cho biết giá trị thuộc loại nào và vì thế phép toán nào dùng được trên nó. Python tự suy ra kiểu từ giá trị; hàm type() cho em biết kiểu hiện tại.
Kiểu
Ví dụ giá trị
Phép toán thường dùng
Lưu ý
int
3, 0, 2040
+ - * // % **
Số nguyên, không có phần thập phân; chia nguyên // và lấy dư % áp dụng cho số nguyên.
float
2.5, 0.75, 4.0
+ - * /
Số thực viết bằng dấu chấm. Kết quả có thể lệch một lượng rất nhỏ so với phép tính trên giấy (kiến thức bổ sung).
str
"HN", "4721"
+ (nối), * (lặp), len()
Chuỗi kí tự nằm trong cặp nháy. "4721" là chuỗi, không phải số.
bool
True, False
and, or, not
Kết quả của phép so sánh; dùng làm điều kiện của if và while.
Phép toán số học và thứ tự ưu tiên
Bốn phép quen thuộc là +, -, * (nhân), / (chia). Python thêm ba phép rất hay dùng: // (chia nguyên: lấy phần nguyên của thương), % (phần dư) và ** (lũy thừa). Thứ tự ưu tiên từ cao xuống thấp: trước hết ngoặc, rồi ** , rồi * / // % (cùng mức, tính từ trái sang phải), cuối cùng + - .
a = 17
b = 4
print(a / b)
print(a // b)
print(a % b)
print(a ** 2)
In ra
4.25
289
Với hai số nguyên không âm a và b>0, ba phép liên hệ qua đẳng thức a=(a\,//\,b)\cdot b+(a\,\%\,b) và 0\le a\,\%\,b<b. Đọc bằng hình ảnh: chia a viên bi vào các hộp mỗi hộp b viên thì a // b là số hộp đầy , a % b là số bi lẻ còn lại. Phép / thì khác: nó trả về một số thực, và trả về số thực ngay cả khi chia hết .
print(10 / 5)
print(10 // 5)
print(type(10 / 5))
In ra
2.0
<class 'float'>
Bẫy 2 · phép toán đi theo kiểu dữ liệu
Ba chỗ hay trượt: (một) 10 / 5 là 2.0 (kiểu float), không phải 2; muốn số nguyên dùng 10 // 5 . (hai) "3" + "4" là "34" chứ không phải 7. (ba) dữ liệu nhập bằng input() có kiểu chuỗi, nên phải đổi kiểu bằng int() hoặc float() trước khi tính.
Gặp ở: Lab 2 và 3 · Bài 1 và 12
x = "3"
y = "4"
print(x + y)
print(int(x) + int(y))
print(x * 3)
print(len(x + y))
In ra
34
333
Điều gì xảy ra nếu cộng chuỗi với số?
tuoi = input() # người dùng gõ 15
print(tuoi + 1)
Dòng đầu cho tuoi là chuỗi "15" . Dòng thứ hai thử cộng chuỗi với số nguyên nên Python dừng chương trình và báo TypeError (thông báo nói rằng nối được chuỗi với chuỗi). Cách sửa là đổi kiểu trước khi tính: int(tuoi) + 1 . Máy không tự đoán rằng em muốn cộng số.
Kiến thức bổ sung: chia nguyên trong C++
Trong C++, nếu cả hai toán hạng đều là số nguyên thì 7 / 2 cho 3 (chia nguyên), còn Python cho 3.5 . Hai ngôn ngữ cùng có phép lấy dư % . Vì vậy khi đọc một đoạn mã, hãy xác nhận ngôn ngữ trước khi kết luận phép chia cho kết quả gì.
Giá trị của biểu thức 2 + 3 * 4 ** 2 // 5 % 7 là bao nhiêu?
Phòng lab 2 · Kiểu của biểu thức DẠNG: KÉO THẢ · PHÂN LOẠI KIỂU HOẶC LỖI
Dự đoán, kéo thả, kiểm tra. Mỗi thẻ là một biểu thức Python. Xếp nó vào ô kiểu của kết quả (int, float, str, bool) hoặc ô “báo lỗi”. Không kéo được thì bấm thẻ rồi bấm ô đích. Lab này gặp bẫy 2 .
Phép chia nguyên và phép lấy dư là hai nửa của cùng một phép chia có dư. Em dùng lab 3 để nhìn chúng bằng hộp bi: đổi số bi và cỡ hộp, đọc ba kết quả, và chinh phục ba mục tiêu.
Có 47 viên bi, xếp vào các hộp, mỗi hộp 6 viên. Hỏi 47 // 6 và 47 % 6 lần lượt là gì?
Phòng lab 3 · Hộp bi: chia nguyên, dư và chia thực DẠNG: THANH TRƯỢT · HỘP BI VÀ BA PHÉP CHIA
Dự đoán trước: kéo hai thanh trượt, đoán trước số hộp đầy và số bi lẻ rồi đọc ba kết quả. Ba mục tiêu bên dưới yêu cầu em tìm số bi và cỡ hộp phù hợp. Lab này gặp bẫy 2 .
Cho x = 7, rồi chạy lần lượt: x = x // 2 và x = x % 2 + x. Cuối cùng x bằng bao nhiêu? Em lần vết từng dòng trước rồi mở gợi ý.