蜜蜂路线（强化版）题解

常规
1

题目描述：

一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房 M 开始爬到蜂房 N ，共有多少种不同的路径？

蜂房

输入格式：

输入 M,N 的值

输出格式：

爬行有多少种路线

样例输入1：

3 7

样例输出1：

5

约定：

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

解：

从图片找出规律，发现，路径数就是一个斐波那契数列
如， 1\Rightarrow10 ，路径数就是55（第10个斐波那契数）
2\Rightarrow10 ，路径数是34（第（10-2+1）个斐波那契数）
则，从 M\Rightarrow N ，路径数就是第（ N-M+1 ）个斐波那契数
求斐波那契数列：

cin>>n>>m;
string s1="1",s2="1",s3;
p[1]=s1;
p[2]=s2;
for(int i=3;i<=1000;i++)
{
	s3=add(s1,s2);
	p[i]=s3;
	s1=s2;
	s2=s3;
}

高精度加法：

string add(string sa,string sb)
{
	string ans="";
	int a[1010]={0},b[1010]={0},c[1010]={0};
	int la=sa.size(),lb=sb.size();
	int lc=max(la,lb);
	for(int i=0;i<la;i++)a[i]=sa[la-1-i]-'0';
	for(int i=0;i<lb;i++)b[i]=sb[lb-1-i]-'0';
	for(int i=0;i<lc;i++)
	{
		c[i]+=(a[i]+b[i]);
		c[i+1]+=c[i]/10;
		c[i]%=10;
	}
	if(c[lc])lc++;
	for(int i=lc-1;i>=0;i--)ans+=char(c[i]+48);
	return ans;
}

给个赞吧

9 个赞
2

这道题有人问吗

7 个赞
3

没人问也没事

6 个赞
4

#include
using namespace std;
int a[400]= {1,1},b[400]= {1,1},c[400]= {1,1};//定义数组
void mf(int a, int b, int c) {//定义函数（高精度加法）
int a1 = a[0], b1 = b[0];//定义变量
int len = max(a1, b1) + 1;//数组的数位
for (int i = 1; i <= len; i++) {
c[i]=a[i]+b[i];
}
for (int i = 1; i < len; i++) {
if (c[i] > 9) {
c[i + 1] = c[i + 1] + 1;
c[i] = c[i] - 10;
}
}
if (len > 1 & c[len] == 0) len–;
c[0] = len;//结果赋值
}
int main() {
int m, n;
cin >> m >> n;
if (m > n) {//因为“只能从标号小的蜂房爬到标号大的相邻蜂房”，所以m>n无解
cout << 0;
return 0;
}
int t = n - m + 1;//“n-m>=0”!!!
for (int i = 3; i <= t; ++i) {
mf(a,b,c);//函数计算
for (int i = 0; i <= b[0]; i++) {
a[i] = b[i];//把b赋值到a中
}
for (int i = 0; i <= c[0]; i++) {
b[i] = c[i];//把c赋值到b中
}
}
for (int i = c[0]; i > 0; i–) cout << c[i];//输出
return 0;
}
AC代码

8 个赞
5

@康雨齐 ，注意代码要格式化：
image

5 个赞
6

我第一次知道有这种功能

5 个赞
7

me too

5 个赞
8

@林品逸 字符串能return？
for(int i=lc-1;i>=0;i–)ans+=char(c[i]+48);
变量lc改成len更好
char(c[i]+48)是什么东西？？？？？

1 个赞
9

就是把c[i]+48的值变为字符呀，ASCLL学过没？

1 个赞