Đề bài
Dãy Fibonacci bắt đầu với 0, 1 và mỗi số tiếp theo là tổng của hai số liền trước: 0, 1, 1, 2, 3, 5, 8, …. F(0) = 0 và F(1) = 1.
Cài đặt fibonacci(n).
Đầu vào
n: Vị trí trong dãy số.
Đầu ra
Trả về F(n).
Ràng buộc
0 ≤ n ≤ 90
Ví dụ
Ví dụ 1
Đầu vào:
n = 10
Kết quả mong đợi:
expected = 55Đầu vào:
long long n = 10;
Kết quả mong đợi:
long long expected = 55;Đầu vào:
long n = 10;
Kết quả mong đợi:
long expected = 55;Giải thích
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55: F(10) = 55.
Ví dụ 2
Đầu vào:
n = 0
Kết quả mong đợi:
expected = 0Đầu vào:
long long n = 0;
Kết quả mong đợi:
long long expected = 0;Đầu vào:
long n = 0;
Kết quả mong đợi:
long expected = 0;Giải thích
Theo định nghĩa F(0) = 0.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Hai giá trị đầu đã cố định, nên hãy bắt đầu từ các trường hợp cơ sở.
Gợi ý 2
Tạo các giá trị sau từ hai giá trị trước thay vì tính lại đệ quy.
Gợi ý 3
Dùng cách lặp để tránh tính lặp và đệ quy quá sâu.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(1)
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.