Tổng Fibonaci
Xem PDF
Điểm:
1600 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Xét dãy số Fibonacci \({Fn}\) theo định nghĩa:
- \(𝐹_0=𝐹_1=1\)
- \(𝐹_n=𝐹_{n-1}+𝐹_{n-2}\ ∀𝑛>1\)
Yêu cầu: Cho số \(𝒏\), hãy tính tổng \(𝑆=𝐹_0+𝐹_1+𝐹_2+⋯+𝐹_𝑛\) và đưa ra số dư của \(S\) chia cho (\(10^9+7\)).
Input
- Chỉ một dòng duy nhất ghi số nguyên dương \(n\) (\(𝑛≤10^{15}\)).
Output
- Ghi một số nguyên \(S\) – số dư tìm được.
Example
Test 1
Input
3 Output
7Note
- \(S = 1+1+2+3\)
Test 1
Input
5 Output
20Note
- \(S = 1+1+2+3+5+8\)
Nguồn: CĐ DHBB
Bình luận
lời giải của em bị sai ở đâu vậy:
def fibo(n):
if n == 1 or n == 0:
return n
else:
return fibo(n - 1) + fibo(n - 2)
n = int(input()) + 2
tg = fibo(n)
print(tg - 1)
-
1
iq2000laday
3:17 p.m. 20 Tháng 6, 2024
←
chỉnh sửa 2
→
5 bình luận nữaNó không sai đâu em, mà là nó chạy chậm quá đó. Fibonacci em không nên dùng đệ quy nha, vì muốn tính \(F_n\) giống như em thì độ phức tạp là \(O(2^n)\) lận, \(n\) càng lớn thì em hiểu rồi đó 🙂