@Amit: Thanks for the solution but I have seen this approach. I was wondering how this can be solved using linked lists without using bignum libraries.
Bharath On Jul 31, 12:38 pm, amit karmakar <amit.codenam...@gmail.com> wrote: > 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 > herehttp://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.
