Chuyên đề 1: Xử lý chữ số và đổi hệ cơ số trong C++ và Python: tách chữ số, số đảo ngược, số đối xứng, hệ nhị phân và thập lục phân
n % 10 và n / 10 em đã giải được cả một họ bài: tổng chữ số, số đảo ngược, số đối xứng. Thay 10 bằng 2 là ta có ngay hệ nhị phân, ngôn ngữ của máy tính.Lời mở đầu
Chào các em! Series Nhập môn lập trình gồm 14 bài đã đưa em đi từ câu lệnh đầu tiên tới bài 14: tổng ôn và đề thi thử. Tuy vậy, có vài dạng bài xuất hiện rất thường xuyên trong đề thi HSG cấp huyện, cấp thành phố mà 14 bài chưa có chỗ để nói kỹ. Vì thế thầy viết thêm 10 chuyên đề nhập môn: chữ số và hệ cơ số, số thực và làm tròn, số nguyên lớn, mô phỏng trên lưới, xử lý xâu, số học trong đề thi, đọc ghi file – nhập xuất nhanh, dùng Python khi đi thi, mảng cộng dồn 2 chiều và vét cạn thông minh. Em có thể học chúng sau bài 14, hoặc xen kẽ ngay khi đã học xong các bài nền tảng tương ứng.
Chuyên đề 1 này chỉ cần em biết vòng lặp (bài 4), nên có thể học ngay sau bài 4; riêng phần 3 dùng xâu ký tự nên em nên học thêm bài 8: xâu ký tự. Đề thi rất hay hỏi: tính tổng các chữ số, đếm chữ số chẵn, tìm số đảo ngược, kiểm tra số đối xứng, đổi một số sang hệ nhị phân… Tất cả đều xoay quanh một kỹ thuật duy nhất, và hôm nay mình sẽ đi thật chậm, có nhiều ví dụ để em nắm chắc.
n % 10 và n / 10; đếm chữ số, tính tổng chữ số, tìm chữ số lớn nhất; hai trường hợp hay sai là n = 0 và số âm; cách tạo số đảo ngược, kiểm tra số đối xứng, ghép hai số; khi nào nên xử lý bằng xâu; đổi thập phân sang nhị phân và ngược lại (phương pháp Horner); hệ cơ số b bất kỳ, hệ 16 và các hàm có sẵn trong C++, Python. Có khung chạy tay từng dòng code, 3 mô phỏng tương tác và 8 bài tập kèm gợi ý.Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Tách chữ số bằng % 10 và / 10
Em hãy nhìn số $n = 4507$. Nếu chia $4507$ cho $10$ thì được thương là $450$ và dư $7$. Thật thú vị: số dư chính là chữ số cuối cùng (hàng đơn vị), còn thương chính là số ban đầu khi đã bỏ chữ số cuối đi. Trong C++ (với số nguyên) và Python, hai phép tính đó viết là:
n % 10: lấy chữ số cuối của n. Ví dụ4507 % 10 = 7.n / 10trong C++ hoặcn // 10trong Python: bỏ chữ số cuối của n. Ví dụ4507 / 10 = 450.
Hình 1. Một phép chia cho 10 tách số 4507 thành hai phần: chữ số cuối (7) và phần còn lại (450).
Bây giờ ta lặp lại việc đó với phần còn lại: $450$ cho chữ số cuối là $0$, còn lại $45$; $45$ cho chữ số $5$, còn lại $4$; $4$ cho chữ số $4$, còn lại $0$. Khi $n$ về $0$ là đã lấy hết chữ số. Đây chính là vòng lặp while (n > 0) mà em đã học ở bài 4:
| Vòng | n | d = n % 10 | n / 10 | tổng | đếm |
|---|---|---|---|---|---|
| 1 | 4507 | 7 | 450 | 7 | 1 |
| 2 | 450 | 0 | 45 | 7 | 2 |
| 3 | 45 | 5 | 4 | 12 | 3 |
| 4 | 4 | 4 | 0 | 16 | 4 |
| dừng | 0 | – | – | 16 | 4 |
Bảng 1. Tách chữ số của 4507. Cột d lần lượt là 7, 0, 5, 4: các chữ số được lấy ra từ phải sang trái. Sau 4 vòng, đếm = 4 chữ số, tổng = 16.
while(n > 0){
int d = n % 10; // lấy chữ số cuối
// ... xử lý chữ số d: cộng vào tổng, đếm, so sánh ...
n /= 10; // bỏ chữ số cuối
}Em nhập một số bất kỳ vào mô phỏng dưới đây rồi bấm Tiếp để xem từng chữ số được “cắt” khỏi đuôi số n như thế nào. Thử cả số $0$ nữa nhé:
Giờ em xem máy tính chạy đoạn code tính tổng chữ số từng dòng một. Em để ý biến n ngắn dần, còn tong lớn dần:
Hai trường hợp đặc biệt hay làm mất điểm.
- n = 0. Điều kiện
n > 0sai ngay từ đầu nên vòng lặp không chạy. Tổng chữ số bằng 0 thì vẫn đúng, nhưng nếu đếm số chữ số thì ra 0, trong khi số 0 có 1 chữ số! Cách sửa: thêmif (n == 0) dem = 1;trước vòng lặp. - Số âm. Với $n = -123$, điều kiện
n > 0sai nên vòng lặp không chạy. Ngay cả khi đổi thànhn != 0thì C++ cho-123 % 10 = -3(số dư âm), còn Python cho-123 % 10 = 7(vì Python làm tròn thương xuống $-13$). Cả hai đều không phải điều ta muốn. Cách an toàn: bỏ dấu trước rồi mới tách:if (n < 0) n = -n;(Python:n = abs(n)).
Gộp tất cả lại: chương trình dưới đây đọc một số nguyên (có thể âm), in ra số chữ số, tổng các chữ số và chữ số lớn nhất:
Xem code C++ / Python: đếm chữ số, tổng chữ số, chữ số lớn nhất (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n;
cin >> n;
if(n < 0) n = -n; // số âm: bỏ dấu trước khi tách
int dem = 0, tong = 0, lon = 0;
if(n == 0) dem = 1; // số 0 có đúng 1 chữ số
while(n > 0){
int d = n % 10; // chữ số cuối
dem++;
tong += d;
lon = max(lon, d);
n /= 10; // bỏ chữ số cuối
}
cout << dem << " " << tong << " " << lon;
return 0;
}n = abs(int(input())) # số âm: bỏ dấu trước khi tách
dem, tong, lon = 0, 0, 0
if n == 0:
dem = 1 # số 0 có đúng 1 chữ số
while n > 0:
d = n % 10 # chữ số cuối
dem += 1
tong += d
lon = max(lon, d)
n //= 10 # bỏ chữ số cuối (chia nguyên)
print(dem, tong, lon)int (khoảng $2 \cdot 10^9$). Em khai báo long long n để đọc được số tới khoảng $9{,}2 \cdot 10^{18}$. Còn tổng chữ số thì nhỏ (tối đa $9 \times 19 = 171$) nên để int là đủ.Lấy chữ số thứ k từ phải sang. Muốn lấy chữ số hàng chục, ta bỏ 1 chữ số cuối rồi lấy chữ số cuối: (n / 10) % 10. Hàng trăm: (n / 100) % 10. Tổng quát, chữ số thứ $k$ tính từ phải (bắt đầu từ $k = 0$ là hàng đơn vị) là $\lfloor n / 10^k \rfloor \bmod 10$. Ví dụ với $4507$: hàng chục là $(4507 / 10) \% 10 = 450 \% 10 = 0$, hàng trăm là $45 \% 10 = 5$.
| k | Hàng | Bỏ k chữ số cuối | Lấy % 10 | Chữ số |
|---|---|---|---|---|
| 0 | đơn vị | 4507 | 4507 % 10 | 7 |
| 1 | chục | 450 | 450 % 10 | 0 |
| 2 | trăm | 45 | 45 % 10 | 5 |
| 3 | nghìn | 4 | 4 % 10 | 4 |
| 4 | chục nghìn | 0 | 0 % 10 | 0 |
Bảng 2. Lấy chữ số thứ k (tính từ phải, bắt đầu từ 0) của 4507. Khi k vượt quá số chữ số thì kết quả là 0, đúng như khi ta viết thêm số 0 ở đầu: 04507.
Xem code C++ / Python: lấy chữ số thứ k tính từ bên phải (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n;
int k;
cin >> n >> k; // k = 0: hàng đơn vị, k = 1: hàng chục, ...
for(int i = 0; i < k; i++) n /= 10; // bỏ k chữ số cuối
cout << n % 10; // chữ số cuối của phần còn lại
return 0;
}n, k = map(int, input().split()) # k = 0: hàng đơn vị, k = 1: hàng chục, ...
print(n // 10 ** k % 10) # bỏ k chữ số cuối rồi lấy chữ số cuốiPhần 2Số đảo ngược, số đối xứng và ghép số
Số đảo ngược của $1230$ là $321$ (đọc ngược được $0321$, bỏ số 0 ở đầu). Ta vẫn dùng khuôn mẫu tách chữ số, nhưng thay vì cộng $d$ vào tổng, ta gắn $d$ vào cuối một số mới rev:
rev = rev * 10 + d
Nhân rev với 10 làm các chữ số cũ dịch sang trái một ô, để lại hàng đơn vị bằng 0; cộng $d$ là đặt $d$ vào đúng chỗ trống đó. Vì các chữ số được tách ra từ phải sang trái, chữ số cuối của $n$ được gắn vào rev đầu tiên và cuối cùng trở thành chữ số đầu: số bị đảo ngược.
| Vòng | n | d = n % 10 | rev = rev * 10 + d | n / 10 |
|---|---|---|---|---|
| 1 | 1230 | 0 | 0 × 10 + 0 = 0 | 123 |
| 2 | 123 | 3 | 0 × 10 + 3 = 3 | 12 |
| 3 | 12 | 2 | 3 × 10 + 2 = 32 | 1 |
| 4 | 1 | 1 | 32 × 10 + 1 = 321 | 0 |
Bảng 3. Đảo ngược 1230. Chữ số 0 ở cuối được gắn đầu tiên nhưng vì rev = 0 nên nó “biến mất”, đúng như ta muốn.
Số đối xứng (palindrome) là số đọc xuôi hay đọc ngược đều như nhau, ví dụ $121$, $4554$, $7$. Cách kiểm tra rất gọn: tính số đảo ngược rồi so với số ban đầu. Nhớ lưu lại n trước khi tách, vì vòng lặp làm n về 0. Trong hàm dưới đây, n là tham số truyền vào (bản sao), nên n ở main vẫn nguyên vẹn.
| n | Số đảo ngược rev | rev == n ? | Kết luận |
|---|---|---|---|
| 12321 | 12321 | bằng | đối xứng |
| 4554 | 4554 | bằng | đối xứng |
| 7 | 7 | bằng | đối xứng (mọi số 1 chữ số) |
| 120 | 21 | khác | không đối xứng |
| 1231 | 1321 | khác | không đối xứng |
Bảng 4. Kiểm tra số đối xứng bằng số đảo ngược. Số tận cùng bằng 0 (khác 0) không bao giờ đối xứng, vì chữ số đầu của nó không thể là 0.
Xem code C++ / Python: số đảo ngược và kiểm tra số đối xứng (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
long long daoNguoc(long long n){
long long rev = 0;
while(n > 0){
rev = rev * 10 + n % 10; // dịch rev sang trái 1 chữ số, gắn chữ số cuối của n
n /= 10;
}
return rev;
}
int main(){
long long n;
cin >> n;
long long r = daoNguoc(n);
cout << r << "\n";
if(r == n) cout << "YES"; // đối xứng: đọc xuôi = đọc ngược
else cout << "NO";
return 0;
}def dao_nguoc(n):
rev = 0
while n > 0:
rev = rev * 10 + n % 10 # dịch rev sang trái 1 chữ số, gắn chữ số cuối của n
n //= 10
return rev
n = int(input())
r = dao_nguoc(n)
print(r)
print("YES" if r == n else "NO") # đối xứng: đọc xuôi = đọc ngượcint, số $1\,000\,000\,009$ vẫn nằm trong giới hạn, nhưng số đảo ngược của nó là $9\,000\,000\,001$ thì vượt quá $2^{31} - 1 \approx 2{,}1 \cdot 10^9$ và bị sai. Vì vậy biến rev nên là long long. Python không có chuyện tràn số, nhưng khi viết C++ em phải luôn tự hỏi: “giá trị lớn nhất của biến này là bao nhiêu?”.Ghép hai số. Muốn viết số $b$ ngay sau số $a$ (ghép $12$ và $345$ thành $12345$), ta dịch $a$ sang trái đúng bằng số chữ số của b rồi cộng $b$: $12 \times 10^3 + 345 = 12345$. Số chữ số của $b$ đếm bằng khuôn mẫu ở phần 1 (nhớ trường hợp $b = 0$ có 1 chữ số). Ý tưởng “dịch sang trái rồi cộng” này sẽ quay lại ở phần 4 với hệ nhị phân, và cũng là chìa khoá của bài Concatenation of Consecutive Binary Numbers trong mục luyện tập.
| a | b | Số chữ số của b | a × 10^k + b | Kết quả |
|---|---|---|---|---|
| 12 | 345 | 3 | 12 × 1000 + 345 | 12345 |
| 7 | 0 | 1 (không phải 0!) | 7 × 10 + 0 | 70 |
| 2026 | 10 | 2 | 2026 × 100 + 10 | 202610 |
Bảng 5. Ghép số. Hàng thứ hai cho thấy vì sao phải nhớ “số 0 có 1 chữ số”: nếu đếm ra 0 chữ số thì ghép 7 với 0 lại ra 7.
Xem code C++ / Python: ghép hai số a và b thành số ab (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int soChuSo(long long x){
if(x == 0) return 1; // số 0 có 1 chữ số
int d = 0;
while(x > 0){ d++; x /= 10; }
return d;
}
int main(){
long long a, b;
cin >> a >> b;
long long p = 1;
for(int i = 0; i < soChuSo(b); i++) p *= 10; // p = 10^(số chữ số của b)
cout << a * p + b; // dịch a sang trái rồi gắn b
return 0;
}def so_chu_so(x):
if x == 0:
return 1 # số 0 có 1 chữ số
d = 0
while x > 0:
d += 1
x //= 10
return d
a, b = map(int, input().split())
p = 10 ** so_chu_so(b) # p = 10^(số chữ số của b)
print(a * p + b) # dịch a sang trái rồi gắn b| Bài toán | Xử lý chữ số d trong vòng lặp | Ví dụ với n = 4507 |
|---|---|---|
| Đếm chữ số | dem++ | 4 |
| Tổng chữ số | tong += d | 16 |
| Tích chữ số | tich *= d (khởi tạo tich = 1) | 0 |
| Chữ số lớn nhất | lon = max(lon, d) | 7 |
| Đếm chữ số chẵn | if (d % 2 == 0) dem++ | 2 (chữ số 0 và 4) |
| Số đảo ngược | rev = rev * 10 + d | 7054 |
Bảng 6. Cùng một vòng lặp tách chữ số, chỉ đổi một dòng là được bài toán mới.
Phần 3Cách làm bằng xâu và khi nào nên dùng
Có một cách khác để lấy các chữ số: biến số thành xâu rồi duyệt từng ký tự. Trong C++ dùng to_string(n), trong Python dùng str(n). Mỗi ký tự là một chữ số dạng ký tự, muốn đổi ra số thì lấy c - '0' trong C++ (vì mã của '0'…'9' đứng liền nhau) hoặc int(c) trong Python.
| Việc cần làm | C++ (s = to_string(n)) | Python (s = str(n)) |
|---|---|---|
| Số chữ số | s.size() | len(s) |
| Chữ số thứ i (từ trái, i từ 0) | s[i] - '0' | int(s[i]) |
| Tổng chữ số | vòng for cộng c - '0' | sum(map(int, s)) |
| Số đảo ngược | reverse(s.begin(), s.end()) | s[::-1] |
| Kiểm tra đối xứng | s == string(s.rbegin(), s.rend()) | s == s[::-1] |
Bảng 7. Xử lý chữ số bằng xâu. Ưu điểm: lấy được chữ số theo thứ tự từ trái sang phải và truy cập thẳng vị trí bất kỳ.
Vậy khi nào bắt buộc dùng xâu? Khi số quá lớn, không kiểu số nguyên nào chứa nổi. Ví dụ đề cho “số $n$ có tới $10^5$ chữ số”: long long chỉ chứa được khoảng 19 chữ số, nên em phải đọc n vào một xâu. Rất nhiều bài kiểu này chỉ hỏi về chữ số (tổng chữ số, chia hết cho 3, cho 9, chữ số thứ k…) nên xâu là đủ, không cần tính giá trị của n.
Nhắc lại dấu hiệu chia hết từ bài 12: số học cơ bản: một số chia hết cho 3 (hoặc 9) khi và chỉ khi tổng các chữ số của nó chia hết cho 3 (hoặc 9). Chương trình dưới đây đọc một số rất dài, in số chữ số, tổng chữ số và cho biết số đó có chia hết cho 3 không:
Xem code C++ / Python: xử lý số có tới 100000 chữ số bằng xâu (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s; // số có thể dài tới 100000 chữ số
long long tong = 0;
for(char c : s) tong += c - '0'; // ký tự '7' trừ '0' được số 7
cout << s.size() << "\n" << tong << "\n";
if(tong % 3 == 0) cout << "YES"; // chia hết cho 3 <=> tổng chữ số chia hết cho 3
else cout << "NO";
return 0;
}import sys
s = sys.stdin.readline().strip() # số có thể dài tới 100000 chữ số
tong = sum(int(c) for c in s) # int('7') = 7
print(len(s))
print(tong)
print("YES" if tong % 3 == 0 else "NO") # chia hết cho 3 <=> tổng chữ số chia hết cho 3long long và em cần tính toán thêm với giá trị số (đảo ngược rồi cộng, so sánh…): không phải đổi qua đổi lại kiểu dữ liệu.Dùng xâu khi số quá dài, khi cần đọc chữ số từ trái sang phải, hoặc khi cần sửa một chữ số ở giữa (như bài Đổi 1 chữ số để chia hết cho 3). Với số âm, nhớ rằng
to_string(-12) là "-12", ký tự đầu là dấu trừ chứ không phải chữ số!Phần 4Hệ nhị phân: đổi qua lại với hệ thập phân
Ta quen viết số trong hệ thập phân (hệ 10): dùng 10 chữ số 0…9, và mỗi vị trí có giá trị gấp 10 lần vị trí bên phải nó: $4507 = 4 \cdot 1000 + 5 \cdot 100 + 0 \cdot 10 + 7 \cdot 1$. Máy tính thì chỉ có hai trạng thái (có điện, không điện), nên nó dùng hệ nhị phân (hệ 2): chỉ có hai chữ số 0 và 1 (gọi là bit), và mỗi vị trí có giá trị gấp 2 lần vị trí bên phải: 1, 2, 4, 8, 16, 32…
Hình 2. Số nhị phân $1101_2$: bit ở vị trí k có giá trị $2^k$. Cộng giá trị của các bit 1 lại: $8 + 4 + 1 = 13$. Chữ số nhỏ $_2$ cho biết số đang viết ở hệ 2.
| k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| $2^k$ | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 |
Bảng 8. Các lũy thừa của 2 nên thuộc lòng. Mẹo: $2^{10} = 1024 \approx 10^3$, nên $2^{20} \approx 10^6$, $2^{30} \approx 10^9$ và $2^{60} \approx 10^{18}$.
Ví dụ đổi nhị phân → thập phân: $101101_2$ có các bit 1 ở vị trí 5, 3, 2, 0 (đếm từ phải, bắt đầu từ 0), nên bằng $32 + 8 + 4 + 1 = 45$. Ví dụ ngược lại bằng cách nhẩm: muốn viết $37$ ở hệ 2, lấy lũy thừa của 2 lớn nhất không vượt quá 37 là 32, còn $37 - 32 = 5$; lũy thừa lớn nhất không vượt quá 5 là 4, còn 1; cuối cùng là 1. Vậy $37 = 32 + 4 + 1$, bật các bit ở vị trí 5, 2, 0: $37 = 100101_2$. Cách nhẩm này tiện khi làm trên giấy, nhưng để lập trình thì cách chia 2 lấy dư dưới đây gọn hơn nhiều.
Thập phân → nhị phân: chia 2 lấy dư, đọc ngược. Ở phần 1, n % 10 cho chữ số cuối trong hệ 10. Hoàn toàn tương tự, n % 2 cho bit cuối trong hệ 2 (n chẵn thì bit cuối là 0, n lẻ thì là 1), còn n / 2 bỏ bit cuối đi. Cứ chia 2 liên tục tới khi thương bằng 0, ghi lại các số dư, rồi đọc ngược từ số dư cuối cùng lên số dư đầu tiên.
| Phép chia | Thương | Số dư |
|---|---|---|
| 13 : 2 | 6 | 1 |
| 6 : 2 | 3 | 0 |
| 3 : 2 | 1 | 1 |
| 1 : 2 | 0 | 1 |
Bảng 9. Đổi 13 sang hệ 2. Các số dư theo thứ tự là 1, 0, 1, 1; đọc từ dưới lên ta được $13 = 1101_2$, khớp với Hình 2.
Em tự nhập số khác để luyện tay. Ô “Hệ b” để là 2; phần 5 em sẽ thử đổi sang 8 hoặc 16:
Trong code, ta thêm từng số dư vào cuối xâu s, nên xâu thu được bị ngược; cuối cùng chỉ cần đảo ngược xâu. Đừng quên trường hợp $n = 0$:
Nhị phân → thập phân: phương pháp Horner. Cách thứ nhất là cộng giá trị các vị trí như Hình 2. Nhưng có cách gọn hơn, giống hệt rev = rev * 10 + d ở phần 2: đọc các bit từ trái sang phải, mỗi bit mới làm res = res * 2 + bit. Với $1101_2$: $res = 0 \to 0 \cdot 2 + 1 = 1 \to 1 \cdot 2 + 1 = 3 \to 3 \cdot 2 + 0 = 6 \to 6 \cdot 2 + 1 = 13$. Nhân 2 làm các bit cũ dịch sang trái một vị trí (giá trị mỗi bit gấp đôi), nên khi đọc hết, bit đầu tiên đã được nhân đủ $2^3 = 8$ lần.
Xem code C++ / Python: đổi thập phân ↔ nhị phân (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
string toBinary(long long n){
if(n == 0) return "0";
string s = "";
while(n > 0){
s += char('0' + n % 2); // số dư = bit cuối
n /= 2;
}
reverse(s.begin(), s.end()); // đọc ngược các số dư
return s;
}
long long fromBinary(const string &s){
long long res = 0;
for(char c : s) res = res * 2 + (c - '0'); // Horner
return res;
}
int main(){
long long n;
string s;
cin >> n >> s;
cout << toBinary(n) << "\n" << fromBinary(s);
return 0;
}import sys
def to_binary(n):
if n == 0:
return "0"
s = ""
while n > 0:
s += str(n % 2) # số dư = bit cuối
n //= 2
return s[::-1] # đọc ngược các số dư
def from_binary(s):
res = 0
for c in s:
res = res * 2 + int(c) # Horner
return res
data = sys.stdin.read().split()
print(to_binary(int(data[0])))
print(from_binary(data[1]))n & 1 (lấy bit cuối, giống n % 2), n >> 1 (bỏ bit cuối, giống n / 2). Em sẽ học kỹ ở bài 20: thao tác bit, khi đó hệ nhị phân trong chuyên đề này là nền tảng bắt buộc.Phần 5Hệ cơ số b tổng quát, hệ 16 và các hàm có sẵn
Không có gì đặc biệt với 10 hay 2. Trong hệ cơ số b (với $b \ge 2$), ta dùng $b$ chữ số có giá trị $0, 1, \ldots, b - 1$, và vị trí thứ $k$ (tính từ phải, bắt đầu từ 0) có giá trị $b^k$. Hai thuật toán ở phần 4 dùng được cho mọi $b$, chỉ cần thay số 2 bằng $b$:
- Thập phân → hệ b: chia liên tục cho $b$, ghi số dư, đọc ngược.
- Hệ b → thập phân: Horner,
res = res * b + chữ số.
Khi $b > 10$ thì 10 chữ số 0…9 không đủ dùng, người ta mượn chữ cái: A = 10, B = 11, C = 12, D = 13, E = 14, F = 15, rồi tiếp tục tới Z = 35. Vì vậy hệ lớn nhất hay gặp là hệ 36. Hệ 16 (thập lục phân, hexadecimal) rất phổ biến trong tin học: mã màu #FF8800 trên web chính là ba số hệ 16.
| Thập phân | 0 | 5 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 255 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Nhị phân | 0 | 101 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 | 10000 | 11111111 |
| Bát phân (hệ 8) | 0 | 5 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 20 | 377 |
| Thập lục phân | 0 | 5 | 9 | A | B | C | D | E | F | 10 | FF |
Bảng 10. Một số giá trị ở các hệ thường gặp. Mỗi chữ số hệ 16 ứng với đúng 4 bit, ví dụ $\text{F}_{16} = 1111_2$, nên $255 = 11111111_2 = \text{FF}_{16}$.
Mẹo đổi nhanh giữa hệ 2 và hệ 16. Vì $16 = 2^4$, mỗi chữ số hệ 16 ứng với đúng một nhóm 4 bit. Muốn đổi một số nhị phân sang hệ 16, em chia các bit thành từng nhóm 4 tính từ phải sang (nhóm cuối bên trái thiếu thì thêm số 0 vào đầu), rồi đổi từng nhóm. Ví dụ $1011010_2$: chia thành 0101 và 1010, tức là 5 và 10 (chữ A), vậy $1011010_2 = \text{5A}_{16} = 90$. Tương tự, hệ 8 ứng với nhóm 3 bit vì $8 = 2^3$: $1011010_2$ chia thành 001, 011, 010 là $132_8$. Kiểm tra: $1 \cdot 64 + 3 \cdot 8 + 2 = 90$.
Ví dụ: đổi $255$ sang hệ 16: $255 : 16 = 15$ dư $15$ (chữ F), $15 : 16 = 0$ dư $15$ (chữ F), đọc ngược được $\text{FF}$. Ngược lại, $\text{2A}_{16} = 2 \cdot 16 + 10 = 42$. Em kéo lên mô phỏng ở phần 4, đổi “Hệ b” thành 16 và nhập $n = 255$ để tự kiểm tra nhé. Trong code, ta dùng một xâu DIG = "0123456789ABC…Z" để đổi qua lại giữa giá trị và ký tự chữ số: DIG[r] là ký tự của số dư $r$, còn vị trí của ký tự trong DIG là giá trị của nó.
Xem code C++ / Python: đổi sang hệ b bất kỳ (2 đến 36) và đổi ngược lại (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const string DIG = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string toBase(long long n, int b){ // thập phân -> hệ b
if(n == 0) return "0";
string s = "";
while(n > 0){
s += DIG[n % b]; // số dư 0..b-1 -> ký tự
n /= b;
}
reverse(s.begin(), s.end());
return s;
}
long long fromBase(const string &s, int b){ // hệ b -> thập phân
long long res = 0;
for(char c : s) res = res * b + DIG.find(c);
return res;
}
int main(){
long long n;
int b;
cin >> n >> b;
string s = toBase(n, b);
cout << s << "\n" << fromBase(s, b); // đổi ngược lại để kiểm tra
return 0;
}DIG = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def to_base(n, b): # thập phân -> hệ b
if n == 0:
return "0"
s = ""
while n > 0:
s += DIG[n % b] # số dư 0..b-1 -> ký tự
n //= b
return s[::-1]
def from_base(s, b): # hệ b -> thập phân
res = 0
for c in s:
res = res * b + DIG.index(c)
return res
n, b = map(int, input().split())
s = to_base(n, b)
print(s)
print(from_base(s, b)) # hoặc int(s, b)Các hàm có sẵn. Khi đi thi, nếu đề chỉ cần đổi hệ đơn giản thì dùng hàm có sẵn cho nhanh và ít lỗi. Tuy vậy em vẫn phải biết tự cài, vì nhiều bài cần xử lý từng chữ số trong lúc đổi, hoặc dùng hệ không có hàm sẵn (hệ 3, hệ 7…).
| Việc cần làm | C++ | Python |
|---|---|---|
| Thập phân → nhị phân | bitset<64>(n).to_string() (có số 0 ở đầu, độ dài cố định 64) | bin(n)[2:] hoặc format(n, 'b') |
| Thập phân → hệ 8, hệ 16 | cout << oct << n, cout << hex << uppercase << n | format(n, 'o'), format(n, 'X') |
| Hệ b → thập phân (b ≤ 36) | stoll(s, nullptr, b) | int(s, b) |
| Đếm số bit 1 | __builtin_popcountll(n) | bin(n).count('1') |
| Số bit của n (n > 0) | 64 - __builtin_clzll(n) | n.bit_length() |
| Thập phân → hệ b bất kỳ | tự cài toBase | tự cài to_base |
Bảng 11. Tóm tắt hàm có sẵn. Chú ý cout << hex có tác dụng với mọi lần in số sau đó, muốn quay về hệ 10 phải in dec.
Chương trình dưới đây gói gọn các hàm trong Bảng 11: đọc $n$, một xâu $s$ và hệ $b$; in $n$ ở hệ 2, hệ 8, hệ 16, số bit 1 của $n$, và giá trị thập phân của $s$ (viết ở hệ $b$). Em chạy thử để quen cách gọi từng hàm nhé:
Xem code C++ / Python: các hàm đổi hệ có sẵn trong C++ và Python (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n;
string s;
int b;
cin >> n >> s >> b;
string bits = bitset<64>(n).to_string(); // 64 ký tự, có số 0 ở đầu
bits = bits.substr(min(bits.find('1'), (size_t)63)); // cắt số 0 thừa (giữ "0" nếu n = 0)
cout << bits << "\n";
cout << oct << n << " " << hex << uppercase << n << dec << "\n"; // nhớ quay về dec
cout << __builtin_popcountll(n) << "\n"; // số bit 1
cout << stoll(s, nullptr, b); // xâu s ở hệ b -> thập phân
return 0;
}n, s, b = input().split()
n, b = int(n), int(b)
print(format(n, 'b')) # giống bin(n)[2:]
print(format(n, 'o'), format(n, 'X')) # hệ 8, hệ 16 chữ in hoa
print(bin(n).count('1')) # số bit 1
print(int(s, b)) # xâu s ở hệ b -> thập phân0.2. Quên đọc ngược các số dư: $13$ thành
1011 thay vì 1101.3. Python:
bin(13) trả về '0b1101' có tiền tố 0b, phải cắt bằng [2:] hoặc dùng format(13, 'b'). Tương tự hex() có tiền tố 0x và in chữ thường.- Đếm Chữ Số (Dễ)
- Số Đặc Biệt (Dễ)
- Tìm Số Đảo Ngược (VL18) (Dễ)
- Đổi 1 Chữ Số Để Chia Hết Cho 3 (Dễ)
- Mật Khẩu (PASSWORD) (HSG 12 THPT Lê Quý Đôn Hà Tĩnh 2021-2022) (Dễ)
- Tìm Chữ Số (CHUSO2) (Trung bình)
- Concatenation of Consecutive Binary Numbers (LeetCode 1680) (Trung bình)
Bài tậpLuyện xử lý chữ số và hệ cơ số
Cho số nguyên $n$ ($|n| \le 10^{18}$, có thể âm). Tính tổng các chữ số của $n$ (không tính dấu trừ).
-450716📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
if (n < 0) n = -n; rồi cộng dần n % 10. Với $-4507$: $4 + 5 + 0 + 7 = 16$. Nhớ khai báo long long vì $|n|$ có thể tới $10^{18}$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n;
cin >> n;
if(n < 0) n = -n;
int tong = 0;
while(n > 0){
tong += n % 10;
n /= 10;
}
cout << tong;
return 0;
}n = abs(int(input()))
tong = 0
while n > 0:
tong += n % 10
n //= 10
print(tong)Cho số nguyên $n$ ($0 \le n \le 10^{18}$). Đếm xem trong cách viết thập phân của $n$ có bao nhiêu chữ số chẵn (0, 2, 4, 6, 8).
204814📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
d % 2 == 0 thì tăng biến đếm. Các chữ số chẵn của 20481 là 2, 0, 4, 8. Bẫy: $n = 0$ có một chữ số 0 là số chẵn, đáp án là 1, nhưng vòng while (n > 0) không chạy lần nào. Hãy xử lý riêng, hoặc dùng vòng do … while để thân vòng lặp chạy ít nhất một lần.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n;
cin >> n;
int dem = 0;
do { // chạy ít nhất 1 lần nên đúng cả khi n = 0
if(n % 10 % 2 == 0) dem++;
n /= 10;
} while(n > 0);
cout << dem;
return 0;
}n = int(input())
dem = 0
while True: # chạy ít nhất 1 lần nên đúng cả khi n = 0
if n % 10 % 2 == 0:
dem += 1
n //= 10
if n == 0:
break
print(dem)Cho số nguyên $n$ ($0 \le n \le 10^{18}$). In ra số đảo ngược của $n$ (bỏ các chữ số 0 ở đầu, nếu có).
120303021📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
rev = rev * 10 + n % 10 như phần 2. Đọc ngược 12030 được 03021, bỏ số 0 đầu còn 3021. Cách làm bằng số tự động bỏ các số 0 này. Nếu làm bằng xâu thì phải tự xoá các ký tự 0 ở đầu (và cẩn thận đừng xoá hết khi $n = 0$). Biến rev phải là long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n, rev = 0;
cin >> n;
while(n > 0){
rev = rev * 10 + n % 10;
n /= 10;
}
cout << rev;
return 0;
}n = int(input())
rev = 0
while n > 0:
rev = rev * 10 + n % 10
n //= 10
print(rev)Cho $T$ số nguyên ($T \le 10^5$), mỗi số $n$ thoả $0 \le n \le 10^{18}$. Với mỗi số, in YES nếu đó là số đối xứng (đọc xuôi và ngược như nhau), ngược lại in NO.
4
12321
1221
120
7YES
YES
NO
YES📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
s == s[::-1]; và vì có tới $10^5$ số nên đọc toàn bộ dữ liệu một lần bằng sys.stdin.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
bool doiXung(long long n){
long long m = n, rev = 0; // giữ lại n để so sánh
while(m > 0){
rev = rev * 10 + m % 10;
m /= 10;
}
return rev == n;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
while(T--){
long long n;
cin >> n;
cout << (doiXung(n) ? "YES" : "NO") << "\n";
}
return 0;
}import sys
data = sys.stdin.read().split()
t = int(data[0])
out = []
for s in data[1:t + 1]:
out.append("YES" if s == s[::-1] else "NO")
print("\n".join(out))Cho số nguyên $n$ ($0 \le n \le 10^{18}$). Dòng thứ nhất in biểu diễn nhị phân của $n$ (không có số 0 thừa ở đầu). Dòng thứ hai in số lượng bit 1 trong biểu diễn đó.
131101
3📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
0 và 0. Python có thể dùng thẳng bin(n)[2:].Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n;
cin >> n;
if(n == 0){ cout << "0\n0"; return 0; }
string s = "";
int mot = 0;
while(n > 0){
int r = n % 2;
if(r == 1) mot++;
s += char('0' + r);
n /= 2;
}
reverse(s.begin(), s.end());
cout << s << "\n" << mot;
return 0;
}n = int(input())
s = bin(n)[2:] # bin(13) = '0b1101'
print(s)
print(s.count('1'))Cho hai số nguyên $a, b$ ($1 \le a \le b \le 10^9$, $b - a \le 10^5$). Trong các số từ $a$ tới $b$, tìm số có tổng chữ số lớn nhất; nếu có nhiều số như vậy thì chọn số nhỏ nhất. In ra số đó và tổng chữ số của nó.
15 3129 11📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
tongCS(x) theo khuôn mẫu phần 1, duyệt $x$ từ $a$ tới $b$ và chỉ cập nhật khi tổng lớn hơn hẳn (dấu >, không phải >=) để giữ được số nhỏ nhất khi bằng nhau. Trong ví dụ: 19 và 28 có tổng 10, còn 29 có tổng 11 là lớn nhất.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int tongCS(long long x){
int t = 0;
while(x > 0){ t += x % 10; x /= 10; }
return t;
}
int main(){
long long a, b;
cin >> a >> b;
long long best = a;
int bestT = tongCS(a);
for(long long x = a + 1; x <= b; x++){
int t = tongCS(x);
if(t > bestT){ // > để giữ số nhỏ nhất khi bằng nhau
bestT = t;
best = x;
}
}
cout << best << " " << bestT;
return 0;
}def tong_cs(x):
t = 0
while x > 0:
t += x % 10
x //= 10
return t
a, b = map(int, input().split())
best, best_t = a, tong_cs(a)
for x in range(a + 1, b + 1):
t = tong_cs(x)
if t > best_t: # > để giữ số nhỏ nhất khi bằng nhau
best, best_t = x, t
print(best, best_t)Cho số nguyên $a$, xâu $s$ và số nguyên $c$ ($2 \le a, c \le 36$). Xâu $s$ là một số viết trong hệ $a$, dùng các chữ số 0–9 và chữ in hoa A–Z (A = 10, …, Z = 35), không có số 0 thừa ở đầu, và giá trị của nó không vượt quá $10^{18}$. Hãy in số đó khi viết trong hệ $c$ (dùng chữ in hoa).
16 FF 211111111📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long, rồi chia liên tục cho $c$ để đổi sang hệ $c$ (phần 5). $\text{FF}_{16} = 15 \cdot 16 + 15 = 255 = 11111111_2$. Với Python: int(s, a) làm xong bước một. Nhớ trường hợp giá trị bằng 0.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const string DIG = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main(){
int a, c;
string s;
cin >> a >> s >> c;
long long v = 0;
for(char ch : s) v = v * a + DIG.find(ch); // hệ a -> thập phân
if(v == 0){ cout << 0; return 0; }
string t = "";
while(v > 0){ // thập phân -> hệ c
t += DIG[v % c];
v /= c;
}
reverse(t.begin(), t.end());
cout << t;
return 0;
}DIG = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
a, s, c = input().split()
a, c = int(a), int(c)
v = int(s, a) # hệ a -> thập phân
t = ""
while v > 0: # thập phân -> hệ c
t += DIG[v % c]
v //= c
print(t[::-1] if t else "0")Cho hai số nguyên $n$ và $b$ ($1 \le n \le 10^6$, $2 \le b \le 16$). Đếm số lượng số $x$ trong đoạn $[1, n]$ sao cho $x$ đối xứng cả khi viết trong hệ 10 lẫn khi viết trong hệ $b$.
10 25📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
rev = rev * b + x % b rồi so sánh với $x$ (đúng phần 2, chỉ thay 10 bằng $b$). Duyệt mọi $x$ từ 1 tới $n$ và gọi hàm hai lần, với hệ 10 và hệ $b$. Mẹo tăng tốc: kiểm tra hệ 10 trước, vì rất ít số qua được bước này. Trong ví dụ có 5 số: $1 = 1_2$, $3 = 11_2$, $5 = 101_2$, $7 = 111_2$, $9 = 1001_2$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
bool doiXung(long long x, int b){
long long m = x, rev = 0;
while(m > 0){
rev = rev * b + m % b; // đảo ngược trong hệ b
m /= b;
}
return rev == x;
}
int main(){
int n, b;
cin >> n >> b;
int dem = 0;
for(int x = 1; x <= n; x++)
if(doiXung(x, 10) && doiXung(x, b)) dem++;
cout << dem;
return 0;
}def doi_xung(x, b):
m, rev = x, 0
while m > 0:
rev = rev * b + m % b # đảo ngược trong hệ b
m //= b
return rev == x
n, b = map(int, input().split())
dem = 0
for x in range(1, n + 1):
s = str(x)
if s == s[::-1] and doi_xung(x, b): # hệ 10 kiểm tra bằng xâu cho nhanh
dem += 1
print(dem)
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét