Time Limit: 10 second

Memory Limit: 2 MB

问题描述

一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,

现在问你：蜜蜂从蜂房M开始爬到蜂房N，有多少种爬行路线？

Input

仅一行，包含两个integer范围以内的自然数m，n 。

Output

仅一行，包含一个自然数，即爬行路线的种数。

Sample Input

1 14

Sample Output

377

【题解】

假设我们从1出发，然后设a[i]为到位置i的步骤数，那么a[2] = 1，即 直接从1走到2，a[3] = 2，即从1走到3 或者从1走到2 再走到3.

a[4] = a[2] + a[3].即走到3然后走到4，或者走到2再走到4.

以此不难得出递推式a[i] = a[i-1] + a[i-2];

然后我们可以看出 决定路线种数的不是起始和末位置，而是两个数的差，即b-a + 1;设这个数为n，则我们在求斐波那契数列的第n项。

我们只要用a,b,c三个数字递推就能得出答案。不过要用高精度，因为n可能很大。

【代码】

#include 
    
     #include 
     
      int x,y,z,n;int a[500],b[500],c[500];void input_data(){    scanf("%d %d",&x,&y);    if (x > y) //保证 x是小于y的        {            z = x;x = y;y = z;        }    n = y - x + 1; 得到n}void get_ans(){    memset(a,0,sizeof(a)); //初始化a,b,c数组 用于高精度运算    memset(b,0,sizeof(b));    memset(c,0,sizeof(c));    int la = 1,lb = 1,lc; //分别表示a,b,c表示的数字的长度    a[1] = 1;b[1] = 1;    if ( n == 1)        {            printf("1");            return;        }    if (n == 2)        {            printf("1");            return;        } //n等于1或2的情况只要特判就可以    for (int i = 3;i <=n;i++) //大于等于3则需要用迭代+高精度的方法获取答案        {            int l;            if (lb > la)                l = lb;                    else                        l = la;            int x = 0; //x用来处理进位问题            for (int j = 1;j <= l;j++)                {                    c[j] = a[j] + b[j] + x;                    x = c[j] / 10;                    c[j] = c[j] % 10;                }            while (x > 0) //要进位 可能会让数字的长度变长                {                    l++;                    c[l] += x;                    x = c[l] / 10;                    c[l] = c[l] % 10;                }            lc = l;            for (int j = 1;j <= lb;j++) //进行迭代 a = b,b =c                a[j] = b[j];            la = lb;            for (int j = 1;j <= lc;j++)                b[j] = c[j];            lb = lc;        }    for (int j = lc;j >= 1;j--)        printf("%d",c[j]);}int main(){    input_data();    get_ans();    return 0;}