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 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!
-
0
longdegea11
11:40 p.m. 7 Tháng 6, 2023
←
chỉnh sửa 2
→
-
-2
villeclaude
4:03 p.m. 25 Tháng 4, 2023
-
0
161007thanhhiu
7:48 p.m. 21 Tháng 8, 2023
-
3
tk22NguyenHongPhuc
11:51 a.m. 3 Tháng 3, 2024
-
0
kietlqt
9:28 a.m. 31 Tháng 5, 2024
-
-4
nguyenthanhtai24122013
3:08 p.m. 31 Tháng 8, 2024
-
1
kietlqt
3:56 p.m. 31 Tháng 8, 2024
-
-2
Kuze
3:58 p.m. 31 Tháng 8, 2024
-
1
kietlqt
4:00 p.m. 31 Tháng 8, 2024
5 bình luận nữaTheo như mình thấy thì: Si = F(i + 3) - 1 nếu nhân ma trận, còn theo công thức thì đúng rồi
.
nhân như nào hả bạn ?
ko biết thì học
đúng zại
đúng quá đúng
sai bạn sai
Ko biết thì học sao lại sai . Người ta có câu
Ko biết phải hỏi muốn giỏi phải họcthôi . Chứ chẳng lẽ bạn ko học vẫn giỏi à . Cái ngữ chỉ chờ có code để chép như bạn thì nói làm gì . Ko có code thì nói người ta sai . Bạn chỉ là con chó chỉ biết ngồi chờ code mà cắn .chửi gắt thế:)
Chứ nó cứ hầm hầm ấy . Người ta ko co code cứ nói là gay ở đây nè . Thấy tức ko !!!