0

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

出于某种原因，它工作到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
4

2 回答 2

2

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

于 2012-09-13T19:27:01.197 回答
0

随着数字越来越大，所以整数溢出，所以“环绕”正在发生，所以你可以使用 GNU GMP 库或使用字符串来表示数字，就像我对大数的阶乘所做的那样链接到http://codepad.org/ bkWNV0JC

于 2012-09-14T04:43:15.163 回答