前几天在我们学校的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，一直到最后；因为要计算很多的数，因此没有在递归的过程中，把斐波那契数反过来；因为即使反过来，下次再使用时还要再反回去：
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中存储的数据反过来了。
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个字符大，就表示这整个字符串大，若第一个字符是相等的，才开始比较第二个，一直比较到最后。因此，我这里用了两个条件进行判断：
- 若data[i]的长度比a或b大，那铁定data[i]更大；
- 若data[i]的长度和a或b的一样，那strcmp(data[i], a)>0，则表示data[i]更大。
这样就能判断出边界了。
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);
}
