ACM 495 Fibonacci Freeze

一開始以為很簡單，就算出費氏，
結果n = 5000時，數字根本超大，
心機啊……

像這題array這麼大的，不能設成區域變數，
要不然會stack overflow，
要用全域變數或malloc。

最後寫出來了，沒想到一直RE RE RE RE，
哇咧，原來費氏數列要從0開始，
難怪一直RE XD，
真蠢我也 orz。

/* ACM 495 Fibonacci Freeze
 * mythnc
 * 2011/11/07 11:53:16   
 * run time: 0.532
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXARY 1100
#define MAXN   5001

void init(int **);
void fibo(int **);
int bigadd(int *, int *, int *, int);
void printbig(int *);
void freen(int **);

int main(void)
{
    int n;
    int *number[MAXN];

    init(number);
    fibo(number);
    while (scanf("%d", &n) == 1) {
        printf("The Fibonacci number for %d is ", n);
        printbig(number[n]);
    }
    freen(number);
    return 0;
}

/* init: make space to n[i] and 
 * initialize content of n[i] to zero */
void init(int **n)
{
    int i;

    for (i = 0; i < MAXN; i++) {
        n[i] = (int *)malloc(sizeof(int) * MAXARY);
        memset(n[i], 0, sizeof(int) * MAXARY);
    }
}

/* fibo: calculate fibonacci number from 0 to 5000 */
void fibo(int **n)
{
    int i, digit;

    n[0][0] = 0;
    n[1][0] = digit = 1;
    for (i = 2; i < MAXN; i++)
        digit = bigadd(n[i], n[i - 1], n[i - 2], digit);

}

/* bigadd: big number addtion,
 * return it's digits */
int bigadd(int *n, int *pre, int *ppre, int d)
{
    int i;

    for (i = 0; i < d; i++)
        n[i] += pre[i] + ppre[i];

    /* carry */
    for (i = 0; i < d; i++)
        if (n[i] > 9) {
            n[i] %= 10;
            n[i + 1]++;
        }

    if (n[i] != 0)
        return i + 1;
    return i;
}

/* printbig: print out big number */
void printbig(int *n)
{
    int i;

    i = MAXARY - 1;
    while (n[i] == 0 && i > 0)
        i--;
    for (; i > -1; i--)
        printf("%d", n[i]);
    printf("\n");
}

void freen(int **n)
{
    int i;

    for (i = 0; i < MAXN; i++)
        free(n[i]);
}