c - 动态规划问题-斐波那契数列

Question

我正在阅读this维基百科文章，并尝试在 C 中实现基于“ map ”的解决方案，其中“ map ”只是一个初始化为 0 的 int 数组。

由于某种原因，它会工作到fib(93)，然后开始输出奇怪的数字。如果重要的话，我指定 -std=c99:

#include <stdio.h>
#include <stdlib.h>

// represents a fib num
typedef unsigned long long fib_t;

// the default value of our 'map'
const int FIB_NULL   = 0;

// could get from input, set here for now
const int FIB_MAX    = 100;

// our 'map' for fib nums
static fib_t *fibMap;

// calculate the fib num n
fib_t fib( unsigned int n )
{
    // if this num, n, is not 0 or 1, and is FIB_NULL, then calculate it
    if( n > 1 && FIB_NULL == fibMap[n] )
    {
        fibMap[n] = fib( n-1 ) + fib( n-2 );
    }

    // get it from the map
    return fibMap[n];
}

// used to setup the 'map' for the fibs
static void initFibMap()
{
    // emulate a map
    fibMap = malloc( sizeof(fib_t) * FIB_MAX);

    // initialize it to 'null'
    memset(fibMap, FIB_NULL, sizeof(fib_t) * FIB_MAX);

    // by definition
    fibMap[0] = 0;
    fibMap[1] = 1;
}

int main(int argc, char *argv[]) 
{
    // setup our 'map'
    initFibMap();

    for( unsigned int i=0; i<FIB_MAX; i++ )
    {
        // breaks on 94
        printf("Fib #%d: %llu\n",i, fib(i));
    }
}

奇怪的输出:

// . . .
// . . .
// Fib #90: 2880067194370816120  // good
// Fib #91: 4660046610375530309  // good
// Fib #92: 7540113804746346429  // good
// Fib #93: 12200160415121876738 // good
// Fib #94: 1293530146158671551  // WHAT?
// Fib #95: 13493690561280548289
// Fib #96: 14787220707439219840
// Fib #97: 9834167195010216513
// Fib #98: 6174643828739884737
// Fib #99: 16008811023750101250

Answer 1

对于如此大的数字，您会遇到无符号整数溢出，这会导致“环绕”导致运算的原始结果模 1 << bits ，bits 是特定整数类型的位宽度。如果你想表示这些数字，你必须使用某种bignum库，例如GNU GMP.