hdu 1316 How Many Fibs?(Fibonacci+高精度+二分)

hdu 1316 How Many Fibs?(Fibonacci+高精度+二分)

题目：​​Input

10 100

1234567890 9876543210

0 0

Sample Output

5

4

不会是一个一个找，二分确定上下界，最后相减即可。

#include #include #include using namespace std;const int m=105;char f[1000][m+2]; //估计1000内的feibo可以达到1e100char a[m+2],b[m+2];int cmp_ab(char *s1,char *s2){ // 比较两个数字 why not use strcmp(s1,s2)? for(int i=0;i<=m;i++){ if(i==m)return s1[i]-s2[i]; if(s1[i]!=s2[i])return s1[i]-s2[i]; }}int find1(int i,char *x){ //如果没有找到，将会返回接近结果的下界（上界不是feibo）。 int low=0,high=i,mid; while(low<=high){ mid=(low+high)>>1; int val=cmp_ab(x,f[mid]); //int val=strcmp(x,f[mid]); if(val>0)low=mid+1; else if(val==0)return mid-1; else high=mid-1; } return high; // not find. high>1; int val=cmp_ab(x,f[mid]); //int val=strcmp(x,f[mid]); if(val>0)low=mid+1; else if(val==0)return mid+1; else high=mid-1; } return low; // not find. low>high}int main(){ //freopen("cin.txt","r",stdin); f[0][m]=1; f[1][m]=2; int p=m,i=2; while(f[i-1][5]<=1){ for(int j=m;j>=p;j--){ f[i][j]=f[i-1][j]+f[i-2][j]; } for(int j=m;j>=p;j--){ int c=f[i][j]/10; if(c>0){ f[i][j-1]+=c; f[i][j]=f[i][j]%10; } } if(f[i][p-1]>0)p--; i++; } while(cin>>a>>b){ if(a[0]=='0'&&b[0]=='0') break; int len1=strlen(a),len2=strlen(b); int d,k; for(d=len1-1,k=m;d>=0;d--,k--){ //把数字字符串的内容移动到右边：123000 --> 000123 a[k]=a[d]-'0'; a[d]=0; } for(d=len2-1,k=m;d>=0;d--,k--){ b[k]=b[d]-'0'; b[d]=0; } int l=find1(i-1,a),r=find2(i-1,b); printf("%d\n",r-l-1); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); } return 0;}

为什么不用strcmp(s1,s2)呢？看看我从百度百科上偷来的源码：

​​int​​​ ​​​(strap)(​​​ ​​​const​​​ ​​​char​​​ ​​​*sl,​​​ ​​​const​​​ ​​​char​​​ ​​​*s2)​​ ​​{​​ ​​/*compare unsigned char sl[],s2[]*/​​ ​​for​​​ ​​​(;*sl==*s2;++sl,++s2)​​ ​​if​​​ ​​​(*sl==​​​ ​​​'\0'​​​ ​​​)​​ ​​return​​​ ​​​(0);​​ ​​return​​​ ​​​((*(unsignedchar*)sl<*(unsignedchar*)s2)?-1:+1);​​ ​​}​​ 当*​​sl='\0'时直接得到0的结果。所以像"---4"，"---3"这样的字符串比较得到的是0而不是1('-'表示'\0')。​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。