1.題目描述

nowcoder利用業(yè)余時(shí)間養(yǎng)了一窩蜜蜂，因?yàn)榭臻g比較小，蜂房只有兩排，如下圖所示：

如你所見，蜜蜂的蜂房是正六邊形，假設(shè)蜜蜂只會(huì)從左往右爬，即從1號(hào)蜂房能爬到2號(hào)和3號(hào)；從6號(hào)蜂房能爬到7號(hào)和8號(hào)……

現(xiàn)給出兩個(gè)蜂房的編號(hào)a和b，要求計(jì)算蜂房a的蜜蜂爬到蜂房b有幾條不同路線。

2.輸入描述:

1. 輸入的第一行是一個(gè)整數(shù)n
2. 接下來n行數(shù)據(jù)，每行一組測(cè)試用例
3. 每組測(cè)試用例包含兩個(gè)正整數(shù)a和b，(0 < a < b < 2^31)

3.輸出描述:

每組用例的結(jié)果單獨(dú)輸出一行。輸出數(shù)據(jù)結(jié)果范圍是 [0, 2^63)。

4.輸入例子:

3 1 2 3 6 99 100

5.輸出例子:

1 3 1

6.解題思路:

推導(dǎo)a到b共有多少種走法，且只能從左向右走；
b-a=1（1種）、b-a=2（2種）、b-a=3（3種）、b-a=4（5種）。。。。
依然是斐波那契數(shù)列的規(guī)律

7.源代碼：

#include<stdio.h> int main() {int i,n,a,b;long long num[103];num[0]=1;num[1]=1;num[2]=2;for(i=3;i<=103;i++)num[i]=num[i-1]+num[i-2];scanf("%d",&n);for(i=0;i<n;i++){ scanf("%d %d",&a,&b);printf("%lld\n",num[b-a]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的蜜蜂寻路(PAT)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。