Đảo số: recursion và iteration

Bối cảnh

Một cổng kiểm tra mã thiết bị cần đọc một số nguyên không âm rồi đảo thứ tự các chữ số để tạo mã phản chiếu. Ví dụ 12030 trở thành 3021; các số 0 ở đầu của kết quả sau đảo không được giữ vì output là một số nguyên. Nhóm phát triển đang chuyển một đoạn code từ vòng lặp sang recursion và muốn xác nhận hai cách cài đặt cho kết quả giống nhau trên cùng input.

Bạn phải viết cả hai phiên bản. Với recursion, cách trực tiếp nhất là dùng một accumulator rev: mỗi tầng lấy chữ số cuối n%10, ghép vào cuối accumulator bằng rev*10 + digit, rồi gọi tiếp với n/10. Đây là tail recursion và giúp minh họa rõ "state" của một lời gọi. Phiên bản loop dùng đúng invariant đó để làm chuẩn đối chiếu. Bài Medium vì người học phải hiểu không chỉ call stack mà còn cách mang trạng thái tích lũy qua các tầng, xử lý n=0 và các chữ số 0 ở cuối số ban đầu.

Yêu cầu

1. Đọc n.
2. Viết hàm recursion đảo số bằng accumulator.
3. Viết phiên bản loop có cùng contract.
4. In hai kết quả rec loop.
5. Hai kết quả phải bằng nhau.

Yêu cầu tổ chức code

Phải có cả hàm recursion và phiên bản loop.

Online Judge chấm output. Giảng viên có thể review source code để xác nhận học viên dùng đúng recursion và không vượt prerequisite.

Input

Một số nguyên không âm n.

Output

Một dòng rec loop.

Ràng buộc

0 ≤ n ≤ 10^18-1.

Ví dụ 1

Input

12030

Output

3021 3021

Giải thích

Với n=12030, recursion bắt đầu rev=0. Tầng đầu lấy 0 nên rev vẫn 0, rồi n thành 1203. Các tầng tiếp theo lần lượt ghép 3,2,0,1: 0→3→32→320→3021. Khi n về 0, hàm trả 3021. Vòng lặp thực hiện đúng các cập nhật này nên cũng cho 3021. Vì vậy output là 3021 3021.

Ví dụ 2

Input

0

Output

0 0

Giải thích

Input 0 là trường hợp không có chữ số nào cần tách thêm. Hàm recursion được gọi với state (n=0, rev=0) và chạm base case ngay, trả accumulator 0. Phiên bản loop cũng kiểm tra n>0; điều kiện sai ngay từ đầu nên vòng lặp không chạy và rev vẫn là 0. Hai cách có cùng invariant và cùng kết quả, vì vậy output là 0 0.

Thông tin học tập

• Module: M04
• Buổi: B14
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: recursion vs iteration, tail recursion, digit processing, accumulator
• Giới hạn kiến thức: B01-B14
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100