网站首页布局设计模板,wordpress文章发表时间,网站搭建费用价格表,做汽车拆解视频网站1143 多少个Fibonacci数 时间限制:500MS 内存限制:65536K 提交次数:270 通过次数:16 题型: 编程题 语言: G;GCC Description 给你如下Fibonacci 数的定义#xff1a;
F1 1
F2 2
Fn Fn-1 Fn-2 (n 3)
给你两个数a与b#xff0c;现要求你计算在a与b之间;GCC Description 给你如下Fibonacci 数的定义
F1 1
F2 2
Fn Fn-1 Fn-2 (n 3)
给你两个数a与b现要求你计算在a与b之间包括a、b有多少个Fibonacci 数 输入格式 有多行每行有两个数a、b使用空格分隔a b 10^100即最大10的100次方
最后一行为两个0 输出格式 除了最后一行其它每一行要求输出在a与b之间的Fibonacci 数的个数一行一个 输入样例 10 100
1234567890 9876543210
0 0输出样例 5
4作者 admin 这题刚开始做时懵逼了好久后来别人提示了下才会做。。。各种坑。。。代码注释里讲解解题步骤 1 /*#include cstdio2 #include cstring3 #define N 10004 5 using namespace std;6 char f[N5][N];7 //8 //高精度加法9 void big_plus(char a[],char b[],int t)10 {11 int c[N],d[N];12 memset(c,0,sizeof(c));memset(d,0,sizeof(d));//数组全部清0。13 int len_a,len_b,i,j,k;14 //15 i1;16 len_astrlen(a);len_bstrlen(b);17 //18 //将字符数组转为整型数组逆方向。19 for(klen_a-1;k0;k--)20 c[i]a[k]-0;21 j1;22 for(klen_b-1;k0;k--)23 d[j]b[k]-0;24 //25 klen_alen_b?len_a:len_b;26 for(i1;ik;i)//将每一位相加满十进位。27 {28 c[i1](c[i]d[i])/10;29 c[i](c[i]d[i])%10;30 }31 //32 if(c[k1]) //判断最高位是否有进位33 kk1;34 j0;35 for(ik;i1;i--) //将整型数组转变为字符数组存到f数组里。36 f[t][j]c[i]0;37 }38 //39 40 int big_cmp(char a[],char b[])//高精度 数字比较。ab返回1ab返回0ab返回-1。41 {42 int i,len_a,len_b;43 len_astrlen(a);44 len_bstrlen(b);45 //46 if(len_alen_b)47 return 1;48 else if(len_alen_b)49 return 0;50 else51 {52 for(i0;ilen_a;i)53 {54 if(a[i]b[i])55 return 1;56 else if(a[i]b[i])57 return 0;58 else continue;59 }60 }61 return -1; //上面的return均未执行则说明ab。62 }63 int main()64 {65 int i,j;66 char f1[N],f2[N];67 memset(f,\0,sizeof(f));68 f[1][0]1; f[2][0]2;69 //70 //下面循环累加打表法。71 for(i3;iN;i)72 {73 big_plus(f[i-2],f[i-1],i);74 }75 //76 while(scanf(%s%s,f1,f2))77 {78 int cnt0;79 if((f1[0]-0)0||(f2[0]-0)0)80 break;81 //82 for(i1;iN;i)//这个循环用来找f1的位置83 {84 if(big_cmp(f[i],f1)-1)85 {86 cnt1;87 i;88 break;89 }90 if(big_cmp(f[i],f1)0)91 {92 cnt0;93 break;94 }95 }96 for(ji;jN;j)//这个循环用来找f2的位置97 {98 if(big_cmp(f[j],f2)0)99 cnt;
100 else
101 break;
102 }
103 //
104 printf(%d\n,cnt);
105 }
106
107
108 return 0;
109 }
110 */
111
112 #includecstdio
113 #includecstring
114 #define N 1000
115 char fb[N5][N];//存储前1000项的fb
116 //高精度数比较 返回1表示ab 返回-1表示ab 0表示ab
117 int big_cmp(char a[],char b[])
118 {
119 int i,len_a,len_b;
120 len_astrlen(a);
121 len_bstrlen(b);
122 if(len_alen_b) return 1;//先比长度
123 else if(len_alen_b) return 0;
124 else//长度相同的时候再从高位开始逐一比较
125 {
126 for(i0; ilen_a; i)
127 {
128 if(a[i]b[i]) return 1;
129 else if(a[i]b[i]) return 0;
130 else continue;
131 }
132 }
133 return -1;//全部比较完毕以上return未生效 就是 ab
134 }
135 //高精度加法
136 void big_plus(char a[],char b[],int t)
137 {
138 int c[N],d[N];
139 memset(c,0,sizeof(c)); //数组全部清0。
140 memset(d,0,sizeof(d));
141 int len_a,len_b,i,j,k;
142 i1;
143 len_astrlen(a);
144 len_bstrlen(b);
145 //字符数组转为整形数组 逆置存放
146 for(klen_a-1; k0; k--)
147 c[i]a[k]-0;
148 j1;
149 for(klen_b-1; k0; k--)
150 d[j]b[k]-0;
151
152 klen_alen_b?len_a:len_b;
153 for(i1; ik; i) //将每一位相加满十进位。
154 {
155 c[i1](c[i]d[i])/10;
156 c[i](c[i]d[i])%10;
157 }
158 if(c[k1]) kk1; //判断最高位是否有进位
159
160 j0;
161 for(ik; i1; i--) //将整形数组转化为字符数组存在fb数组
162 fb[t][j]c[i]0;
163 }
164 int main()
165 {
166 int i,j;
167 char s1[N],s2[N];
168 memset(fb,\0,sizeof(fb));
169 fb[1][0]1;
170 fb[2][0]2;
171 //下面循环累加打表法。
172 for(i3; iN; i)
173 big_plus(fb[i-2],fb[i-1],i);
174
175 while(scanf(%s%s,s1,s2))
176 {
177 int cnt0;
178 if(!((s1[0]-0)||(s2[0]-0))) break;
179 for(i1; iN; i)
180 {
181 //查找a的位置 i
182 if(big_cmp(fb[i],s1)-1)
183 {
184 cnt1;
185 i;
186 break;
187 }
188 if(big_cmp(fb[i],s1)0)
189 {
190 cnt0;
191 break;
192 }
193 }
194 for(ji; jN; j)
195 if(big_cmp(fb[j],s2)0) cnt;
196 else break;
197 printf(%d\n,cnt);
198 }
199 return 0;
200 } 转载于:https://www.cnblogs.com/geek1116/p/5213292.html