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
Mình xin phép trình bày 1 cách giải bài này như sau:
Ta có:
F(0) + F(1) + F(2) + ... + F(n) = F(n+2) - 1 (Đẳng thức của dãy Fibonanci, các bạn có thể xem ở đây: https://vi.wikipedia.org/wiki/D%C3%A3y_Fibonacci)
F(n + 1) = F(n) + F(n - 1)
F(n + 2) = F(n) + F(n + 1) = F(n) + F(n) + F(n - 1) = 2 * F(n) + F(n - 1)
Đến đây thì các bạn nhân ma trận là xong!
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
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)
nhân ma trận tìm số fibo thứ n+3 rồi lấy kết quả -1
Mình xin phép trình bày lời giải của bài toán này như sau:
Gọi \(F_0=F_2-1\text{ }(F_2=2\) theo quy luật ban đầu\()\)
Gọi \(S_i=F_0+F_1+F_2+...+F_i\)
Ta có: \(S_0=F_0=F_2-1\)
Thực hiện quy nạp như trên, ta có công thức: \(S_i=F_{i+2}-1\)
Đến đây chỉ cần thực hiện nhân ma trận là xong!