HDU2044一只小蜜蜂...（递归）

我就是我 2022-05-25 02:41 176阅读 0赞

# 一只小蜜蜂... #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 90448 Accepted Submission(s): 32139**

Problem Description

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。  
其中，蜂房的结构如下所示。  
![C40-1001-1.jpg][]

Input

输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0<a<b<50)。

Output

对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占一行。

Sample Input

2 1 2 3 6

Sample Output

1 3

**假设起点是 1 的时候  
  
  
f(n-1) := 从 1 到 n 的可能线路数  
  
  
从 1 到 2 有 1 中方法 f(1)=1  
从 1 到 3 有 1 中方法 f(2)=1  
从 1 到 4 有 1 中方法 f(3)=2  
  
  
从 1 到 4 的方法数等于从 2 到 4 的方法数 + 从 3 到 4 的方法数  
因为密封想要到达 4 肯定是得经过 2 和 3  
所以我们把 2 和 3 作为起点来考虑就简单多了  
  
  
所以  
从 1 到 4 有 1 中方法 f(3)=2 = f(2) = f(1)  
从 1 到 5 有 1 中方法 f(4)=3 = f(3) + f(2)  
从 1 到 6 有 1 中方法 f(5)=5 = f(4) + f(3)**

**所以这其实就是一个简单地斐波那契数列的，结果就是 f（b-a）**

**注意要用long long ,避免数据溢出**

AC代码如下：

#include<cstdio>
    using namespace std;
    typedef long long ll;
    ll a[60];
    int main()
    {
    	a[0]=1;a[1]=1;
    	for(int i=2;i<60;i++)	a[i]=a[i-1]+a[i-2];
    	int t,m,n;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d %d",&n,&m);
    		printf("%lld\n",a[m-n]);
    	}
    	return 0;
    }

[C40-1001-1.jpg]: /images/20220525/545c0e48d37f48e8b46dcd951c07736e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，176人围观）

还没有评论，来说两句吧...

相关阅读

相关 hduoj 一只小蜜蜂

一只小蜜蜂... Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

「爱情、让人受尽委屈。」/ 2024年02月18日 21:48/ 0 赞/ 8 阅读

相关递归逻辑小案例

递归分析递归算法就是直接或间接调用自己的算法代码如下： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shado

梦里梦外;/ 2023年01月05日 05:14/ 0 赞/ 159 阅读

相关递归小案例

递归小案例不要用console.log输出，浏览器会死的 <!DOCTYPE html> <html> <head> <meta

冷不防/ 2022年12月11日 02:19/ 0 赞/ 162 阅读

相关一只小蜜蜂... （递推） hdu 2044 c++版

一只小蜜蜂... Problem Description 有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计

浅浅的花香味﹌/ 2022年08月10日 14:48/ 0 赞/ 180 阅读

相关一只蜜蜂

一只蜜蜂在我房间大块的固定窗玻璃上扑腾，它一定很困惑，眼前这灰濛濛明晃晃的空间为什么可见而不可入。过了几分钟，我看见它落在窗台上，蹒跚地移动着，一条腿看上去还有些瘸，再这样下去

以你之姓@/ 2022年08月07日 03:56/ 0 赞/ 202 阅读

相关 hdu2044（dp训练2）

在上文中做了关于dp的介绍，和用法，那么本文再做一个加深训练。在网上找到了杭电的2044道题，一只小蜜蜂可以用该思想解决。有一只经过训练的蜜蜂只能爬向右侧相邻

左手的ㄟ右手/ 2022年06月01日 11:46/ 0 赞/ 182 阅读

相关 HDU-2044-一只小蜜蜂...(水)

一只小蜜蜂... Problem Description 有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到

我会带着你远行/ 2022年05月27日 09:35/ 0 赞/ 147 阅读

相关 HDU2044一只小蜜蜂...（递归）

一只小蜜蜂... Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Jav

我就是我/ 2022年05月25日 02:41/ 0 赞/ 177 阅读

相关一只小蜜蜂...

> Description > > 有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。 > 其中，蜂房的结构如下所示

川长思鸟来/ 2022年04月17日 00:26/ 0 赞/ 219 阅读

相关递归（一）：递归的基本思想

递归是算法设计中的一种基本而重要的算法。递归方法通过函数调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。递归算法的定义：如果一个对象的描述中包含它本身

r囧r小猫/ 2021年11月24日 00:24/ 0 赞/ 540 阅读