Đề bài
Dãy Fibonacci bắt đầu với F(1) = 1, F(2) = 1, và mỗi số hạng tiếp theo bằng tổng hai số hạng đứng trước: 1, 1, 2, 3, 5, 8, 13, 21, ... Hãy tìm vị trí mà dãy lần đầu đạt n chữ số thập phân. Các số hạng sớm vượt quá số nguyên 64 bit, nên nếu ngôn ngữ của bạn không có số nguyên lớn, hãy cộng chúng dưới dạng mảng chữ số.
Hãy viết fibonacci_with_n_digits(n).
Đầu vào
n: Số chữ số.
Đầu ra
Trả về chỉ số i của số hạng F(i) đầu tiên có ít nhất n chữ số. Với n = 1 thì đáp án là 1.
Ràng buộc
1 ≤ n ≤ 1000
Ví dụ
Đầu vào:
n = 2
Kết quả mong đợi:
expected = 7
Đầu vào:
long long n = 2;
Kết quả mong đợi:
long long expected = 7;
Đầu vào:
long n = 2;
Kết quả mong đợi:
long expected = 7;
Giải thích
F(6) = 8 có một chữ số và F(7) = 13 có hai chữ số, nên đáp án là 7.
Đầu vào:
n = 4
Kết quả mong đợi:
expected = 17
Đầu vào:
long long n = 4;
Kết quả mong đợi:
long long expected = 17;
Đầu vào:
long n = 4;
Kết quả mong đợi:
long expected = 17;
Giải thích
F(16) = 987 và F(17) = 1597, nên đáp án là 17.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Chỉ giữ lại hai số hạng gần nhất.
Gợi ý 2
Lưu mỗi số hạng dưới dạng chữ số và cộng có nhớ.
Gợi ý 3
Đếm chỉ số trong lúc tính, bắt đầu từ F(1) = 1.
Độ phức tạp mong đợi
thời gian O(n²), bộ nhớ phụ O(n)
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.