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

F₁=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: 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.

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;
}