蜜蜂路线_高精

题目

一只蜜蜂在数字蜂房上爬动，已知它只能从标号小的蜂房爬到标号大的相邻蜂房，现在请编程计算：蜜蜂从蜂房m开始爬到蜂房n，1<=m<n<=1000，有多少种爬行路线？

思路

读懂题目后，可能会有点蒙。但不急，先找规律。**到一个点的路线个数等于能到这个点的两点路线个数相加，**于是就有了0 1 3 8 21…
1 2 5 13 34…
摊开就是 0 1 1 2 3 5 8 13 21 34好家伙，就是肥不拉 ，呸，斐波那契数列！
先别激动，看数据，n<=1000，第一千个数是什么呢？不用问，肯定大到没没朋友，直接上高精，高精加题。

代码

#include<bits/stdc++.h>
using namespace std;
int m,n;
string p[2021];
string jia(string a,string b)
{
    int x[500],y[500],z[500];
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    memset(z,0,sizeof(z));
    for(int i=0;i<a.size();i++)
    {
        x[a.size()-i]=int(a[i])-48;
    }
    for(int i=0;i<b.size();i++)
    {
        y[b.size()-i]=int(b[i])-48;
    }
   long long c=max(a.size(),b.size());
    for(int i=1;i<=c;i++)
    {
        z[i]+=x[i]+y[i];
        if(z[i]>=10)
        {
            z[i+1]++;
            z[i]%=10;
        }
    }
    if(z[c+1]!=0)
    {
        c++;
    }
    string giao;
    giao="";
    for(int i=c;i>=1;i--)
    {
        giao+=char(z[i]+48);
    }
    return giao;
}
int main()
{
    cin>>m>>n;
    p[1]="0",p[2]="1";
    for(int i=3;i<=n-m+2;i++)
    {
        p[i]=jia(p[i-1],p[i-2]);
    }
    cout<<p[n-m+2];
    return 0;
}

总结

其实就是一道高精加的题目，读懂题目，要有一定数学基础。主要弄明白高精度为什么要倒叙输入输出，掌握高精进位推位。本蒟蒻第一次写博客，不喜勿喷。