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

このような大きな数値を使用すると、符号なし整数オーバーフローが発生し、「ラップアラウンド」が発生して、演算の元の結果 modulo 1 << bits、ビットが特定の整数型のビット幅になります。これらの数値を表現したい場合は、 GNU GMPなどのある種の bignum ライブラリを使用する必要があります。

于 2012-09-13T19:27:01.197 に答える
0

数値が大きくなり、整数がオーバーフローするため、「ラップアラウンド」が発生するため、GNU GMP ライブラリを使用するか、大きな数値の階乗で行ったように文字列を使用して数値を表すことができますhttp://codepad.org/へのリンクbkWNV0JC

于 2012-09-14T04:43:15.163 に答える