Viết chương trình tính so thứ hạng n của dãy finonacci

Đề bài: tìm số Fibonacci thứ (n), biết số Fibonacci thứ n được tính theo công thức sau
- nếu n = 1 hoặc n = 2 thì F(n) = 1
- nếu n>2 thì F(n) = F(n-1) + F(n-2)

Cách 1: dùng vòng lặp và mảng

#include 

int main(){
    int n;
    printf("Nhap n: ");
    scanf("%d",&n);
    int F[n+1];
    F[1]=1;
    F[2]=1;
    for(int i=3;i<=n;i++){
        F[i]=F[i-1]+F[i-2];
    }
    printf("F(%d) = %d",n,F[n]);
    return 0;
}

Cách 2: dùng vòng lặp, không dùng mảng

#include 

int main(){
     int n;
     printf("Nhap n: ");
     scanf("%d",&n);
     int f,f1,f2;
     f=f1=f2=1;
     for(int i=3;i<=n;i++){
        f=f1+f2;
        f1=f2;
        f2=f;
     }
     printf("F(%d) = %d",n,f);
     return 0;
}

Cách 3: dùng đệ quy

#include 

int Fibo(int n){
    if (n==1 || n==2)
        return 1;
    else
        return Fibo(n-1)+Fibo(n-2);
}
int main(){
     int n;
     printf("Nhap n: ");
     scanf("%d",&n);
     printf("F(%d) = %d",n,Fibo(n));
     return 0;
}

#include

using namespacestd;

constintbase=1000000000;

constintbase_digits=9;

structbigint

{

    vector<int>a;

    intsign;

    bigint():sign(1)

    {

    }

    bigint(longlongv)

    {

        *this=v;

    }

    bigint(const string&s)

    {

        read(s);

    }

    voidoperator=(constbigint&v)

    {

        sign = v.sign;

        a=v.a;

    }

    voidoperator=(longlongv)

    {

        sign=1;

        if(v<0)

            sign= -1,v=-v;

        for(;v>0;v=v/base)

            a.push_back(v %base);

    }

    bigint operator+(constbigint&v) const

    {

        if (sign == v.sign)

        {

            bigint res = v;

            for(inti=0,carry=0;i< (int)max(a.size(),v.a.size())||carry;++i)

            {

                if(i==(int)res.a.size())

                    res.a.push_back(0);

                res.a[i]+=carry+(i<(int)a.size()? a[i]:0);

                carry=res.a[i]>=base;

                if (carry)

                    res.a[i]-=base;

            }

            return res;

        }

        return*this-(-v);

    }

    bigint operator-(constbigint&v) const

    {

        if (sign == v.sign)

        {

            if (abs() >= v.abs())

            {

                bigint res = *this;

                for(inti=0,carry=0; i<(int)v.a.size()||carry;++i)

                {

                    res.a[i] -=carry+(i<(int)v.a.size()?v.a[i]:0);

                    carry =res.a[i]<0;

                    if(carry)

                        res.a[i] +=base;

                }

                res.trim();

                return res;

            }

            return-(v-*this);

        }

        return *this+(-v);

    }

    voidoperator*=(intv)

    {

        if (v<0)

            sign=-sign,v=-v;

        for(int i=0,carry=0;i<(int)a.size()||carry;++i)

        {

            if(i==(int)a.size())

                a.push_back(0);

            longlongcur=a[i]*(longlong)v+carry;

            carry =(int)(cur/base);

            a[i]=(int)(cur%base);

            //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));

        }

        trim();

    }

    bigint operator*(intv)const

    {

        bigint res=*this;

        res *=v;

        return res;

    }

    friend pair<bigint,bigint>divmod(constbigint&a1, const bigint &b1)

    {

        int norm = base / (b1.a.back() + 1);

        biginta=a1.abs()*norm;

        bigintb= b1.abs()*norm;

        bigintq,r;

        q.a.resize(a.a.size());

        for(inti=a.a.size()-1;i>=0;i--)

        {

            r *=base;

            r+=a.a[i];

            int s1=r.a.size()<=b.a.size()?0: r.a[b.a.size()];

            ints2=r.a.size()<= b.a.size()-1?0:r.a[b.a.size()-1];

            int d=((longlong)base *s1+s2)/b.a.back();

            r -=b *d;

            while(r<0)

                r+=b, --d;

            q.a[i]=d;

        }

        q.sign= a1.sign *b1.sign;

        r.sign=a1.sign;

        q.trim();

        r.trim();

        returnmake_pair(q,r/norm);

    }

    bigint operator/(constbigint&v) const

    {

        return divmod(*this, v).first;

    }

    bigint operator%(constbigint&v) const

    {

        return divmod(*this, v).second;

    }

    voidoperator/=(intv)

    {

        if(v< 0)

            sign=-sign,v=-v;

        for(inti= (int)a.size()-1,rem=0;i>=0;--i)

        {

            long longcur=a[i]+rem *(longlong)base;

            a[i]= (int)(cur/v);

            rem=(int)(cur%v);

        }

        trim();

    }

    bigint operator/(intv)const

    {

        bigint res=*this;

        res/=v;

        returnres;

    }

    int operator%(intv)const

    {

        if(v<0)

            v =-v;

        intm=0;

        for(inti=a.size()- 1;i>=0;--i)

            m=(a[i]+m *(long long)base)%v;

        returnm *sign;

    }

    voidoperator+=(const bigint&v)

    {

        *this = *this + v;

    }

    voidoperator-=(constbigint&v)

    {

        *this = *this - v;

    }

    voidoperator*=(constbigint&v)

    {

        *this = *this * v;

    }

    void operator/=(constbigint&v)

    {

        *this = *this / v;

    }

    booloperator<(constbigint &v) const

    {

        if (sign != v.sign)

            return sign < v.sign;

        if(a.size()!= v.a.size())

            returna.size()*sign< v.a.size()*v.sign;

        for(inti=a.size()-1; i>=0;i--)

            if(a[i]!=v.a[i])

                return a[i]*sign<v.a[i]*sign;

        returnfalse;

    }

    bool operator>(constbigint&v) const

    {

        return v < *this;

    }

    booloperator<=(const bigint&v) const

    {

        return !(v < *this);

    }

    booloperator>=(constbigint&v) const

    {

        return !(*this < v);

    }

    booloperator==(constbigint&v) const

    {

        return !(*this < v) && !(v < *this);

    }

    booloperator!=(constbigint&v) const

    {

        return *this < v || v < *this;

    }

    void trim()

    {

        while(!a.empty()&& !a.back())

            a.pop_back();

        if (a.empty())

            sign=1;

    }

    boolisZero()const

    {

        returna.empty()||(a.size()==1&& !a[0]);

    }

    bigint operator-()const

    {

        bigint res=*this;

        res.sign=-sign;

        return res;

    }

    bigint abs()const

    {

        bigint res=*this;

        res.sign *=res.sign;

        returnres;

    }

    longlonglongValue()const

    {

        longlongres=0;

        for(inti=a.size()-1; i>=0;i--)

            res=res *base+a[i];

        return res *sign;

    }

    friend bigint gcd(constbigint&a, const bigint &b)

    {

        return b.isZero() ? a : gcd(b, a % b);

    }

    friend bigint lcm(constbigint&a, const bigint &b)

    {

        return a / gcd(a, b) * b;

    }

    void read(conststring&s)

    {

        sign = 1;

        a.clear();

        int pos=0;

        while(pos<(int)s.size()&& (s[pos] == '-' || s[pos] == '+'))

        {

            if (s[pos] == '-')

                sign = -sign;

            ++pos;

        }

        for (inti=s.size()-1;i>=pos;i-=base_digits)

        {

            intx=0;

            for(intj=max(pos,i- base_digits+1);j<=i;j++)

                x=x *10+ s[j]-'0';

            a.push_back(x);

        }

        trim();

    }

    friend istream&operator>>(istream &stream, bigint &v)

    {

        string s;

        stream>> s;

        v.read(s);

        returnstream;

    }

    friend ostream &operator<<(ostream &stream, const bigint &v)

    {

        if (v.sign == -1)

            stream << '-';

        stream<< (v.a.empty()?0:v.a.back());

        for(int i=(int)v.a.size()-2;i>=0;--i)

            stream <<setw(base_digits)<<setfill('0')<<v.a[i];

        return stream;

    }

    staticvector<int>convert_base(constvector<int>&a, int old_digits, int new_digits)

    {

        vector p(max(old_digits, new_digits) + 1);

        p[0]=1;

        for(inti= 1;i<(int)p.size();i++)

            p[i]= p[i-1]*10;

        vector<int>res;

        longlongcur =0;

        intcur_digits=0;

        for(inti=0;i< (int)a.size();i++)

        {

            cur+=a[i]* p[cur_digits];

            cur_digits+=old_digits;

            while(cur_digits>= new_digits)

            {

                res.push_back(int(cur% p[new_digits]));

                cur/=p[new_digits];

                cur_digits -=new_digits;

            }

        }

        res.push_back((int)cur);

        while (!res.empty()&& !res.back())

            res.pop_back();

        returnres;

    }

    typedef vector<longlong>vll;

    staticvll karatsubaMultiply(constvll&a, const vll &b)

    {

        int n = a.size();

        vll res(n+n);

        if(n<=32)

        {

            for (inti=0;i<n;i++)

                for(intj= 0;j<n;j++)

                    res[i+j]+= a[i]*b[j];

            returnres;

        }

        int k=n>>1;

        vll a1(a.begin(),a.begin()+ k);

        vll a2(a.begin()+k,a.end());

        vll b1(b.begin(),b.begin()+k);

        vll b2(b.begin()+ k,b.end());

        vll a1b1=karatsubaMultiply(a1,b1);

        vll a2b2=karatsubaMultiply(a2,b2);

        for(inti=0;i<k; i++)

            a2[i]+=a1[i];

        for(inti=0; i<k;i++)

            b2[i]+=b1[i];

        vllr =karatsubaMultiply(a2,b2);

        for(inti=0;i< (int)a1b1.size();i++)

            r[i]-=a1b1[i];

        for (inti=0;i<(int)a2b2.size();i++)

            r[i] -=a2b2[i];

        for(inti=0;i<(int)r.size(); i++)

            res[i+k]+=r[i];

        for(inti= 0;i<(int)a1b1.size();i++)

            res[i]+= a1b1[i];

        for(inti=0;i<(int)a2b2.size(); i++)

            res[i+n]+=a2b2[i];

        returnres;

    }

    bigint operator*(constbigint&v) const

    {

        vector a6 = convert_base(this->a, base_digits, 6);

        vector<int> b6=convert_base(v.a,base_digits,6);

        vlla(a6.begin(), a6.end());

        vllb(b6.begin(),b6.end());

        while (a.size()<b.size())

            a.push_back(0);

        while (b.size()<a.size())

            b.push_back(0);

        while (a.size()& (a.size() - 1))

            a.push_back(0), b.push_back(0);

        vllc=karatsubaMultiply(a, b);

        bigint res;

        res.sign=sign *v.sign;

        for (inti=0,carry=0;i<(int)c.size();i++)

        {

            longlongcur=c[i]+carry;

            res.a.push_back((int)(cur %1000000));

            carry=(int)(cur/1000000);

        }

        res.a =convert_base(res.a,6,base_digits);

        res.trim();

        return res;

    }

};

intmain()

{

    bigint first,second,temp;

    first= 1;

    second=1;

    inti=3;

    cout<<1<<" "<<first<<"\n";

    cout<<2<<" "<<second<< "\n";

    while(i<1000)

    {

        i++;

        temp= first+second;

        cout<<i<<" "<<temp<<"\n";

        first =second;

        second=temp;

    }

}