斐波那契数列区间计数问题题解

问题描述

给定两个非常大的整数a和b（最多有100位），计算在区间[a,b]内有多少个斐波那契数。斐波那契数列定义为：

• f₁ = 1
• f₂ = 2
• fₙ = fₙ₋₁ + fₙ₋₂ (n≥3)

解题思路

1. 预处理斐波那契数列：预先计算足够多的斐波那契数（最多500个），因为斐波那契数增长非常快
2. 大数处理：使用数组存储每一位数字来处理大数运算
3. 二分查找：在预处理好的斐波那契数列中查找a和b的位置
4. 区间计数：根据查找结果计算区间内的斐波那契数数量

代码解析

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 550;
const int MAXNLEN = 130;

int F[MAXN][MAXNLEN]; // 存储斐波那契数的每一位
char Fi[MAXN][MAXNLEN]; // 存储斐波那契数的字符串形式

// 预处理斐波那契数列
void Fibo() {
    // 初始化前两个斐波那契数
    F[1][0] = 1;
    F[2][0] = 2;
    
    // 计算斐波那契数列
    for(int i = 3; i <= 500; ++i) {
        for(int j = 0; j <= 110; ++j) {
            F[i][j] = F[i][j] + F[i-1][j] + F[i-2][j];
            if(F[i][j] >= 10) { // 处理进位
                F[i][j+1] += F[i][j]/10;
                F[i][j] %= 10;
            }
        }
    }
    
    // 将斐波那契数转换为字符串形式
    for(int i = 1; i <= 500; ++i) {
        int j;
        // 找到最高非零位
        for(j = 110; j >= 0; j--)
            if(F[i][j] == 0)
                continue;
            else
                break;
        // 从高位到低位转换为字符
        int k = 0;
        for(; j >= 0; j--)
            Fi[i][k++] = F[i][j] + '0';
        Fi[i][k] = '\0'; // 字符串结束符
    }
}

// 比较两个大数的大小
int cmp(char *A, char *B) {
    int LenA = strlen(A);
    int LenB = strlen(B);
    if(LenA != LenB)
        return LenA > LenB ? 1 : -1;
    else
        return strcmp(A,B);
}

// 二分查找数字在斐波那契数列中的位置
int Search(char *Num, bool &flag) {
    int low = 1;
    int high = 480;
    while(low <= high) {
        int mid = (low+high)/2;
        int res = cmp(Num, Fi[mid]);
        if(res == 0) { // 找到相等的数
            flag = 1;
            return mid;
        }
        else if(res < 0) // Num < Fi[mid]
            high = mid - 1;
        else // Num > Fi[mid]
            low = mid + 1;
    }
    return low;
}

char A[MAXNLEN], B[MAXNLEN]; // 存储输入的两个大数

int main() {
    Fibo(); // 预处理斐波那契数列
    
    while(~scanf("%s %s", A, B)) {
        if(strcmp(A,"0")==0 && strcmp(B,"0") == 0)
            break;
        
        bool FlagA = 0, FlagB = 0;
        // 查找A和B在斐波那契数列中的位置
        int Left = Search(A, FlagA);
        int Right = Search(B, FlagB);
        
        // 计算区间内的斐波那契数数量
        if(FlagB) // B是斐波那契数
            printf("%d\n", Right-Left+1);
        else // B不是斐波那契数
            printf("%d\n", Right-Left);
    }
    return 0;
}

关键点解析

1. 大数处理：

   • 使用二维数组F存储斐波那契数的每一位
   • 从低位到高位计算，处理进位

2. 预处理优化：

   • 预先计算500个斐波那契数，足以覆盖10¹⁰⁰的范围
   • 将每个斐波那契数转换为字符串形式便于比较

3. 高效查询：

   • 使用二分查找确定数字在斐波那契数列中的位置
   • 比较函数先比较长度，再逐位比较

4. 区间计数：

   • 通过查找a和b的位置差计算区间内的斐波那契数数量
   • 处理边界情况（当b正好是斐波那契数时）

复杂度分析

• 预处理时间复杂度：O(n×m)，其中n是斐波那契数个数（500），m是数字最大位数（110）
• 查询时间复杂度：O(q×log n)，其中q是查询次数，n是斐波那契数个数
• 空间复杂度：O(n×m)，存储所有斐波那契数

该解决方案高效地处理了超大整数范围的斐波那契数计数问题，通过预处理和二分查找优化了查询效率。