Hướng dẫn giải của Chuyển số sang cách đọc
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu viết một chương trình để chuyển đổi một số nguyên trong khoảng [0, 1000] sang dạng văn bản tiếng Việt không dấu. Các quy tắc đặc biệt cần tuân thủ bao gồm: sử dụng 'tư' thay cho 'bốn' ở một số trường hợp, 'linh' thay cho 'lẻ', và 'nghìn' cho số 1000. Với các số khác, cần đọc đúng số hàng trăm, hàng chục và hàng đơn vị.
Các cách tiếp cận
Cách Phân tích từng phần (Phương pháp trực tiếp)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string d[] = {"khong", "mot", "hai", "ba", "bon", "nam", "sau", "bay", "tam", "chin"};
string doc_so(int n) {
if (n == 0) return "khong";
if (n == 1000) return "mot nghin";
string res = "";
int hang_tram = n / 100;
int hang_chuc = (n / 10) % 10;
int hang_don_vi = n % 10;
// Đọc hàng trăm
if (hang_tram > 0) {
res += d[hang_tram] + " tram";
if (hang_chuc == 0 && hang_don_vi != 0) {
res += " linh";
}
}
// Đọc hàng chục
if (hang_chuc > 0) {
if (!res.empty()) res += " ";
if (hang_chuc == 1) {
res += "muoi";
} else {
res += d[hang_chuc] + " muoi";
}
}
// Đọc hàng đơn vị
if (hang_don_vi > 0) {
if (!res.empty()) res += " ";
// Quy tắc đặc biệt cho các số
if (hang_don_vi == 1 && hang_chuc > 1) res += "mot";
else if (hang_don_vi == 5 && hang_chuc > 0) res += "lam";
else if (hang_don_vi == 4) {
// Quy tắc dùng 'tư': có hàng chục >= 2 hoặc có hàng trăm mà không có hàng chục
if (hang_chuc >= 2 || (hang_chuc == 0 && hang_tram > 0)) {
res += "tu";
} else {
res += "bon";
}
} else {
res += d[hang_don_vi];
}
}
return res;
}
int main() {
int T;
if (cin >> T) {
while (T--) {
int n;
cin >> n;
cout << doc_so(n) << endl;
}
}
return 0;
}
- Time Complexity: O(T)
- Space Complexity: O(1)
Phương pháp này chia nhỏ số thành các phần: hàng trăm, hàng chục, hàng đơn vị. Dựa vào các phần này, ta ghép chuỗi lại theo quy tắc:
- Hàng trăm: Nếu > 0, đọc số rồi thêm 'tram'. Nếu hàng chục là 0 và hàng đơn vị khác 0, thêm 'linh'.
- Hàng chục: Nếu > 0, kiểm tra nếu là 1 thì chỉ thêm 'muoi', ngược lại thêm số và 'muoi'.
- Hàng đơn vị: Nếu > 0, áp dụng các quy tắc thay thế:
- Số 1: nếu có hàng chục (từ 2 trở lên), đọc là 'mot'.
- Số 5: nếu có hàng chục, đọc là 'lam'.
- Số 4: nếu có hàng chục >= 2 hoặc có hàng trăm mà hàng chục là 0, đọc là 'tu', ngược lại là 'bon'.
- Các số khác: đọc mặc định. Phương pháp này xử lý các trường hợp biên một cách tường minh.
Cách Quản lý trạng thái chuỗi (Tối ưu hóa)
#include <bits/stdc++.h>
using namespace std;
string d[] = {"khong","mot","hai","ba","bon","nam","sau","bay","tam","chin"};
string f(int n)
{
if (n == 0) return "khong";
if (n == 1000) return "mot nghin";
string r = "";
int t = n / 100;
int c = (n / 10) % 10;
int v = n % 10;
if (t > 0)
{
r += d[t] + string(" tram");
if (c == 0 && v != 0) r += " linh";
}
if (c > 0)
{
if (!r.empty()) r += " ";
if (c == 1) r += "muoi";
else r += d[c] + string(" muoi");
}
if (v > 0)
{
if (!r.empty()) r += " ";
if (v == 1 && c > 1) r += "mot";
else if (v == 5 && c > 0) r += "lam";
else if (v == 4)
{
if (c == 0 && t > 0) r += "tu";
else if (c >= 2) r += "tu";
else r += "bon";
}
else r += d[v];
}
return r;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
cout << f(n) << "\n";
}
return 0;
}
- Time Complexity: O(T)
- Space Complexity: O(1)
Đây là biến thể của phương pháp trực tiếp, sử dụng các biến tạm để lưu trữ phần nguyên của phép chia. Code được tối ưu hóa cú pháp C++ (sử dụng string concatenation thay vì stringstream). Logic cơ bản giữ nguyên: kiểm tra từng hàng, xử lý các trường hợp đặc biệt của số 4, 5, 1 dựa trên việc hàng chục và hàng trăm có tồn tại hay không. Việc kiểm tra !r.empty() đảm bảo không có dấu cách thừa ở đầu chuỗi.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(T) | O(1) | Phân tích từng phần (Phương pháp trực tiếp) |
| 2 | O(T) | O(1) | Quản lý trạng thái chuỗi (Tối ưu hóa) |
Bài học kinh nghiệm
- Việc chia số thành các phần (hàng trăm, chục, đơn vị) là chìa khóa để xử lý logic đọc số.
- Các quy tắc 'tư', 'lam', 'mot' phụ thuộc vào ngữ cảnh (có hàng chục hay không), nên cần kiểm tra các biến hàng xóm.
- Trường hợp 'linh' chỉ xuất hiện khi có hàng trăm, hàng chục là 0 và hàng đơn vị khác 0.
Lỗi thường gặp
- Quên xử lý trường hợp số 0 (cần in 'khong') và số 1000 (cần in 'mot nghin') riêng biệt vì logic chung không bao涵盖 hết.
- Lỗi logic với số 4: 'tư' chỉ dùng khi có hàng chục >= 2 hoặc có hàng trăm mà không có hàng chục. Nếu chỉ có hàng chục là 1 (ví dụ 14), ta vẫn dùng 'bon' (muoi bon) hay đúng là 'muoi tu' theo ví dụ mẫu? Xem xét kỹ sample: 14 -> 'muoi bon'. Trong code accepted, điều kiện cho 'tu' là
if (c == 0 && t > 0) ... else if (c >= 2) .... Với 14,c=1, không thỏa mãn điều kiện nào để thành 'tu' nên mặc định là 'bon'. Điều này khớp sample. - Thêm dấu cách thừa: Cần kiểm tra chuỗi r có rỗng trước khi thêm dấu cách trước các phần tiếp theo.
Bình luận