动态规划问题 - Fibonacci序列 [英] Dynamic Programming Issue - Fibonacci Sequence

问题描述

我在读这的维基百科的文章，并试图以实施地图在C，解决方案，其中地图只是一个int数组，初始化为0。

出于某种原因，它的工作原理到 FIB（93），然后开始输出陌生号码。如果重要的我指定 -std = C99 ：

 的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;//重新presents一个FIB NUM
无符号的typedef长长fib_t;//我们的'地图'的默认值
const int的FIB_NULL = 0;//能够从输入得到的，在这里设置现在
const int的FIB_MAX = 100;//我们的地图的FIB NUMS
静态fib_t * FIBMAP;//计算FIB NUMñ
fib_t FIB（无符号整数N）
{
    //如果此民中，n，是不是0或1，并且是FIB_NULL，然后计算它
    如果（正→1＆放大器;＆放大器; FIB_NULL == FIBMAP [n]）的
    {
        FIBMAP [η] = FIB（N-1）+ FIB（N-2）;
    }    //从地图上得到它
    返回FIBMAP [N];
}//用于设置地图的小谎
静态无效initFibMap（）
{
    //模拟图
    FIBMAP =的malloc（sizeof的（fib_t）* FIB_MAX）;    //初始化为'空'
    memset的（FIBMAP，FIB_NULL，sizeof的（fib_t）* FIB_MAX）;    //定义
    FIBMAP [0] = 0;
    FIBMAP [1] = 1;
}INT主（INT ARGC，CHAR *的argv []）
{
    //设置我们的地图
    initFibMap（）;    为（unsigned int类型I = 0; I＆LT; FIB_MAX;我++）
    {
        // 94休息
        的printf（纤维蛋白原＃％D：％LLU \\ n，我撒了个谎（I））;
    }
}
 

奇怪的输出：

  //。 。 。
//。 。 。
//蛋白原＃90：2880067194370816120 //好
//蛋白原＃91：4660046610375530309 //好
//蛋白原＃92：7540113804746346429 //好
//蛋白原＃93：12200160415121876738 //好
//蛋白原＃94：1293530146158671551 //什么呢？
//蛋白原＃95：13493690561280548289
//蛋白原＃96：14787220707439219840
//蛋白原＃97：9834167195010216513
//蛋白原＃98：6174643828739884737
//蛋白原＃99：16008811023750101250
 

解决方案

有了这样大的数字，你得到一个无符号整数溢出，从而导致环绕导致操作，模原结果 1 LT;＆LT;位，比特属于特定整数类型的位宽。如果你想重新present这些数字，你必须使用某种BIGNUM库，如 GNU GMP。

I was reading this Wikipedia article, and attempting to implement a 'map' based solution in C, where a 'map' is just an int array, initialized to 0.

For some reason it works up to fib(93), then starts outputting strange numbers. If it matter's I'm specifying -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));
    }
}

Strange output:

// . . .
// . . .
// 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

解决方案

With such large numbers, you're getting an unsigned integer overflow, which causes a "wrap around" to result in the original result of the operation, modulo 1 << bits, bits being the bit width of the particular integer type. If you want to represent these numbers, you have to use some kind of bignum library, such as the GNU GMP.

这篇关于动态规划问题 - Fibonacci序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！