动态规划问题 - Fibonacci序列

我读this维基百科的文章，并试图实现C，其中一个“地图”只是一个int数组“地图”基础的解决方案，初始化为0动态规划问题 - Fibonacci序列

对于一些原因是它工作到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

来源

2012-09-13 Josh

您*确实已经意识到即使是'无符号的长长右'也溢出了吗？ – Mysticial

@Mystical：我没有，我从来没有使用过这么大的数字。快速浏览'limit.h＃ULONG_MAX'就会发现你确实是正确的。有关解决此问题的任何建议？ – Josh

不幸的是，C没有原生支持bignums。所以你需要自己写或者使用GMP等库。如果你愿意牺牲精度，那么去浮点可能是可以接受的。 – Mysticial

有了这样大的数字，你得到一个无符号整数溢出，这将导致“环绕”导致原始操作结果，模，位是特定整数类型的位宽。如果你想表示这些数字，你必须使用某种BIGNUM库，如GNU GMP.

来源

2012-09-13 19:27:01

**无符号**整数在计算结果超出范围时的行为完全由标准定义，它的算术模数为2^WIDTH'。 –

@DanielFischer哎呀，忽略。修正了，谢谢。 – 2012-09-14 04:36:29

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

来源

2012-09-14 04:43:15

动态规划问题 - Fibonacci序列

回答

相关问题