Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Dãy Collatz dài nhất

Tìm số bắt đầu không vượt quá giới hạn có dãy Collatz dài nhất.

Bạn sẽ học được gì

  • Sinh một dãy Collatz
  • Lưu kết quả để tránh tính lặp
  • Khi có nhiều kết quả bằng nhau, chọn giá trị nhỏ nhất

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.