动态规划问题 – Fibonacci序列

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

由于某种原因，它可以达到fib(93) ，然后开始输出奇怪的数字。 如果重要的是我指定-std=c99 ：

 #include  #include  // 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 ，位是特定整数类型的位宽。 如果要表示这些数字，则必须使用某种bignum库，例如GNU GMP。

Answer 2

随着数字越来越大，所以整数越来越大，所以“环绕”正在发生，所以你可以使用GNU GMP库或使用字符串来表示数字就像我为大数据的因子链接到http://codepad.org/ bkWNV0JC