Độ bền nhân của một số

Bối cảnh

Trong một trò chơi số học, một số nguyên không âm được biến đổi bằng cách nhân tất cả các chữ số của nó. Quá trình lặp lại cho đến khi kết quả chỉ còn một chữ số. Số bước biến đổi được gọi là độ bền nhân (multiplicative persistence). Ví dụ 39 → 27 → 14 → 4, nên độ bền là 3 và chữ số cuối cùng là 4.

Bạn phải cài cả phiên bản recursion và iteration rồi in kết quả của cả hai để đối chiếu. Phần recursion gồm hai lớp: một hàm đệ quy nhỏ tính tích chữ số của một số, và một hàm đệ quy ngoài áp dụng phép biến đổi lặp lại cho đến base case n<10. Phiên bản loop thực hiện cùng contract. Bài Medium vì người học phải phân biệt recursion "bên trong một bước" với recursion "lặp lại nhiều bước", đồng thời kiểm soát trường hợp chứa chữ số 0 — khi tích trở thành 0, quá trình sẽ kết thúc ngay ở bước kế tiếp.

Yêu cầu

1. Đọc n.
2. Viết hàm đệ quy tính tích chữ số.
3. Viết hàm recursion tính số bước và chữ số cuối.
4. Viết phiên bản loop tương đương.
5. In recSteps recDigit loopSteps loopDigit.

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

Phải có cả phiên bản recursion và iteration.

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 gồm bốn số recSteps recDigit loopSteps loopDigit.

Ràng buộc

0 ≤ n ≤ 10^18-1.

Ví dụ 1

Input

39

Output

3 4 3 4

Giải thích

Quá trình recursive bắt đầu với 39. Tích chữ số là 3×9=27, nên bước 1 đưa số về 27. Tiếp theo 2×7=14 là bước 2; rồi 1×4=4 là bước 3. Vì 4 chỉ có một chữ số, base case dừng và trả digit=4. Phiên bản loop thực hiện cùng ba biến đổi, nên output là 3 4 3 4.

Ví dụ 2

Input

7

Output

0 7 0 7

Giải thích

Input 7 đã là số một chữ số. Cả recursion và loop đều chạm điều kiện dừng trước khi thực hiện phép nhân chữ số, nên số bước bằng 0 và chữ số cuối là chính 7. Output vì thế là 0 7 0 7.

Thông tin học tập

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