洛谷 P2437 蜜蜂路线 C++ （高精度）题解

洛谷 P2437 蜜蜂路线 C++ （高精度）题解 题目背景

无

题目描述

一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房 mm 开始爬到蜂房 nn，m

输入格式

输入 m,n 的值

输出格式

爬行有多少种路线

输入输出样例

输入 #1复制

1 14

输出 #1复制

377

说明/提示

对于100%的数据 M,N≤1000

 思路简介：

如果接触多了此类题就会很快的意识到，这肯定是存在规律或者递推式的。如果再对数学敏感一些，会很容易发现从任意一点m到m+1和m+2点的方法都是只有一种。所以不难想到，从任何一点m到另一点n的方法，就等于从m点到n-1的方法+到n-2点的方法。即f[m][n]=f[m]n-1]+f[m][n-2]。

这显然就是斐波那契数列的变式，关键就是怎么将题转化为斐波那契数列的解法。

既然已经确定了递推式，我们可以通过不完全归纳法和特解法来得到答案。

先穷举一部分斐波那契数列，1、1、2、3、5、8、13...

再穷举，当m等于1时候，n依次取值，分析结果，对比和斐波那契数列特殊项对应。发现n=2、3、4、5、6、7的结果，分别对应斐波那契数列第2、3、4、5、6、7项的结果。也可以取m=2，n依次取来验证。所以显然m和n确定的斐波那契数列项数便是第n-m+1项，从而用高精度轻易AC。

高精度AC代码如下：

#include
using namespace std;
#define MAX 9999
int f[1001][MAX];
int len;
void fun(int x) {//高精度加法
	for (int i = 0; i < len; i++) {
		f[x][i] += f[x - 1][i] + f[x - 2][i];//递推式
		if (f[x][i] > 9) {
			f[x][i + 1]++;
			f[x][i] -= 10;
		}
		if (i == len - 1 && f[x][len])len++;
		}
}
int main(){
	int m, n;
	cin >> m >> n;
	f[1][0] = 1;//斐波那契数列前两项都是1
	f[2][0] = 1;
	len = 1;
	int x = n - m + 1;
	for (int i = 3; i <=x; i++) {
		fun(i);
}
	while (f[x][len - 1] == 0 && len > 1)len--;
	for (int i = len-1; i >=0; i--)
		cout << f[x][i];

	return 0;
}

当然此题也可以利用结构体模拟大整数类，利用运算符重载，快速幂，结合高精度运算等等来解决。话不多说，直接送上神犇的代码。

//本题其实就是求斐波那切数列的第n-m+1项，但由于数据过大，所以需要使用到高精度加法
#include
#include	//strlen和memset所需头文件
#include	//reverse所需头文件
#define r register int	//register关键字将变量存储在CPU寄存器中，可以提高效率
struct BigInteger{
    char str[100001];	//str数组用于存储字符串
    int num[100001],len;	//num数组为str数组转为int类型的结果，len为str的长度，也就是num的大小
    inline void output(){	//输出函数，由于是反向模拟加法的，所以也需要反向输出
        for(r i=len-1;i+1;--i)printf("%d",num[i]);
    }
    BigInteger operator+(BigInteger &k){	//开始重载了，加法竖式模拟也不需要多解释
        len=max(len,k.len);r f=0;
        for(r i=0;i^len;++i){
            num[i]+=k.num[i]+f;
            if(num[i]>9)num[i]-=10,f=1;
            else f=0;
        }
        if(f)num[len++]=1;	//这里是对进位的处理
        return *this;	//*this返回一个指向类本身的指针
    }
    BigInteger(){	//初始化，清零所有变量和数组
    	len=0;
        memset(str,0,sizeof str);
        memset(num,0,sizeof num);
    }
    BigInteger(int k){	//将BigInteger类型赋为int类型，也可当做强制转换使用
        memset(str,0,sizeof str);
        sprintf(str,"%d",k);	//sprintf与printf类似，可以当做将数值打印到字符串中，具体用法请自行度娘（笑）
        len=strlen(str);	//保存字符串长度
        std::reverse(str,str+len);	//由于需要反向模拟竖式，所以我们在这里就调用STL的reverse函数将str字符串倒过来
        for(r i=0;i^len;++i)num[i]=str[i]-48;	//将字符串转为int类型
    }
};
main(){
    BigInteger n(1),m(1);	//注意，这里必须初始化为1，否则会出错
    int a,b,c;
    scanf("%d%d",&a,&b);
    c=b-a+1;	//求出是求斐波那切数列的第几项
    for(r i=1;i^c;++i)	//这里的位运算其实优（zhi）化（shi）意（wei）义（le）不（zhuang）大（bi）
        if(i&1)n=n+m;	//这里的a^b可当做a 
总之，此题虽然在递归题单里，在数据量不大的时候显然用递归很容易。但此处显然是要利用高精的，所以还是那句话，刷题只要能把题AC和学习到相应的知识就行，而并不在于秀自己的编程技巧。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5710508.html