動態規劃問題 - 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序列

回答

相關問題