一只小蜜蜂...
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15746 Accepted Submission(s): 5816
http://acm.hdu.edu.cn/showproblem.php?pid=2044
Problem Description
有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房,不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中,蜂房的结构如下所示。
Input
输入数据的第一行是一个整数N,表示测试实例的个数,然后是N 行数据,每行包含两个整数a和b(0<a<b<50)。
Output
对于每个测试实例,请输出蜜蜂从蜂房a爬到蜂房b的可能路线数,每个实例的输出占一行。
Sample Input
2
1 2
3 6
Sample Output
1
3
分析:
首先想到这道题是递推的应用,于是分析题目,观察到每个蜂房都和与它标号相邻的前两个标号蜂房相邻,既是x-1号和x-2号,于是猜测这是斐波拉数列的应用,根据猜测继续分析得到递推公式 NUM(a to b) = NUM(b - 1) + NUM(b-2);以a为端点,直到a停止。于是得到AC代码如下(由于数据比较大,直接用int要产生溢出所以改用__int64):
#include <stdio.h>
#include <string.h>
__int64 beecell[50];
__int64 beeStepCalculate(int level)
{
if(level == 0 || level == 1)
{
return 1;
}
if(beecell[level] != 0)
{
return beecell[level];
}
return beecell[level] = beeStepCalculate(level - 1) + beeStepCalculate(level - 2);
}
int main()
{
int n,a,b,level;
__int64 sum;
while(scanf("%d",&n)!=EOF)
{
while(n--)
{
scanf("%d%d",&a,&b);
memset(beecell,0,50);
level = b - a;
sum = beeStepCalculate(level);
printf("%I64d\n",sum);
}
}
return 0;
}
- 大小: 9.6 KB
分享到:
相关推荐
HDU的一题........HDU DP动态规
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU1059的代码
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
标题前言hdu2023求平均成绩hdu2027统计元音hud2044一只小蜜蜂…hud2029Palindromes _easy versionhud2043密码hud2040亲和数hud2021发工资咯hud2032杨辉三角 前言 今天bigsai陪伴我刷题,我很高兴在他的帮助下过了8道...
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
自己做的HDU ACM已经AC的题目
hdu 1166线段树代码
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
HDU最全ac代码
hdu动态规划算法集锦
hdu题目分类
Hdu 1237 解题代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU图论题目分类