HDU的基础递推训练,我感觉做做还是蛮不错的, 况且对于思维的锻炼是一个不错的机会,,,
一只小蜜蜂...Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Problem Description
有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房,不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中,蜂房的结构如下所示。
Input
输入数据的第一行是一个整数N,表示测试实例的个数,然后是N 行数据,每行包含两个整数a和b(0<a<b<50)。
Output
对于每个测试实例,请输出蜜蜂从蜂房a爬到蜂房b的可能路线数,每个实例的输出占一行。
Sample Input
Sample Output
Author
lcy
Source
|
题目思路:
一看就是一道有关递推的问题,但是递推的式子必须要能很快的的找到,否则就是无稽之谈,容易发现,上排为奇数,下排为偶数,那么奇数和偶数交错排列,
如果数字之间相差1或者2的话,只用1步就能达到,如果数字值相差3或者以上时,那么我们很容易发现,如果到达终点,那么终点就会有两个相邻点,这两个相邻点
的步数记做a[n-1]+a[n-2],好了,这下子就总结出了递推的关系式!慢慢的递推吧,,打张表,然后一个一个的查询吧。。
代码:
# include<cstdio> # include<iostream> using namespace std; typedef long long LL; # define MAX 60 LL a[MAX]; void dabiao() { a[1] = 1; a[2] = 1; for ( int i = 3;i < MAX;i++ ) { a[i] = a[i-1]+a[i-2]; } } int main(void) { dabiao(); int t;cin>>t; while ( t-- ) { int n,m; cin>>n>>m; cout<<a[m-n+1]<<endl; } return 0; }