Since long long cannot store the 100th Fibonacci number, you need to implement or use an existing library for bignum.
You may use linked lists to solve this problem. Read about bignum here http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic Here is my implementation for solving this problem, #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define REP(i, n) for(int i = 0; i < (n); i++) #define FILL(c, v) memset(c, v, sizeof(c)) const int MX = 100000; int prv1[MX], prv2[MX], cur[MX], l1, l2, lcur; int main() { FILL(prv1, 0); FILL(prv2, 0); FILL(cur, 0); int n; scanf("%d", &n); prv1[0] = 0; l1 = 1; prv2[0] = 1; l2 = 1; cur[0] = 0; lcur = 1; REP(i, n) { int mx = max(l1, l2); int carry = 0; REP(j, mx) { int imd = prv1[j]+prv2[j]+carry; cur[j] = imd%10; carry = imd/10; } if(carry) { cur[mx++] = carry; } lcur = mx; REP(j, l1) prv2[j] = prv1[j]; l2=l1; REP(j, lcur) prv1[j] = cur[j]; l1=lcur; } REP(i, lcur) printf("%d", cur[lcur-i-1]); printf("\n"); } On Jul 31, 9:31 pm, bharath sriram <bharath.sri...@gmail.com> wrote: > Since both the "normal" recursive (stack overflow) and non-recursive (data > type overflow) versions fails, is there a way one can use linked lists to > solve this problem? > > Bharath. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
