【问题描述】
如下图所示，一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房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 }
