Lập trình và thuật toán cơ bản

Vòng lặp và phép chia hết trong Python/C++

Vòng lặp while thực hiện khối lệnh lặp lại chừng nào điều kiện còn đúng. Điều kiện được kiểm tra trước mỗi lần lặp, nên nếu sai ngay từ đầu thì khối lệnh không chạy lần nào. Để đếm số lần lặp, cách chắc chắn nhất là theo dõi giá trị các biến qua từng vòng: thực hiện thân vòng, cập nhật biến, rồi kiểm tra lại điều kiện với giá trị mới.

Khi biến tăng đều một bước d > 0 từ giá trị đầu a và điều kiện là x < b, số lần lặp bằng số giá trị a, a+d, a+2d, \dots nhỏ hơn b.

Vòng lặp for và range

• Python: for i in range(a, b) cho các giá trị i = a, a+1, \dots, b-1, không gồm b; số lần lặp là b - a. Ví dụ range(2, 9) lặp 7 lần.
• C++: for (int i = a; i < b; i++) cho cùng dãy giá trị.
• Vòng lặp lồng nhau: nếu vòng trong chạy range(0, i + 1), thì với mỗi giá trị i thân vòng trong chạy i + 1 lần. Biến khai báo ngoài vòng bị thay đổi sau mỗi lần gán, nên phải tính lại giá trị theo từng bước; ví dụ phép gán k = -1 \cdot k đổi dấu sau mỗi vòng ngoài.

Phép chia lấy dư và kiểm tra chia hết

• a % b là số dư khi chia a cho b. a chia hết cho b khi a % b == 0; a % b != 0 nghĩa là không chia hết. Ví dụ x % 2 == 0 dùng để kiểm tra x là số chẵn.
• Với số âm, Python cho -5 % 3 bằng 1 (kết quả không âm khi số chia dương), còn C++ cho -5 % 3 bằng -2 (kết quả mang dấu của số bị chia).
• Điều kiện lặp nối bằng and nghĩa là vòng tiếp tục chỉ khi cả hai vế đúng; vòng dừng khi một trong hai vế sai, theo quy tắc phủ định \neg(A \wedge B) = \neg A \vee \neg B. Với while n % a != 0 and n % b != 0, khi n bắt đầu từ 1 và tăng dần, vòng dừng khi n chia hết cho a hoặc cho b, nên n là số nguyên dương nhỏ nhất chia hết cho a hoặc b, tức là \min(a, b).

Phép chia nguyên và phép chia thực

• Python: // lấy thương nguyên (làm tròn xuống), còn / luôn cho số thực: 9 // 2 cho 4, 9 / 2 cho 4.5.
• C++: khi cả hai toán hạng là số nguyên, / là chia nguyên và bỏ phần thập phân: 9 / 2 cho 4. Với số dương, // của Python và / của C++ cho cùng kết quả; với số âm thì khác nhau: Python -9 // 2 cho -5, C++ -9 / 2 cho -4.
• Khi đọc chương trình, phải xác định biến có phải số nguyên hay không, vì x / 2 trong Python với x nguyên ra số thực. Ví dụ: nếu x = 20 thì 20 // 6 cho 3.

Chỉ số chuỗi và mảng

• s[k] lấy kí tự ở vị trí k, và vị trí được đếm từ 0 trong cả Python lẫn C++. Ví dụ với s = "HOC", s[1] là O.
• Vì vậy kí tự thứ k+1 trong chuỗi ứng với chỉ số k. Khi x đã được tính, phải tra đúng vị trí x chứ không phải vị trí x+1.

Thuật toán và cấu trúc điều khiển

Thuật toán và cấu trúc điều khiển. Thuật toán là dãy hữu hạn các bước rõ ràng, cho kết quả xác định từ dữ liệu vào. Mọi chương trình được xây dựng từ ba cấu trúc điều khiển: tuần tự (các lệnh thực hiện theo thứ tự), rẽ nhánh (if/else chọn một trong các nhánh) và lặp (for/while). Khi đọc một đoạn mã, bước đầu tiên là xác định cấu trúc nào đang quyết định giá trị các biến.

Theo dõi thuật toán bằng bảng giá trị. Để tìm kết quả của một hàm, ghi lại giá trị các biến sau mỗi lệnh gán, rồi thay các giá trị cuối cùng vào biểu thức trả về. Kết quả của hàm phụ thuộc vào vị trí các phần tử trong mảng, không chỉ phụ thuộc vào tập giá trị có trong mảng.

Sắp xếp chèn (insertion sort). Với mỗi phần tử x ở vị trí i, các phần tử lớn hơn x trong đoạn đã sắp xếp được dịch lùi sang phải, rồi x được đặt vào chỗ trống. Vòng while dịch chuyển chỉ chạy khi điều kiện A[j] > x đúng; nếu mảng đã sắp xếp không giảm thì điều kiện này luôn sai nên không có lệnh dịch nào được thực hiện. Ví dụ với mảng (3, 1, 2): với i = 1, x = 1 nên 3 được dịch sang phải và thu được (1, 3, 2); với i = 2, x = 2 nên 3 được dịch tiếp và thu được (1, 2, 3).

Phân hoạch mảng bằng biến chỉ số. Một mẫu thuật toán thường gặp: dùng i để duyệt mảng và giữ j là vị trí đích cho phần tử có tính chất cần đưa lên đầu. Khi gặp phần tử có tính chất mà A[j] không có, hai phần tử đổi chỗ rồi j tăng thêm 1. Sau khi chạy xong, mọi phần tử có tính chất nằm trước các phần tử còn lại, nhưng thứ tự tương đối giữa các phần tử cùng loại không được giữ nguyên.

Học máy là thuật toán học từ dữ liệu.

• Học có giám sát: dữ liệu huấn luyện có nhãn đã biết (ví dụ kết luận do chuyên gia đưa ra); mô hình học cách ánh xạ từ các đặc trưng (thuộc tính đầu vào) sang nhãn (đầu ra cần dự đoán). Các nhãn cần dự đoán phải nằm trong tập nhãn đã định nghĩa trước.
• Học không giám sát: dữ liệu không có nhãn và thuật toán tự tìm cấu trúc, ví dụ gom các mẫu giống nhau thành nhóm. Khi dữ liệu đã được gán nhãn tích cực hoặc tiêu cực, bài toán thuộc loại học có giám sát chứ không phải học không giám sát.
• Phân loại văn bản theo sắc thái là ứng dụng xử lý ngôn ngữ tự nhiên, thể hiện khả năng hiểu ngôn ngữ của trí tuệ nhân tạo. Không nhất thiết phải dùng toàn bộ dữ liệu để huấn luyện, vì phần dữ liệu còn lại dùng làm tập kiểm tra để đánh giá khách quan mô hình.
• Mô hình chỉ dự đoán tốt khi đầu vào có đủ các đặc trưng đã dùng để huấn luyện. Kết quả dự đoán là căn cứ hỗ trợ quyết định, không thay thế việc quan sát và đánh giá thực địa của người chuyên môn.
• Chất lượng mô hình sau khi triển khai có thể được đánh giá bằng hiệu quả thực tế mà nó mang lại.

Vòng lặp và phép chia hết trong Python/C++

Vòng lặp for trong Python duyệt lần lượt từng phần tử của danh sách: câu lệnh for x in a: gán lần lượt mỗi phần tử của a cho biến x, và thân vòng lặp chạy một lần cho mỗi phần tử theo đúng thứ tự xuất hiện. Vì vậy kết quả chương trình phụ thuộc vào thứ tự các phần tử. Biến tích lũy như s hoặc tong phải được gán giá trị khởi đầu bằng 0 trước vòng lặp, rồi cập nhật bằng s = s + x hoặc s += x. Ví dụ: s = 0, duyệt [2, 4, 5] thì s = 11. Khi có điều kiện lọc, chỉ phần tử thỏa điều kiện mới được cộng vào s; các phần tử còn lại không làm thay đổi s.

Lặp theo chỉ số với range()

• range(n) sinh dãy 0, 1, …, n−1, nên range(3) chạy đúng 3 lượt.
• range(a, b) sinh các số từ a đến b−1, không bao gồm b; ví dụ range(1, 9) cho các số từ 1 đến 8.
• range(len(a)) sinh các chỉ số 0 đến len(a)−1; a[i] là phần tử ở vị trí i (đếm từ 0).
• Khi cần chỉ số, công thức có thể dùng trực tiếp i, ví dụ s = s + a[i] - i.
• range(1, x + 1) cho x lượt lặp khi x ≥ 1, vì số cuối x + 1 không được lấy.
• Vòng lặp while lặp khi điều kiện còn đúng và phải tự cập nhật biến chỉ số (i = i + 1); nếu quên bước này, vòng lặp không dừng.

Phép % và //

• a % k là số dư khi chia a cho k. a % k == 0 đúng khi a chia hết cho k; a % 2 == 0 kiểm tra số chẵn, a % 2 == 1 kiểm tra số lẻ. Ví dụ: 7 % 3 = 1 và 9 % 3 = 0.
• % chỉ cho số dư, không cho thương; thương là //. Với x = 7 thì x % 2 = 1 còn x // 2 = 3.
• a // b là phép chia lấy phần nguyên; với số nguyên, kết quả là số nguyên không có phần thập phân: 9 // 2 = 4.
• Điều kiện chia hết có thể dùng với số bất kỳ, ví dụ x % 7 == 0 hoặc x % 4 == 0.
• Trong C++, với hai số nguyên (int) thì % cũng cho số dư và / cho thương đã bỏ phần lẻ, tương đương // của Python. Khác biệt cần nhớ: khi có số âm, Python cho số dư cùng dấu với số chia, còn C++ theo dấu của số bị chia; các bài tập thường chỉ dùng số dương.

if / elif / else

• if chỉ thực hiện khối lệnh khi điều kiện đúng. Khi không có else, phần tử không thỏa điều kiện bị bỏ qua và biến giữ nguyên giá trị.
• elif chỉ được xét khi các nhánh if phía trước đều sai. Khi nhiều điều kiện cùng đúng, chỉ nhánh đầu tiên đúng được thực hiện. Ví dụ với x = 12, điều kiện x % 4 == 0 đúng nên nhánh elif x > 5 bị bỏ qua.
• else là nhánh còn lại; khi có else, mọi phần tử đều được xử lý, ví dụ phần tử không thỏa điều kiện thì bị trừ 1 khỏi s.
• Khi các nhánh cộng và trừ giá trị khác nhau, tổng cuối cùng phụ thuộc vào số lượt rơi vào mỗi nhánh; cần đếm đủ từng lượt.
• Điều kiện so sánh như x > 5 hoặc lst[i] > 6 kết hợp với phép chia hết cho phép lọc theo ngưỡng.