hdu 1250 Hat's Fibonacci (大数相加,水题)
发布时间:2020-12-14 04:08:10 所属栏目:大数据 来源:网络整理
导读:小记:之所以对这个水题写篇博文,主要是为了让自己谨记在写大数相加的代码时,要注意一点,用整数数组实现N进制的大整数相加算法在输出的时候记得用%0xd (x = lgN)。铭记这点就OK了。 题解:我是用数组进行预处理的,bignum[x][0] 表示第x个斐波那契数相对
小记:之所以对这个水题写篇博文,主要是为了让自己谨记在写大数相加的代码时,要注意一点,用整数数组实现N进制的大整数相加算法在输出的时候记得用%0xd (x = lgN)。铭记这点就OK了。 题解:我是用数组进行预处理的,bignum[x][0] 表示第x个斐波那契数相对于N进制有多少位。然后从bignum[x][bignum[x][0]] 一直输出到bignum[x][1]。 代码奉上: #include <iostream> #include <stdio.h> #include <string.h> using namespace std; #define max(x,y) ((x)>(y))?(x):(y) #define N 7500 int bignum[N][670]; void add(int x){ int i,t; t = max(bignum[x - 1][0],bignum[x - 2][0]); t = max(t,bignum[x - 3][0]); t = max(t,bignum[x - 4][0]); for(i = 1; i <= t; i ++){ bignum[x][i] += bignum[x - 1][i] + bignum[x - 2][i] + bignum[x - 3][i] + bignum[x - 4][i]; bignum[x][i + 1] = bignum[x][i] / 10000; bignum[x][i] %= 10000; } if(bignum[x][i] > 0)bignum[x][0] = t + 1;//存储第X个斐波那契数它的万进制表示有多少位 else bignum[x][0] = t; } void calc(){ int i; for(i = 5; i < N; i ++){ add(i); } } int main() { //freopen("d:in.txt","r",stdin); //freopen("d:out.txt","w",stdout); int i,j,n; for(i = 1; i < 5; i++){ bignum[i][0] = 1; bignum[i][1] = 1; } calc(); while(~scanf("%d",&n)){ if(n < 5){printf("1n");continue;} i = bignum[n][0]; printf("%d",bignum[n][i]); for(i -= 1; i > 0; i--){ printf("%04d",bignum[n][i]);//注意输出 } putchar('n'); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |