蜜蜂路线

简介: 【问题描述】如下图所示,一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你:蜜蜂从蜂房M开始爬到蜂房N,M=m+2光盘测试数据比较大,要用高精度数解决。 1 #include 2 #include 3 #include 4 //高精度数操作函数 5 //高精度数a[]的a[0]存放位数,例如“357234567”存为int数组:“9357234567”。

【问题描述】
如下图所示,一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你:蜜蜂从蜂房M开始爬到蜂房N,M<N,有多少种爬行路线?

【输入格式】
输入M,N的值。
【输出格式】
爬行有多少种路线。
【输入样例】bee.in
1 14
【输出样例】bee.out
377

算法分析:

假设f(i)表示从m到达i的方法数目。则有:

f(m)=1,f(m+1)=1.

f(i)=f(i-1)+f(i-2),其中i>=m+2

光盘测试数据比较大,要用高精度数解决。

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include<string.h>
 4 //高精度数操作函数
 5 //高精度数a[]的a[0]存放位数,例如“357234567”存为int数组:“9357234567”。
 6 #define maxN 1005
 7 void add(int *a,int *b,int *c);//a+b -> c
 8 void mov(int *from,int *to);   //把from复制到to
 9 void printOut(int *a);            //输出高精度数a
10 
11 int main()
12 {
13     /*
14     int a[maxN]={5,5,5,5,5,5};
15     int b[maxN]={5,5,5,5,5,5};
16     int c[maxN]={0};
17     printOut(a);
18     printf(" + ");
19     printOut(b);
20     printf("=");
21     add(a,b,c);
22     printOut(c);
23     printf("\n");*/
24 
25     freopen("bee_data/BEE1.in","r",stdin);
26     freopen("bee_data/BEE1.txt","w",stdout);
27     int m,n,i,a[1005]={0},b[1005]={0},c[1005]={0};
28     scanf("%d%d",&m,&n);
29     a[0]=1;a[1]=1;
30     b[0]=1;b[1]=1;
31     c[0]=1;c[1]=1;
32     for(i=m+2;i<=n;i++)
33     {
34 
35         add(a,b,c);   // c=a+b;
36         mov(b,a);     // a=b;
37         mov(c,b);     // b=c;
38     }
39     printOut(c);
40     printf("\n");
41     return 0;
42 }
43 //高精度数操作函数
44 //高精度数a[]的a[0]存放位数,例如“357234567”存为int数组:“9357234567”。
45 void add(int *a,int *b,int *c) //a+b -> c
46 {
47     int i,j,k;
48     for(i=0;i<maxN;i++) c[i]=0;
49 
50     for(i=a[0],j=b[0],k=1;  i>=1&&j>=1;  i--,j--,k++)
51         c[k]=a[i]+b[j];
52     while(i>=1) { c[k]=a[i]; i--; k++; }
53     while(j>=1) { c[k]=b[j]; j--; k++; }
54     c[0]=k-1;
55     for(i=1;i<=c[0];i++)  //进位
56     {
57         c[i+1]+=c[i]/10;
58         c[i]=c[i]%10;
59     }
60     if(c[i]!=0) c[0]++;  //向更高位进位
61     for(i=1,j=c[0];i<j;i++,j--)
62     { k=c[i]; c[i]=c[j]; c[j]=k; }
63 }
64 void mov(int *from,int *to) //把from复制到to
65 {
66     int i;
67 
68     for(i=0;i<=from[0];i++)
69         to[i]=from[i];
70 }
71 void printOut(int *a) //输出高精度数a
72 {
73     int i;
74     for(i=1;i<=a[0];i++)
75     {
76         printf("%d",a[i]);
77     }
78 }
利用高精度数据解决

 

相关文章
|
传感器 编解码 供应链
禾赛张伟:激光雷达路线之争,已初见分晓
禾赛张伟:激光雷达路线之争,已初见分晓
134 0
禾赛张伟:激光雷达路线之争,已初见分晓
|
7月前
|
数据采集 安全 物联网
“智慧的车,聪明的路”距离市场还有多远?
随着油价连续上涨,新能源汽车再次迎来利好。在能够蚕食燃油车市场的“历史机遇”面前,新能源车却玩起了涨价。这并不是新能源“傲娇”,而是主战场已经开始悄悄转换,从堆料砸性价比,迈向了智能化升级的路。 在这一波军备竞赛中,车联网无疑是一个可操作的、能立竿见影提升产品力的、能迅速拉开与燃油车代差的选项。
|
传感器 算法 数据挖掘
【VRP问题】基于帝国企鹅优化算法求解冷链配送物流车辆调度优化研究
【VRP问题】基于帝国企鹅优化算法求解冷链配送物流车辆调度优化研究
139 0
|
算法 自动驾驶
【无人车】用于无人地面车辆的路径跟踪算法(Matlab代码实现)
【无人车】用于无人地面车辆的路径跟踪算法(Matlab代码实现)
109 0
|
数据可视化 计算机视觉 智能硬件
人在房间里走了一圈,慕尼黑工业大学的研究推理出室内3D物体
人在房间里走了一圈,慕尼黑工业大学的研究推理出室内3D物体
118 0
|
机器学习/深度学习 传感器 算法
【VRP问题】基于遗传算法的连锁超市配送路线规划问题研究附matlab代码
【VRP问题】基于遗传算法的连锁超市配送路线规划问题研究附matlab代码
数车常用的三种退刀路线讲解
数车常用的三种退刀路线讲解
数车常用的三种退刀路线讲解
|
机器学习/深度学习 传感器 人工智能
快速行驶的自动驾驶,离现实还有多远?
随着人工智能的发展,萌芽于上个世纪70年代的自动驾驶技术,逐步成长为创业的风口。
156 0
快速行驶的自动驾驶,离现实还有多远?
|
人工智能 自动驾驶 安全
我把无人车的避障技术装进了iPad,刺激手部为盲人导航,杂货间也能畅通无阻
我把无人车的避障技术装进了iPad,刺激手部为盲人导航,杂货间也能畅通无阻
200 0