P2437 蜜蜂路线---一只小蜜蜂啊,飞入花丛中啊......

发布时间:2024年01月20日

# 蜜蜂路线

## 题目背景

## 题目描述

一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你:蜜蜂从蜂房 $m$ 开始爬到蜂房 $n$,$m<n$,有多少种爬行路线?(备注:题面有误,右上角应为 $n-1$)

![](https://cdn.luogu.com.cn/upload/pic/1575.png)

## 输入格式

输入 $m,n$ 的值

## 输出格式

爬行有多少种路线

## 样例 #1

### 样例输入 #1

```
1 14
```

### 样例输出 #1

```
377
```

## 提示

对于100%的数据,$1 \le M,N\le 1000$

? ? ? ?不知道各位小伙伴看到这题时,会怎么操作呢?其实仔细一想就是斐波那契数列高精度加法的结合应用,如果这两个知识点不会的小伙伴,那可以看一下本蒟蒻前面的相关文章。

? ?我们现在开始讲述本题的重点,就是如何把斐波那契数列与高精度算法结合起来呢?毫无疑问的是要用到数组。我们运用数组就可以把二者有机结合起来了。各位小伙伴可以尝试一下,看能不能写出题解。

? ? ?当我也是按照这种思维思考时,便遇到了一个问题就是如何计算数组的实际长度,经过我七七四十九分钟的思考,终于想到怎么计算了,一般我们计算一个数组的长度会从头开始,但这样做这题显然不行,那么我们就反着来,从最后开始,只要其元素项为0,那就减一就OK了,这样这道题就算解出来了,直接代码吧.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int Max(int a,int b) {
	if (a > b){
		return a;
	}
	else return b;
}
int main() {
	int n, m, arr[1005]={1}, brr[1005] = {1}, a, b, c;
	scanf("%d%d", &m, &n);
	n = n-m;
	m = 1;
	if (n == 1) {
		printf("1");
	}
	else {
		
		while (m < n) {
			int crr[1005] ={0};
			a = 1004;
			b = 1004;
				while (arr[a] == 0) {
					a--;
			}
			while (brr[b] == 0) {
				b--;
			}
			c = Max(a,b) + 1;
			for (int i = 0;i <= c;i++) {
				crr[i]+= arr[i] + brr[i];
				crr[i + 1] = crr[i] / 10;
				crr[i] = crr[i] % 10;
			}
			for (int i = 0;i <= a;i++){
				brr[i] = arr[i];
			}
			for (int i = 0;i <=c;i++){
				arr[i] = crr[i];
			}
			m++;
		}
	}

	for (int i = c - 1;i >= 0;i--) {
		printf("%d", arr[i]);
	}

	return 0;
}

不知道各位看到这题时,各位是这样思考的嘛,应该还有另外的思想,动动脑筋,加油·!

文章来源:https://blog.csdn.net/d__king/article/details/135721965
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。