蜜蜂路线-阿里云开发者社区

开发者社区> 华山青竹> 正文

蜜蜂路线

简介: 【问题描述】如下图所示,一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你:蜜蜂从蜂房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 }
利用高精度数据解决

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10076 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
2962 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
12071 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
11818 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
7496 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
4503 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
7365 0
+关注
华山青竹
一个喜欢玩代码的小青年呵呵呵
543
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载