Định dạng số

Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Dễ Đệ quy Tách chữ số

Đề bài

Cho số nguyên dương $N$. Hãy in ra kết quả số $N$ ở định dạng: từ phải qua trái, cứ đủ 3 chữ số và vẫn còn phần bên trái thì có dấu phẩy ngăn cách.

Input: gồm 1 dòng chứa số nguyên dương $N$ $(1 \le N \le 10^{18})$.

Output: in ra định dạng của số $N$ theo như yêu cầu.

Lưu ý của đề

Bài này không dùng mảng hay chuỗi nhé, chỉ sử dụng các biến bình thường.

Ví dụ 1 – input

1234

Ví dụ 1 – output

1,234

Ví dụ 2 – input

123456

Ví dụ 2 – output

123,456

Ví dụ 3 – input

1234567

Ví dụ 3 – output

1,234,567

Ví dụ 4 – input

123

Ví dụ 4 – output

123

Lời mở đầu

Nếu được dùng chuỗi thì bài này chỉ là chèn dấu phẩy. Nhưng đề cấm mảng và chuỗi, nên ta phải "bóc" số bằng phép chia – và gặp ngay một rắc rối: phép % 1000 lấy ra nhóm 3 chữ số bên phải trước, trong khi phải in nhóm bên trái trước. Đệ quy giải quyết rắc rối này cực gọn, vì ngăn xếp lời gọi tự "đảo ngược" thứ tự giúp ta. Đây là bài rất hay để hiểu làm việc trước hay sau lời gọi đệ quy khác nhau thế nào.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngTrái trước, phải sauCodeC++ & Python

Bộ testBộ test chính thức có gì?

Bộ test có 100 test, mỗi test là một số $N$. Đề không chia subtask, và bộ test cũng không chia nhóm: độ dài $N$ trải đều từ 1 đến 18 chữ số, lẫn lộn giữa các test.

Số test	N nhỏ nhất	N lớn nhất	Số chữ số	Có nhóm bắt đầu bằng 0
100	2	923 713 280 435 293 013	1 … 18	21 test

Điều đáng chú ý nhất: có 21 test chứa một nhóm 3 chữ số ở giữa/cuối bắt đầu bằng 0 (kiểu ...,076,...). Đây chính là các test "bẫy" dành cho bạn nào in nhóm bằng n % 1000 mà quên bù số 0.

Ý tưởngIn phần bên trái trước, rồi mới in 3 chữ số cuối

Với $n \ge 1000$, kết quả của $n$ gồm hai phần ghép lại:

• Phần bên trái là $n / 1000$ (bỏ 3 chữ số cuối) – được định dạng theo đúng quy tắc cũ, tức là bài toán con cùng dạng, nhỏ hơn.
• Phần bên phải là dấu phẩy và đúng 3 chữ số cuối $n \bmod 1000$.

Hàm đệ quy inSo(n)

Nếu $n < 1000$: in $n$ rồi dừng (điểm dừng). Ngược lại: gọi inSo(n / 1000) trước, rồi mới in , và 3 chữ số của $n \bmod 1000$.

Vì lời gọi đệ quy đứng trước lệnh in, máy phải đi xuống tận nhóm trái nhất rồi mới in, sau đó in dần các nhóm còn lại khi quay lên. Chú ý nhóm 3 chữ số phải in đủ 3 chữ số: $1005$ phải ra 1,005 chứ không phải 1,5.

Em nhập $N$ rồi bấm Tiếp để xem các lời gọi đi xuống và màn hình được in ra lúc quay lên:

N =

Ví dụ nhanh:

CodeCài đặt

C++▶ Chạy tay từng dòng codeGọi đệ quy cho phần bên trái trước, in 3 chữ số cuối sau.

Dữ liệu vào (stdin) – sửa thoải mái1234567

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. if(n < 1000) là điểm dừng: còn tối đa 3 chữ số thì in thẳng, không có số 0 thừa ở đầu (nhóm trái nhất được phép ngắn hơn 3 chữ số).
2. inSo(n / 1000) đứng trước lệnh in – đây là mấu chốt để các nhóm in ra theo đúng thứ tự từ trái sang phải.
3. In 3 chữ số của r bằng r / 100, r / 10 % 10, r % 10 để giữ số 0 ở đầu nhóm. Cách khác tương đương: printf(",%03d", r).
4. $N \le 10^{18}$ vừa trong long long. Độ sâu đệ quy tối đa 7 lời gọi (19 chữ số).

Không gian$O(\log_{1000} N)$ – độ sâu đệ quy

Thời gian$O(\log_{1000} N)$

Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất chỉ 0.004 giây. Python đúng 100/100 test, test chậm nhất chỉ 0.025 giây.

Lỗi hay gặp: quên giữ số 0 đầu nhóm

Nếu viết cout << ',' << n % 1000; thì $1005$ in ra 1,5, còn $2000$ in ra 2,0. Mình chạy thử bản sai này trên bộ test: chỉ đúng 79/100 test, sai 21 test – đúng bằng số test có một nhóm (không phải nhóm đầu) bắt đầu bằng chữ số 0.

Ghi chú của mình: code trên (C++) đúng 100/100 test, chậm nhất 0.004 giây; bản Python cũng đúng hết. Bài nhỏ nhưng là ví dụ rõ nhất cho "việc làm sau lời gọi đệ quy được thực hiện theo thứ tự ngược lại" – mẹo này còn dùng để in ngược một số, in số ở hệ cơ số khác, duyệt cây...

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇