gistfile1.c

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

#define MAX 100010
#define LEN 2300

unsigned int seq[MAX][LEN] = {0};

void double_dabble(int n, const unsigned int *arr, char **result)
{
    int nbits = 32*n;         /* length of arr in bits */
    int nscratch = nbits/3;   /* length of scratch in bytes */
    char *scratch = calloc(1 + nscratch, sizeof *scratch);
    int i, j, k;
    int smin = nscratch-2;    /* speed optimization */
 
    for (i=0; i < n; ++i) {
        for (j=0; j < 32; ++j) {
            /* This bit will be shifted in on the right. */
            int shifted_in = (arr[n-i-1] & (1 << (31-j)))? 1: 0;
 
            /* Add 3 everywhere that scratch[k] >= 5. */
            for (k=smin; k < nscratch; ++k)
              scratch[k] += (scratch[k] >= 5)? 3: 0;
 
            /* Shift scratch to the left by one position. */
            if (scratch[smin] >= 8)
              smin -= 1;
            for (k=smin; k < nscratch-1; ++k) {
                scratch[k] <<= 1;
                scratch[k] &= 0xF;
                scratch[k] |= (scratch[k+1] >= 8);
            }
 
            /* Shift in the new bit from arr. */
            scratch[nscratch-1] <<= 1;
            scratch[nscratch-1] &= 0xF;
            scratch[nscratch-1] |= shifted_in;
        }
    }
 
    /* Remove leading zeros from the scratch space. */
    for (k=0; k < nscratch-1; ++k)
      if (scratch[k] != 0) break;
    nscratch -= k;
    memmove(scratch, scratch+k, nscratch+1);
 
    /* Convert the scratch space from BCD digits to ASCII. */
    for (k=0; k < nscratch; ++k)
      scratch[k] += '0';
 
    /* Resize and return the resulting string. */
    *result = realloc(scratch, nscratch+1);
    return;
}

void add(int a, int b) {
	int i, carry;

	for (i = 0, carry = 0; i < LEN; i++) {
		seq[a + 1][i] = seq[a][i] + seq[b][i] + carry;
		carry = (seq[a + 1][i] < seq[a][i])?1:0;
	}

	if (carry) seq[a + 1][i++] = carry;
}

int main() {
	int n, i, len;
	char *strnum = NULL;

	seq[1][0] = 1;																																																																																																																			
	i = scanf("%d", &n);
    
	for (i = 2; i <= n; i++)
		add(i - 1, i - 2);
	
	for(len = LEN; len > 0 && seq[n][len] == 0; len--);
	double_dabble(len+1, seq[n], &strnum);
	printf("%s\n", strnum);
	fflush(stdout);

	return 0;
}