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:

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.

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

3 thoughts on “BCFIBO spoj – Số fibonacci

  1. 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.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *