Đề bài
Bắt đầu từ một số dương n bất kỳ, quy tắc Collatz cho số hạng tiếp theo là n / 2 nếu n chẵn và 3n + 1 nếu n lẻ, dãy dừng lại khi chạm tới 1. Dãy của 6 là 6, 3, 10, 5, 16, 8, 4, 2, 1: chín số hạng. Trong tất cả các số bắt đầu từ 1 đến limit, hãy tìm số có dãy nhiều số hạng nhất.
Hãy viết longest_collatz_chain(limit).
Các dãy thường có chung phần đuôi, nên ghi nhớ độ dài đã tính cho từng số sẽ tiết kiệm rất nhiều công sức. Các số hạng ở giữa có thể vượt quá giới hạn; hãy dùng số nguyên 64 bit.
Đầu vào
limit: Số bắt đầu lớn nhất cần thử.
Đầu ra
Trả về số bắt đầu có dãy nhiều số hạng nhất (tính cả số bắt đầu và số 1 cuối cùng). Nếu có nhiều số bằng nhau, trả về số nhỏ nhất.
Ràng buộc
1 ≤ limit ≤ 100,000
Ví dụ
Đầu vào:
limit = 6
Kết quả mong đợi:
expected = 6
Đầu vào:
long long limit = 6;
Kết quả mong đợi:
long long expected = 6;
Đầu vào:
long limit = 6;
Kết quả mong đợi:
long expected = 6;
Giải thích
Độ dài dãy của các số từ 1 đến 6 lần lượt là 1, 2, 8, 3, 6 và 9 số hạng, nên đáp án là 6.
Đầu vào:
limit = 10
Kết quả mong đợi:
expected = 9
Đầu vào:
long long limit = 10;
Kết quả mong đợi:
long long expected = 9;
Đầu vào:
long limit = 10;
Kết quả mong đợi:
long expected = 9;
Giải thích
9 cho 20 số hạng (9, 28, 14, 7, ...), nhiều hơn mọi số bắt đầu khác đến 10, nên đáp án là 9.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Trước hết hãy đếm số hạng của một dãy, tính cả số bắt đầu và số 1.
Gợi ý 2
Khi dãy chạm tới một số đã biết độ dài, cộng luôn độ dài đó thay vì đi tiếp.
Gợi ý 3
Chỉ thay số bắt đầu tốt nhất khi độ dài lớn hơn hẳn.
Độ phức tạp mong đợi
thời gian O(limit × average new steps), bộ nhớ phụ O(limit)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.