how-many-fibs

前几天在我们学校的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);
}