Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCFIBO/
Nội dung bài viết
1. Đề bài Số fibonacci
BCFIBO spoj PTIT Số fibonacci pascal tin học
Số Fibonacci được xác định bởi công thức sau:
F0=0
F1=1
Fn=Fn-1+Fn-2 với n≥2.
Một số phần tử đầu tiên của dãy Fibonacci: 0,1,1,2,3,5,8,….
Tìm số Fibonacci thứ n.
Input
Một số nguyên dương duy nhất n (n≤1 000 000).
Output
Một số nguyên duy nhất là số Fibonacci thứ n (kết quả lấy phần dư cho 1 000 000 007).
Example
Input:
6
Output:
8
Input:
20
Output:
6765
2. Code tham khảo Số fibonacci
a. Code fibonacci pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | const du=1000000007; var i,F1,F0,F,n:longint; begin readln(n); f0:=0; f1:=1; if n<2 then begin writeln(n); exit; end else for i:=2 to n do begin F:=(f0+f1) mod du; F0:=F1; F1:=F; end; writeln(F); end. |
b. Code fibonacci c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <stdio.h> #define base 1000000007; int fibo(int n) { if (n==0) return 0; if (n==1) return 1; int i,f1=0,f2=1,f; for (i=2; i<=n; i++) { f=(f1+f2)%base; f1=f2; f2=f; } return f; } int main() { int n; scanf("%d",&n); printf("%d",fibo(n)); return 0; } |
Bài viết liên quan
- P167PROE spoj PTIT – ROUND 7E – Phương trình
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- PTIT016D spoj PTIT- ACM PTIT 2016 D – Biểu thức
- Spoj PTIT PTIT016C – ACM PTIT 2016 C – Chẵn lẻ
- PTIT127A spoj PTIT – Tổ chức kì thi
- P164SUMI spoj PTIT – ROUND 4I – Next round
- PTIT135J spoj PTIT – Tính lãi suất
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
- P156PROE spoj PTIT – ROUND 6E – Phép dịch
- P156SUMH spoj PTIT – ROUND 6H – Kim cương
Chào bạn,
Mình gặp bài tương tự như bài này, nhưng có thêm điều kiện là 1 ≤ n ≤ 10^12, mình dùng Free Pascal, với compiler 32bit, theo mình tìm hiểu, thì không dùng được kiểu int64, mình google mãi mà không tìm được giải pháp. Bạn vui lòng hướng dẫn giúp mình được không ạ?
Xin chân thành cám ơn.
Bạn tham khảo về Nhân ma trận trên google giúp mình nha 😀
Cám ơn bạn.