454,382 Members | 1,567 Online
Need help? Post your question and get tips & solutions from a community of 454,382 IT Pros & Developers. It's quick & easy.

# FIbonacci

 P: n/a Hey guys this is the fibonacci series. But Im having this huge problem. First of all I want to do the simplest code possible so then I can use user defined functions and arrays. But this one didnt came out well. Any suggestions! #include #include int main () { int fib, n; for(n=0; n<=10; n++) { fib=(n-1)+(n-2); printf("%d \n", fib); } return 0; } Dec 11 '05 #1
11 Replies

 P: n/a Am Sun, 11 Dec 2005 07:06:00 -0800 schrieb MARQUITOS51: Hey guys this is the fibonacci series. But Im having this huge problem. First of all I want to do the simplest code possible so then I can use user defined functions and arrays. But this one didnt came out well. Any suggestions! #include #include int main () { int fib, n; for(n=0; n<=10; n++) { fib=(n-1)+(n-2); printf("%d \n", fib); } return 0; } As far as I remember, this isn't the fibonacci algorithm. First it starts with 1 and 1, the third element of fibonacci series is the addition of the first and second. So fib(n)=fib(n-1)+fib(n-2). Not saving all elements you are able to only save the last elements in variables and shift them. But what you did on the indexing element doesn't make any sense. Bye, Stefan Dec 11 '05 #2

 P: n/a Hey I did this a few moments ago and it workes. Can you check it and suggest how to optimize. Im also looking how to convert it to user defined function. #include #include int main () { int f[50]; int n=2; f[0]=0; f[1]=1; do { f[n]=f[n-1]+f[n-2]; n++; } while(n<=49); for(n=0; n<=49; n++) {printf("%d \n", f[n]);} return 0; } Dec 11 '05 #3

 P: n/a MARQUITOS51 wrote: Hey I did this a few moments ago and it workes. Can you check it and suggest how to optimize. Im also looking how to convert it to user defined function. Sure, it works, if you don't ever plan on wanting more than 50 Fibonacci numbers. malloc() and friends can help you store an arbitrary number of Fibonacci numbers. If you're just trying to print them, you don't need more than three distinct variables. Think about it. #include #include Why are you including this header? You're not using anything from it. int main () int main( void ) /* better */ -- Christopher Benson-Manica | I *should* know what I'm talking about - if I ataru(at)cyberspace.org | don't, I need to know. Flames welcome. Dec 11 '05 #4

 P: n/a MARQUITOS51 wrote: Hey guys this is the fibonacci series. But Im having this huge problem. First of all I want to do the simplest code possible so then I can use user defined functions and arrays. But this one didnt came out well. Any suggestions! #include unsigned fib(unsigned n) { return n <= 2 ? 1 : fib(n - 1) + fib(n - 2); } int main(void) { printf("fib(17) is: %d\n", fib(17)); return 0; } P.Krumins Dec 11 '05 #5

 P: n/a "Peteris Krumins" wrote in message news:11*********************@f14g2000cwb.googlegro ups.com... [snip] #include unsigned fib(unsigned n) { return n <= 2 ? 1 : fib(n - 1) + fib(n - 2); Personally, I'd make that: return n < 2 ? n : fib(n - 2) + fib(n - 1); } int main(void) { printf("fib(17) is: %d\n", fib(17)); return 0; } Alex Dec 11 '05 #6

 P: n/a Peteris Krumins wrote: MARQUITOS51 wrote:Hey guys this is the fibonacci series. But Im having this huge problem.First of all I want to do the simplest code possible so then I can useuser defined functions and arrays. But this one didnt came out well.Any suggestions! #include unsigned fib(unsigned n) { return n <= 2 ? 1 : fib(n - 1) + fib(n - 2); } int main(void) { printf("fib(17) is: %d\n", fib(17)); return 0; } Somebody always proposes this solution, but it's a poor one. Try it with fib(47), say, and tell us how long it takes. Hint: You won't need a high-precision timer. -- Eric Sosman es*****@acm-dot-org.invalid Dec 11 '05 #7

 P: n/a Eric Sosman wrote: Peteris Krumins wrote: Somebody always proposes this solution, but it's a poor one. Try it with fib(47), say, and tell us how long it takes. Hint: You won't need a high-precision timer. Yes, the solution has exponential complexity. P.Krumins Dec 11 '05 #8

 P: n/a In article , Eric Sosman writes: Peteris Krumins wrote: #include unsigned fib(unsigned n) { return n <= 2 ? 1 : fib(n - 1) + fib(n - 2); } int main(void) { printf("fib(17) is: %d\n", fib(17)); return 0; } Somebody always proposes this solution, but it's a poor one. Try it with fib(47), say, and tell us how long it takes. Hint: You won't need a high-precision timer. Well, there's always this one (with error checking left as an exercise for the reader): /*** prev2 and prev are the two immediately preceeding values in the series; prev2 is F(n-2) and prev is F(n). pos is the current position in the series. want is the position we're looking for. ***/ unsigned fib_cps(unsigned prev2, unsigned prev, unsigned pos, unsigned want) { if (want <= 2) return 1; if (pos == want) return prev2 + prev; return fib_r(prev, prev2 + prev, pos + 1, want); } unsigned fib(n) { return fib_cps(1, 1, 3, n); } Even written this way, and compiled without optimization (I verified that the compiler left the tail-recursive call in rather than optimizing it to a branch), this computes fib(47) in negligible time. But of course it's just the forward-iterative version written as tail recursion. It'd be possible to rewrite Peteris' backward-recursing algorithm using continuation-passing style and tail recursion, but since C lacks dynamic closures we'd have to emulate them. And that would just involve recursively creating some sort of list of instructions to run the forward-iterative algorithm, so it's not very interesting. -- Michael Wojcik mi************@microfocus.com Is it any wonder the world's gone insane, with information come to be the only real medium of exchange? -- Thomas Pynchon Dec 13 '05 #9

 P: n/a Peteris Krumins wrote: Eric Sosman wrote: Peteris Krumins wrote: Somebody always proposes this solution, but it's a poor one. Try it with fib(47), say, and tell us how long it takes. Hint: You won't need a high-precision timer. Yes, the solution has exponential complexity. Exercise to the reader: Describe a function to precisely count the number of "+" operations performed by this function for computing f(n). (Hint: its easier than you think.) -- Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ Dec 14 '05 #10

 P: n/a On 2005-12-11, Peteris Krumins wrote: Eric Sosman wrote: Peteris Krumins wrote: Somebody always proposes this solution, but it's a poor one. Try it with fib(47), say, and tell us how long it takes. Hint: You won't need a high-precision timer. Yes, the solution has exponential complexity. But only needs the last two results [or even the last one even and the last one odd n] cached to reduce it to the same as the iterative version. Dec 14 '05 #11

 P: n/a mw*****@newsguy.com (Michael Wojcik) writes: In article , Eric Sosman writes: Peteris Krumins wrote: #include unsigned fib(unsigned n) { return n <= 2 ? 1 : fib(n - 1) + fib(n - 2); } int main(void) { printf("fib(17) is: %d\n", fib(17)); return 0; } Somebody always proposes this solution, but it's a poor one. Try it with fib(47), say, and tell us how long it takes. Hint: You won't need a high-precision timer. Well, there's always this one (with error checking left as an exercise for the reader): /*** prev2 and prev are the two immediately preceeding values in the series; prev2 is F(n-2) and prev is F(n). pos is the current position in the series. want is the position we're looking for. ***/ unsigned fib_cps(unsigned prev2, unsigned prev, unsigned pos, unsigned want) { if (want <= 2) return 1; if (pos == want) return prev2 + prev; return fib_r(prev, prev2 + prev, pos + 1, want); } unsigned fib(n) { return fib_cps(1, 1, 3, n); } (Of course you meant fib_cps rather than fib_r in the first function.) Just for my own enjoyment: unsigned fib3( unsigned n, unsigned a, unsigned b ){ return n == 0 ? b : fib3( n-1, b, a+b ); } unsigned fib( unsigned n ){ return fib3( n, 1, 0 ); } This definition yields fib(0) == 0, as the Fibonacci numbers are usually defined. Dec 14 '05 #12

### This discussion thread is closed

Replies have been disabled for this discussion.