how-many-fibs

蚊子前端博客
发布于 2015-06-25 06:00
OJ平台上的一道大数运算的题目,计算两个数之间的斐波那契数的个数

前几天在我们学校的OJ平台上做了一道大数运算的题目,其实也不算很难,一次就通过了,不过还是想用日志记录一下解题思路。

先附上题目的链接How many Fibs?。这个题目的意思是,输入两个数a和b(a<=b<=10^100),计算a和b之间斐波那契数的个数(包含a和b,即若a或b也是斐波那契数的话,也计算在内)。

斐波那契数的计算我们都很熟悉,使用递归的方法就可以。 从给出的输入范围我们就能知道,这肯定是个大数运算了,10^100的数据,即时是使用double__int64的类型都存不下的。对于这种大数运算,只能采用字符串进行模拟了。

这里有一个小技巧,感觉可以节省一些时间:首先把10^100以内的斐波那契数都计算出来,存放到数组中,当输入数据时,直接在数组中寻找开始和结束的位置,然后就能计算出中间的个数。不用每次输入a和b都重新递归一遍。那数组应该开多大比较合适呢,经过计算后,发现10^100以内的斐波那契数没有超过480个,因此用来存储数据的数组开到480就可以了。其实从这里,我们也能看到斐波那契数增长的恐怖程度了,还没到480个数,就已经差不多是个100位的数字了。

下面是是用递归字符串计算斐波那契数的递归过程,不过下面计算出的斐波那契数都是倒着的,大数计算就是模拟我们人类计算两个数的和的过程,先计算个位,若超过10就向高位进1,一直到最后;因为要计算很多的数,因此没有在递归的过程中,把斐波那契数反过来;因为即使反过来,下次再使用时还要再反回去:

COPYCPP

char data[485][110]; // 存储斐波那契数,每项默认是"0" // 计算第k个斐波那契数,用s返回 void fb(int k, char *s){ // 若数组中已经存在斐波那契数,直接返回 if(strcmp(data[k], "0")!=0){ strcpy(s, data[k]); return; } char x[110], y[110], result[110]; int c, i, j, n, m, t1, t2, min, max1, max2; // 递归计算出第k-2和第k-1的斐波那契数x, y fb(k-2, x); fb(k-1, y); // 计算x, y的长度 t1 = strlen(x); t2 = strlen(y); min = t1<t2 ? t1 : t2; c = 0; // 向高位的进位 // 计算两个数的公共部分 for(i=0; i<min; i++){ result[i] = ((x[i]-'0')+(y[i]-'0')+c)%10 + '0'; c = ((x[i]-'0')+(y[i]-'0')+c)/10; } // 两个数中多余的部分直接给result for(i=min; i<t1; i++){ result[i] = ((x[i]-'0')+c)%10 + '0'; c = ((x[i]-'0')+(y[i]-'0')+c)/10; } for(i=min; i<t2; i++){ result[i] = ((y[i]-'0')+c)%10 + '0'; c = ((x[i]-'0')+(y[i]-'0')+c)/10; } // 若计算完成后的进位是1,则把1放到最后 if(c>=1){ result[i] = '1'; i++; } result[i] = '\0'; // 把计算出的结果存储到数组中 strcpy(data[k], result); // 返回 strcpy(s, result); }

上面也说了,现在data数组中存储的斐波那契数都是倒着的,那输入a和b时怎么比较呢。我们仅仅是在计算斐波那契数的递归过程中没有颠倒,待计算全部完后就可以把data中存储的数据反过来了。

COPYCPP

void reverse(char *s){ int i, t, tt; char temp; t = strlen(s); tt = t/2; for(i=0; i<tt; i++){ temp = s[i]; s[i] = s[t-1-i]; s[t-1-i] = temp; } }

用一个循环就能把data数组中所有的斐波那契数都颠倒过来。

可是,在C语言中,使用strcpm进行字符串比较时,"2"是比"100"要大的,因为当开始进行字符串比较时,首先比较比较第一个字符,若第1个字符大,就表示这整个字符串大,若第一个字符是相等的,才开始比较第二个,一直比较到最后。因此,我这里用了两个条件进行判断:

  1. 若data[i]的长度比a或b大,那铁定data[i]更大;

  2. 若data[i]的长度和a或b的一样,那strcmp(data[i], a)>0,则表示data[i]更大。

这样就能判断出边界了。

COPYCPP

while(scanf("%s %s", a, b)){ if(strcmp(a, "0")==0 && strcmp(b, "0")==0){ break; } start = len, end = 0; ed = 0; at = strlen(a); bt = strlen(b); for(i=0; i<len; i++){ t = strlen(data[i]); if(t>at || (t==at && strcmp(data[i], a)>=0)){ start = i; break; } } for(i=0; i<len; i++){ t = strlen(data[i]); if(t>bt || (t==bt && strcmp(data[i], b)>=0)){ end = i; // 若b是斐波那契数,则个数+1 if(strcmp(data[i], b)==0){ ed = 1; } break; } } printf("%d\n", end-start+ed); }
标签:
阅读(303)

公众号:

qrcode

微信公众号:前端小茶馆