Đề

Viết hàm đệ quy nhi_phan(n) trả về chuỗi biểu diễn nhị phân (hệ cơ số 2) của số nguyên ~n \ge 0~. Tự tìm trường hợp cơ sở bằng ba câu hỏi của mục 5.6.2:

1. Trường hợp nhỏ nhất biết ngay đáp án là gì?
2. Bài toán nhỏ hơn cùng loại là gì?
3. Có đáp án bài nhỏ rồi thì ghép thế nào?

Chương trình chính đọc T số, với mỗi số in chuỗi nhị phân của nó.

Dữ liệu vào

• Dòng đầu: số nguyên ~T~.
• ~T~ dòng tiếp theo, mỗi dòng một số nguyên ~n~.

Kết quả

~T~ dòng; dòng thứ ~i~ là biểu diễn nhị phân của số thứ ~i~, không có chữ số 0 thừa ở đầu (riêng ~n = 0~ in 0) và không có tiền tố 0b.

Ràng buộc

• ~1 \le T \le 1000~.
• ~0 \le n \le 10^{18}~ (biểu diễn nhị phân dài tối đa 60 chữ số, đệ quy không quá 60 tầng).

Ví dụ

Dữ liệu vào:

3
13
0
8

Kết quả:

1101
0
1000

Giải thích ví dụ

Đổi 13 sang nhị phân bằng cách chia liên tiếp cho 2, ghi lại số dư; đọc các số dư từ dưới lên:

Đọc từ dưới lên: 1, 1, 0, 1 → 1101 (= 8 + 4 + 0 + 1). Số dư cuối cùng n % 2 là chữ số hàng đơn vị, nằm ở bên phải chuỗi của ~n // 2~.

• ~n = 0~ in 0 (không phải dòng trống).
• ~n = 8 = 2^3~ in 1000.

Ghi chú

• Máy chấm chỉ so kết quả, không kiểm được hàm có đệ quy hay không, có dùng bin()/format() hay không. Yêu cầu "viết hàm đệ quy nhi_phan" là phần giảng viên kiểm khi chấm tay.
• Chú ý cả hai đầu: ~n = 0~ và ~n = 1~ phải in đúng 0 và 1; số dương không được có chữ số 0 ở đầu.
• bin(13) cho '0b1101', có tiền tố 0b — in thẳng là sai.
• Hàm đệ quy thiếu trường hợp cơ sở sẽ dừng với RecursionError (Runtime Error).

Nguồn trong sách: Bài C5-11, mục 5.10, giáo trình "Lập trình cơ sở với Python" — TS. Nguyễn Quốc Long · Mức: (****)