求助：如何计算并显示超大斐波那契数（Fibonacci）

你的代码用unsigned long long存储斐波那契数，但该类型最多只能存19位十进制数，而第200项斐波那契数有42位，远超64位整数的范围，必须用大数模拟的方式实现——核心思路是用数组或字符串存储数字的每一位，手动实现加法逻辑。

修改方案步骤： #

• 放弃内置整数类型，改用数组存储大数的每一位十进制数字（比如int数组，每个元素存0-9）
• 手动实现两个大数的逐位加法，处理进位问题
• 保留动态规划核心逻辑：只保存前两项的值，避免冗余计算

示例代码（C语言） #

#include <stdio.h>
#include <string.h>

#define MAX_DIGITS 100  // 足够存第1000项斐波那契数

// 打印大数数组（从高位到低位）
void printBigNumber(int num[], int length) {
    for (int i = length - 1; i >= 0; i--) {
        printf("%d", num[i]);
    }
    printf("\n");
}

// 用动态规划计算第n项斐波那契数（大数版本）
void dynFibBig(int n) {
    if (n == 0) {
        printf("0\n");
        return;
    }
    if (n == 1) {
        printf("1\n");
        return;
    }

    // 数组下标0存个位，1存十位，以此类推
    int prev_prev[MAX_DIGITS] = {0};
    int prev[MAX_DIGITS] = {0};
    int current[MAX_DIGITS] = {0};
    prev_prev[0] = 0;  // F(0) = 0
    prev[0] = 1;       // F(1) = 1
    int prev_len = 1;
    int curr_len = 1;

    for (int i = 2; i <= n; i++) {
        int carry = 0;
        curr_len = prev_len;
        memset(current, 0, sizeof(current));

        // 逐位相加前两项
        for (int j = 0; j < prev_len; j++) {
            int sum = prev_prev[j] + prev[j] + carry;
            current[j] = sum % 10;
            carry = sum / 10;
        }
        // 处理最后可能的进位
        if (carry != 0) {
            current[curr_len] = carry;
            curr_len++;
        }

        // 更新前两项的值和长度
        memcpy(prev_prev, prev, sizeof(prev));
        memcpy(prev, current, sizeof(current));
        prev_len = curr_len;
    }

    printBigNumber(prev, prev_len);
}

int main() {
    dynFibBig(200);  // 计算第200项斐波那契数
    return 0;
}

代码说明： #

1. 数组下标0对应数字的个位，加法时从低位到高位处理更方便
2. 每次计算新项时，逐位相加前两项的对应位，加上进位得到当前位数字和新的进位
3. 用memcpy更新前两项存储，保证动态规划只保留最近两个状态
4. MAX_DIGITS可按需调整，比如计算第1000项可设为210（第1000项有209位）

内容的提问来源于stack exchange，提问作者Jaeric