poj 2413 大数模拟(区间内的斐波那契数个数)
发布时间:2020-12-14 02:46:48 所属栏目:大数据 来源:网络整理
导读:题意:给定两个数a=b=10^100,求区间[a,b]内的斐波那契数的数量。 思路:数组模拟枚举出100位以内的斐波那契数,然后写一个比较函数进行比较即可。其中一个地方让我wa了n次:temp = f [i- 2 ][j]+ f [i- 1 ][j]+ f [i][j];写成了temp =? f [i- 2 ][j]+ f [i-
题意:给定两个数a<=b<=10^100,求区间[a,b]内的斐波那契数的数量。 思路:数组模拟枚举出100位以内的斐波那契数,然后写一个比较函数进行比较即可。其中一个地方让我wa了n次:temp = f[i-2][j]+f[i-1][j]+f[i][j];写成了temp =?f[i-2][j]+f[i-1][j];快哭了~~~ #include <stdio.h> #include <string.h> #define N 155 int f[1000][N]; char a[N],b[N]; int len=1,num; int fibo(){ int i,j,temp; memset(f,sizeof(f)); f[0][0] = 1; f[1][0] = 2; for(i = 2;len<101;i++){ for(j = 0;j<len;j++){ temp = f[i-2][j]+f[i-1][j]+f[i][j];//~~~~~~~~~~~~~~ f[i][j] = temp % 10; f[i][j+1] = temp / 10; } if(f[i][len]) len++; } return i-1; } int cmp(char x[N],int y[N]){ int i,strl; strl = strlen(x); for(i = 100;i>=0;i--) if(y[i]) break; if(strl == i+1){ for(j = i;j>=0;j--){ if(x[j] > (char)(y[j]+'0')) return 1; if(x[j] < (char)(y[j]+'0')) return -1; } return 0; } else if(strl > i+1) return 1; return -1; } void reverse(char* x){//将字符串逆转 int i,k = strlen(x); char j; for(i = 0;i<k/2;i++){ j = x[k-1-i]; x[k-1-i] = x[i]; x[i] = j; } } int main(){ num = fibo();//产生100位以内的斐波那契数列 while(scanf("%s %s",a,b)){ int i,res=0; if(a[0] == '0' && b[0] == '0') break; reverse(a); reverse(b); for(i = 0;i<num && cmp(b,f[i])>=0;i++) if(cmp(a,f[i])<=0) res++; printf("%dn",res); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |