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

Số Fibonacci đầu tiên có n chữ số

Tìm vị trí của số Fibonacci đầu tiên có n chữ số.

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

  • Cộng hai mảng chữ số
  • Sinh số hạng Fibonacci mà không tràn số
  • Dừng ở số hạng đầu tiên thỏa điều kiện

Đề bài

Xem bản gốc (English)

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ụ

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

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

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.