首页 > 试题广场 >

蜜蜂寻路

[编程题]蜜蜂寻路
  • 热度指数：4298 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
nowcoder利用业余时间养了一窝蜜蜂，因为空间比较小，蜂房只有两排，如下图所示：

如你所见，蜜蜂的蜂房是正六边形，假设蜜蜂只会从左往右爬，即从1号蜂房能爬到2号和3号；从6号蜂房能爬到7号和8号……
现给出两个蜂房的编号a和b，要求计算蜂房a的蜜蜂爬到蜂房b有几条不同路线。

输入描述:
1. 输入的第一行是一个整数n
2. 接下来n行数据，每行一组测试用例
3. 每组测试用例包含两个正整数a和b，(0 < a < b < 2^31)


输出描述:
每组用例的结果单独输出一行。输出数据结果范围是 [0, 2^63)。
示例1

输入

3<br/>1 2<br/>3 6<br/>99 100

输出

1<br/>3<br/>1
算法知识视频讲解
添加回答
啥头像 啥
因为 “输出数据结果范围是 [0, 2^63) ” ，而fibonacci数列的第103项就会超过2^63，所以只要算fibonacci数列的前102项就可以了

代码如下： 
#include <iostream>
#include <stdio.h>

using namespace std;

long long diff[103] = {1, 1, 2};

int main()
{
    for(int i=3; i<103; i++) {
        diff[i] = diff[i-1] + diff[i-2];
    }
    unsigned int n; unsigned int a, b, d;
    scanf("%d", &n);
    while(n--) {
        scanf("%d %d", &a, &b); d = b - a;
        printf("%lld\n", diff[d]);
    }
    return 0;
}


发表于 2015-12-31 12:52:45 回复(0)
C/C++
hanjiangxue头像 hanjiangxue

详细题解：

https://blog.csdn.net/qq_33375598/article/details/104609103

2 解析

设n为b与a的差值，F(n)为从a到b的方案。
由题目的图知,下面开始递推讨论
当n为3时：
在这里插入图片描述
当n为4时：
在这里插入图片描述
依次递推，得到递推公式：F(n) = F(n-1) + F(n-2).
也就是斐波那契数列。
由动态规划的知识：
递推式子：
递推边界：
从递推边界出发，依次递推便可得到整个递推式。

3 参考代码

#include <cstdio>

typedef long long ll;
const int MAXN = 100010;
ll f[MAXN] = {1,1,2};

int main(int argc, char const *argv[]){
    int n, a, b;
    for (int i = 3; i < MAXN; ++i) {
        f[i] = f[i -1] + f[i -2];//递推式
    }
    scanf("%d", &n);
    while(n--){
        scanf("%d%d", &a, &b);
        printf("%lld\n", f[b - a]);
    }
    return 0;
}
发表于 2020-03-02 12:49:12 回复(0)
C/C++
不徐不疾头像 不徐不疾
可以看成走台阶的变形版本。
横着走：1->3->5->7->9；2->4->6->8->10；可以看成每次上两阶台阶；
斜向走：1 2；3 4 ；4 5；可以看成每次上一阶台阶；
那么，比如从5->8，就可以看成走8-5=3台阶的情况。即fib（3）=fib（1）+fib（2），即从5->6的走法加上5->7的走法。
打表可以发现：

92的时候，爆long long了
于是我们根据题目说的数据输出范围，打前95个斐波那契数列就可以了。
AC代码： 
#include<iostream>
#define ll long long
using namespace std;

const int maxn=100;
ll fib[maxn];

int main()
{      fib[1]=1;    fib[2]=2;  for(int i=3; i<=95; i++)  {  fib[i]=fib[i-1]+fib[i-2];  }  int T;  int a,b;  cin>>T;  while(T--)  {    scanf("%d %d",&a,&b);  printf("%lld\n",fib[b-a]);  }  return 0;
}

编辑于 2019-05-04 19:58:14 回复(0)
C/C++
Caffeine头像 Caffeine 
思路就是可以前进一步或者两步和小孩跳楼梯一模一样。
#include <iostream>
#include <vector>
using namespace std;
/*
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
*/
int main()
{
    vector<long long> v(100);
    long long temp;
    v[0] = 0;// D
    v[1] = 1;// D A
    v[2] = 2;// D A B 

    for (int i = 3; i < 100; i++)
    {
        v[i] = v[i - 1] + v[i - 2];
    }
    int n;
    int a, b, c;
    while (cin >> n)
    {
        for (int i = 0; i < n; i++)
        {
            cin >> a >> b;
            c = b - a;
            cout << v[c] << endl;
        }    
    }
}

发表于 2018-08-11 21:45:42 回复(0)
xbreak头像 xbreak 
import java.util.Scanner;


public class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			
			int t = scanner.nextInt();
			for(int k = 0; k<t; k++){
				int x = scanner.nextInt();
				int y = scanner.nextInt();
				System.out.println(getRes(x, y));
				
			}
		}
	}

	private static long getRes(int x, int y) {
		
		int N = y-x+1;
		if(N<=2)
			return 1;
		long [] dp = new long[N+1];
		dp[1] = 1;
		dp[2] = 1;
		for(int i = 3; i<=N; i++)
			dp[i] = (dp[i-2]+dp[i-1]);
		return dp[N];
	}
	
	
}
java动规
发表于 2017-09-12 19:59:41 回复(0)
C/C++
cantin头像 cantin 
#include <stdio.h>
int main()
{
    long long a,b,fibo[1000];
    int i,n;
    scanf("%d",&n);
    fibo[1]=1;fibo[2]=1;
    for(i=3;i<=999;i++)
    {
        fibo[i]=fibo[i-1]+fibo[i-2];
    }
    for(i=1;i<=n;i++)
    {
        scanf("%lld%lld",&a,&b);
        b=b-(a-1);
        printf("%lld\n",fibo[b]);
    }
    return 0;
}

发表于 2020-04-17 18:11:31 回复(0)
hestyle头像 hestyle

解题思路：

由于排列规则可知，以及只能往左、右走，可知只有n-2、n - 1到达n。
那不就得出了f(n) = f(n - 1) + f(n - 2)么，这不就是斐波拉契尔数列问题么。。。

路线数 始、终差
1->1 1 0
1->2 1 1
1->3 2 2
1->4 3 3
1->5 5 4
1->6 8 5
1、1、2、3、5、8不就是一个斐波拉契尔数列么

代码实现：\color{blue}代码实现：代码实现：

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    //建立一张表，用于记录f(n)各项值，注意数据溢出，使用long long型
    //由于斐波拉契尔数列第103项已经超过了2^63，并且题目说明结果不会超过2^63，因此计算1-102
    long long fTable[103] = {1, 1};
    for (int i = 2; i < 103; ++i) {
        fTable[i] = fTable[i - 1] + fTable[i - 2];
    }
    int count = 0;
    //scanf返回值为正确输入数据的变量个数，当一个变量都没有成功获取数据时，此时返回-1
    while (scanf("%d", &count) != - 1) {
        for (int i = 0; i < count; ++i) {
            int a = 0, b = 0;
            scanf("%d %d", &a, &b);
            printf("%lld\n", fTable[b - a]);
        }
    }
    return 0;
}

————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104629461

发表于 2020-03-03 12:39:02 回复(0)
C/C++
JediMaster头像 JediMaster 
#include<iostream>
#include<vector>
using namespace std;
//典型fb数列
int main() {
    long long  a,b,n;
    vector<long long> dp(120,0);
    dp[0]=1;
    dp[1]=1;
    for (int i = 2; i < 120; i++) {
        dp[i]=dp[i-1]+dp[i-2];
    }
    while (cin >>n) {
        for(int i=0;i<n;i++){
            cin>>a>>b;
            cout << dp[b-a] << endl;
        }
    }
}

编辑于 2020-02-25 19:10:44 回复(0)
勇敢牛牛额头像 勇敢牛牛额
搞个数组存储太不容易了吧
发表于 2019-12-07 22:50:12 回复(0)
SupritYoung头像 SupritYoung
详细题解
发表于 2018-11-12 17:51:45 回复(0)
ShouldBeOk头像 ShouldBeOk
/*
 * =====================================================================================
 *
 *       Filename:  09蜜蜂寻路.cpp
 *
 *        Version:  1.0
 *        Created:  2018/09/24 11:52:06
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Covfefe
 *   Organization:    Fs-studio
 *   
 *             idea:  b - a - 1 为斐波那契数列第n项
 *
 * =====================================================================================
 */
//************************************
// Method:    main
// FullName:  main
// Access:    public 
// Returns:   int
// Qualifier:
//************************************
#include <stdio.h>
#include <iostream>
using namespace std;
#define FOR(i,n) for(i = 2; i < n; i++)
long long F[90];
int main()
{
    int n, a, b, i;
    F[0] = 1;
    F[1] = 2;
    FOR(i, 100)
        F[i] = F[i - 1] + F[i - 2];
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> a >> b;
        cout << F[b - a - 1] << endl;
    }
    return 0;
}
发表于 2018-09-24 12:14:23 回复(0)
whofhaouwef头像 whofhaouwef
不懂为什么错？
#include<iostream>
#include<stdio.h>
using namespace std;

int main() {
    int n;
    scanf("%d",&n);
    long long Febi[103];
    Febi[0]=0;
    Febi[1]=1;
    Febi[2]=2;
    for(int i=3;i<103;i++){
        Febi[i]=Febi[i-1]+Febi[i-2];
    }
    int a,b;
    for(int i=0;i<n;i++){
        scanf("%d %d",&a,&b);
        d=b-a;
        printf("%d",Febi[d]);
    }
    return 0;
}
发表于 2018-09-02 20:54:18 回复(0)
CodeTiger头像 CodeTiger 
#include<stdio.h>
long fib(int n)
{
    long pre = 1;
    long next = 0;
    long result = 1;
    while(n > 1)
    {
        n--;
        next = pre;
        pre = result;
        result = pre + next;
    }
    return result;
}
int main(void)
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        int a;
        int b;
        scanf("%d%d", &a, &b);
        printf("%ld\n", fib(b - a));
    }
}

发表于 2018-04-01 15:54:46 回复(0)
熊朝春头像 熊朝春 

	//搞错了没有，全是斐波拉契





	#include <stdio.h>





	void DataInit(long long *a);





	int main()





	{





	    int N, i;





	    long long a, b;





	    long long A[100001] = {0, 1, 2};





	    DataInit(A);





	    scanf("%d", &N);





	    for(i=0;i<N;i++)





	    {





	        scanf("%lld %lld", &a, &b);





	        printf("%lld\n", A[b-a]);





	    }





	     





	    return 0;





	}





	void DataInit(long long *a)





	{





	    int i;





	    for(i=3;i<100001;i++)





	    {





	        a[i] = a[i-1] + a[i-2];





	    }





	}

发表于 2017-11-26 23:29:39 回复(0)
南邮陈丹伟头像 南邮陈丹伟
找工作要用JAVA，优势大，做题目，JAVA速度明显慢很多，原来想递归的，超时了
importjava.util.Scanner;
 
publicclassMain {
     
    publicstaticvoidmain(String[] args){    
        //long a[][] = {{2,1},{3,6},{3,3},{4,5}};
        long[] a = newlong[104];
        a[0]=0;
        a[1]=1;
        for(inti=2;i<104;i++)
            a[i] = a[i-1]+a[i-2];
//      for(int i=0;i<10;i++)
//          System.out.println(a[i]);
         
        Scanner scan =  newScanner(System.in);
        intn = scan.nextInt();
        int[] tmp = newint[n];
        for(inti=0;i<n;i++)
        {
            inta1 = scan.nextInt();
            intb1 = scan.nextInt();
            tmp[i] = b1 - a1;
        } 
         
        for(inti=0;i<n;i++)
            System.out.println(a[tmp[i]+1]);
         
        scan.close();
         
    }
 
     
      
}

发表于 2017-02-07 10:20:54 回复(0)
C/C++
MarvelSuperMiracle头像 MarvelSuperMiracle

好像没人用动态存储。。 

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int n;
    while (~scanf("%d", &n)) {
        short *s = (short*)calloc(n+1, sizeof(short));
        int maxs=*s;
        for (int t = 1; t <= n; t++) {
            int a, b;
            scanf("%d%d", &a, &b);
            *(s + t) = b - a;
            if (*(s + t) > maxs) maxs = *(s + t);
        }
        long long *fib = (long long*)calloc(maxs+1, sizeof(long long));
        *(fib+1) = 1; *(fib + 2) = 2;
        for (int i = 3; i <= maxs; i++) fib[i] = fib[i - 1] + fib[i - 2];
        for (int i = 1; i <= n; i++) printf("%lld\n", fib[s[i]]);
        free(s);free(fib);s=NULL;fib=NULL;
    }
    return 0;
}

编辑于 2017-02-02 21:59:24 回复(0)
i逆天耗子丶头像 i逆天耗子丶 
#include<cstdio>
using namespace std;
long ans[103];
int n,a,b;
int main(){
	ans[1]=1;
	ans[2]=2;
	for(int i=3 ;i<103 ;i++){
		ans[i] = ans[i-1] + ans[i-2];
	}
	while(scanf("%d",&n)!=EOF){
		while(n--){
			scanf("%d%d",&a,&b);
			int x = b-a;
			printf("%ld\n",ans[x]);
		}	
	}
	return 0;
}
发表于 2016-07-09 21:36:19 回复(0)
ahac头像 ahac 
#include <stdio.h>

int main(){
    unsigned int n,from,to,i;
    long long sum[103]={0,1,2};///这里申明sum[0]=0只是占位用的
    for(i=3;i<103;i++){
        sum[i]=sum[i-1]+sum[i-2];
    }
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d %d",&from,&to);
        printf("%lld\n",sum[to-from]);
    }
    return 0;
}

发表于 2016-01-15 16:56:35 回复(0)
夏雨天头像 夏雨天

#include <iostream>

using namespace std;

int main()
{
long long array[100001] = { 0 };
int n = 0, a = 0, b = 0;


array[1] = 1;
array[2] = 2;


for (int i = 3; i < 100001;i++)
{
array[i] = array[i - 1] + array[i - 2];
}


while (scanf("%d",&n)!=EOF)
{
for (int i = 0; i < n;i++)
{
cin >> a >> b;
if (b>=a)
{
cout << array[b - a] << endl;
}
else
{
cout << array[a - b] << endl;
}
}
}

return 0;
}
发表于 2015-10-13 17:26:33 回复(0)
杰哥头像 杰哥

#include <stdio.h>

#include <iostream>

using namespace std ;

long fib[ 2000 ] = { 0 };

int main() {

    fib [ 1 ] = 1 ;

    fib [ 2 ] = 2 ;

    for ( int i = 3 ; i < 2000 ; i++) {

        fib [i] = fib [i- 1 ] + fib [i- 2 ];

    }

    int n,a,b;

    scanf ( "%d" , &n);

    while (n--) {

        scanf ( "%d%d" , &a,&b);

        printf ( "%ld\n" , fib [b-a]);

    }

    return 0 ;

}

发表于 2015-07-17 23:54:58 回复(0)
提交观点

问题信息

难度：
21条回答 7844浏览

热门推荐

通过挑战的用户

相关试题

蜜蜂寻路

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号