02/10/2018, 14:01
BCFIBO spoj – Số fibonacci
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCFIBO/ 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: F 0 =0 F 1 =1 F n =F n-1 +F n-2 với n≥2. Một số phần tử đầu tiên của dãy Fibonacci: ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCFIBO/
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
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.
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++
#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;
}
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; } |
