euler25

The Fibonacci sequence is defined by the recurrence relation:

    Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

    F1 = 1
    F2 = 1
    F3 = 2
    F4 = 3
    F5 = 5
    F6 = 8
    F7 = 13
    F8 = 21
    F9 = 34
    F10 = 55
    F11 = 89
    F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?
--------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _digit_t {
    char v;
    int base;
    struct _digit_t *next;
} digit_t;

/* invert input */
digit_t *create_digit(char *d)
{
    digit_t *head;
    digit_t *node, *pnode=NULL;
    int i;

    for (i=strlen(d)-1; i >= 0 ; i--) {
        node = malloc(sizeof(digit_t));
        node->v = d[i];
        node->next = NULL;

        if (pnode) {
            pnode->next = node;
            pnode = node;
        } else {
            pnode = node;
            head = node;
        }
    }

    return head;
}

digit_t *add(digit_t *m, digit_t *n)
{
    digit_t *result;
    digit_t *node;
    digit_t *prev = NULL;
    int carry = 0;

    while (m && n) {
        node = malloc(sizeof(*node));
        node->next = NULL;
        node->v = '0';
        if (prev) {
            prev->next = node;
            prev = node;
        } else {
            result = node;
            prev = node;
        }

        carry += (m->v - '0') +(n->v - '0');
        node->v = carry % 10 + '0';
        carry /= 10;

        m = m->next;
        n = n->next;
    }

    while (m) {
        node = malloc(sizeof(*node));
        node->next = NULL;
        node->v = '0';
        if (prev) {
            prev->next = node;
            prev = node;
        } else {
            result = node;
            prev = node;
        }
        carry += m->v - '0';
        node->v = '0' + carry % 10;
        carry /= 10;

        m = m->next;
    }

    while (n) {
        node = malloc(sizeof(*node));
        node->next = NULL;
        node->v = '0';
        if (prev) {
            prev->next = node;
            prev = node;
        } else {
            result = node;
            prev = node;
        }
        carry += n->v - '0';
        node->v = carry % 10 + '0';
        carry /= 10;

        n = n->next;
    }

    while (carry) {
        node = malloc(sizeof(*node));
        node->next = NULL;
        node->v = '0';
        if (prev) {
            prev->next = node;
            prev = node;
        } else {
            result = node;
            prev = node;
        }

        node->v = carry % 10 + '0';
        carry /= 10;
    }

    return result;
}

/* invert output */
void output_digit(digit_t *head)
{
    digit_t *node = head;

    if (!head)
        return;

    output_digit(head->next);
    putchar(node->v);
}

void free_digit(digit_t *p)
{
    digit_t *node=p;

    while (node) {
        digit_t *next = node->next;
        free(node);
        node = next;
    }
}

int check(digit_t *n)
{
    int num = 0;

    output_digit(n);
    printf("\n");
    while (n) {
        num++;
        n = n->next;
    }

    return num == 1000;
}

int main(int argc, const char *argv[])
{
    digit_t *n, *m, *sum;
    int result;

    n = create_digit("1");
    m = create_digit("1");
    result = 2;
    while (1) {
        result++;
        sum = add(n, m);
        if (check(sum)) break;

        free_digit(n);
        n = m;
        m = sum;
    }

    printf("result: %d\n", result);

    return 0;
}

任意精度的加法。