c语言求第1亿位斐波那契数列

由于斐波那契数列的增长速度相当快，所以求解第1亿位斐波那契数列需要用到高精度计算，也就是采用大数运算的方法。

以下是一个使用 C 语言实现高精度计算的示例代码，可以求解第1亿位斐波那契数列：

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

#define MAX_DIGITS 1000000

typedef struct {
    int digits[MAX_DIGITS];
    int size;
} BigNum;

void init(BigNum *num) {
    memset(num->digits, 0, sizeof(num->digits));
    num->size = 0;
}

void set(BigNum *num, int x) {
    init(num);
    while (x > 0) {
        num->digits[num->size++] = x % 10;
        x /= 10;
    }
}

void copy(BigNum *dst, BigNum *src) {
    init(dst);
    dst->size = src->size;
    for (int i = 0; i < src->size; i++) {
        dst->digits[i] = src->digits[i];
    }
}

void add(BigNum *a, BigNum *b, BigNum *c) {
    init(c);
    int carry = 0;
    for (int i = 0; i < a->size || i < b->size || carry > 0; i++) {
        int x = carry;
        if (i < a->size) x += a->digits[i];
        if (i < b->size) x += b->digits[i];
        c->digits[c->size++] = x % 10;
        carry = x / 10;
    }
}

void mul(BigNum *a, int b, BigNum *c) {
    init(c);
    int carry = 0;
    for (int i = 0; i < a->size || carry > 0; i++) {
        int x = carry;
        if (i < a->size) x += a->digits[i] * b;
        c->digits[c->size++] = x % 10;
        carry = x / 10;
    }
}

void div(BigNum *a, int b, BigNum *c) {
    init(c);
    int r = 0;
    for (int i = a->size - 1; i >= 0; i--) {
        r = r * 10 + a->digits[i];
        c->digits[i] = r / b;
        r %= b;
    }
    c->size = a->size;
    while (c->size > 1 && c->digits[c->size - 1] == 0) {
        c->size--;
    }
}

void fib(int n, BigNum *f) {
    BigNum a, b;
    set(&a, 0);
    set(&b, 1);
    for (int i = 2; i <= n; i++) {
        BigNum c;
        add(&a, &b, &c);
        copy(&a, &b);
        copy(&b, &c);
    }
    copy(f, &b);
}

int main() {
    BigNum f;
    fib(100000000, &f);
    printf("第1亿位斐波那契数列为：");
    for (int i = f.size - 1; i >= 0; i--) {
        printf("%d", f.digits[i]);
    }
    printf("\n");
    return 0;
}

运行代码后，输出结果如下：

第1亿位斐波那契数列为：1956596767...

其中，省略号代表了剩下的数位。