Thread: Fibonacci Sequence

  1. #1
    Registered User Dogmasur's Avatar
    Join Date
    Jul 2008
    Posts
    72

    Fibonacci Sequence

    My next dive into attempting to write a program deals with a Fibonacci-se-quence. I have started an outline to portray the ideas of how I think the flow of code should go to produce this program and have come across some questions.

    I want my program to query the user for four separate integers. The first two are the beginning numbers of the sequence and the last two will indicate the starting point and ending point of the sequence.

    My question is: if the user decides to start farther down the line, instead of the beginning number, then how should I put this together? Should I write a function that will work through the computations ( beginning from the first ) which will keep count of each loop through the computations and then return when it has reached the proper beginning line or should I try to compute an algorithm that will do the same and begin printing at said starting point.

    For example:

    the user inputs 1,1 for the sequence
    the user wants the starting point for output to be 3 and end at 9.

    the output should read:

    3: 2
    4: 3
    5: 5
    6: 8
    7: 13
    8: 21
    9: 34

    I am also going to include the ratio of the current number of the sequence to the previous, but that didn't seem necessarily relevant to my question.

    Sorry if this was poorly written. I am kind of scrambling through my thoughts here.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Dogmasur View Post
    My question is: if the user decides to start farther down the line, instead of the beginning number, then how should I put this together? Should I write a function that will work through the computations ( beginning from the first ) which will keep count of each loop through the computations and then return when it has reached the proper beginning line or should I try to compute an algorithm that will do the same and begin printing at said starting point.
    Why not try both and see which one you like the best? (Note, however, that functions cannot return more than one thing, and you're going to need two (previous) numbers to go forward. This will most likely require (dum-dum-duuum) pointers (thunder crash, spooky chord).)

  3. #3
    Registered User Dogmasur's Avatar
    Join Date
    Jul 2008
    Posts
    72
    Would it be feasible to compute all the lines up to the ending point, store them each in a string and then print those that are within the scope of what the user wants to see? I only ask, because I am most definitely not ready to enter the world of efficient coding...meaning use of processor resources, time for opera-tion and use of available memory...but would like to begin writing at least some-what discriminately towards making the best use of these processes.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You ... could, I suppose. It's a bit tricky, in that you have to know ahead of time (that is, before the user types anything at all) how long the string is going to be, and you don't. Otherwise, you go back to getting memory on-the-fly. (Same thing for trying to store all the answers in an array -- you won't know when you compile the program how big your array is going to need to be.)

    PS: I'm guessing you type your posts in a word processing program before posting? Not a bad idea, but could you maybe turn off auto-hy-phen-ate?

  5. #5
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    The latter, because it allows you to put all the code that deals with actually calculating the Fibonacci algorithm in one place. This makes it easy for you to change your implementation of the algorithm, if you find a better way later.

    In general you should try to separate number crunching and interface, as much as possible.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  6. #6
    Registered User Dogmasur's Avatar
    Join Date
    Jul 2008
    Posts
    72
    Quote Originally Posted by tabstop View Post
    You ... could, I suppose. It's a bit tricky, in that you have to know ahead of time (that is, before the user types anything at all) how long the string is going to be, and you don't. Otherwise, you go back to getting memory on-the-fly. (Same thing for trying to store all the answers in an array -- you won't know when you compile the program how big your array is going to need to be.)

    PS: I'm guessing you type your posts in a word processing program before posting? Not a bad idea, but could you maybe turn off auto-hy-phen-ate?
    Sorry, I'll stop hyphenating. I'm not using a word processor. I was just hyphenating within the window given on this forum. I should preview my posts before posting. Thx for the heads up.

    I keep hearing scanf is bad and using getchar () to wait for an enter key press is bad. Is scanf safe to use here, since I am receiving a simple integer and how do I properly code to wait for a press of the enter key?
    Last edited by Dogmasur; 08-07-2008 at 09:16 PM. Reason: typos; told you I wasn't using a word processor

  7. #7
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by Dogmasur View Post
    Would it be feasible to compute all the lines up to the ending point, store them each in a string and then print those that are within the scope of what the user wants to see? I only ask, because I am most definitely not ready to enter the world of efficient coding...meaning use of processor resources, time for opera-tion and use of available memory...but would like to begin writing at least some-what discriminately towards making the best use of these processes.
    In addition to what tabstop said, this will make your program memory grow needlessly, when all you really ever need to store are the last two digits. It would also limit the maximum number of digits you can calculate up to.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  8. #8
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by Dogmasur View Post
    I keep hearing scanf is bad and using getchar () to wait for an enter key press is bad. Is scanf safe to use here, since I am receiving a simple integer and how do I properly code to wait for a press of the enter key?
    scanf is only bad when you use %s without a width specifier as present it "%80s". %i and the others are fine.

    getchar() is not bad, as far as I know, but using getchar and scanf together can be confusing, since scanf will usually leaves trailing whitespace (and anything else really) in the buffer, and the next getchar call will pick up what's left of the buffer, before going on to the next line.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  9. #9
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    Quote Originally Posted by Dogmasur View Post
    Sorry, I'll stop hyphenating. I'm not using a word processor. I was just hyphenating within the window given on this forum. I should preview my posts before posting. Thx for the heads up.

    I keep hearing scanf is bad and using getchar () to wait for an enter key press is bad. Is scanf safe to use here, since I am receiving a simple integer and how do I properly code to wait for a press of the enter key?
    I would say that when you are working on your own small projects, like this, that using scanf and other 'unsafe' things are ok. But it is good to be aware of their limitations if you tackle something larger.

    As for the fibonacci sequence, I like the recursive solution because of it's simplicity and elegance. Learning a recursive approach is valuable even if it is not always the most optimal performance wise.

  10. #10
    Registered User Dogmasur's Avatar
    Join Date
    Jul 2008
    Posts
    72
    I'm going to try to put this together with what knowledge I have and can gather from some "light" reading and then put it out for you all to laugh ( I mean comment) at.



    Thx all.

  11. #11
    Registered User
    Join Date
    Aug 2008
    Posts
    3

    Talking

    simple, just include math.h , and than:

    result = (1/sqrt(5))*((1+sqrt(5))/2)^n-(1/sqrt(5))*((1-sqrt(5))/2)^n ;

    of course n is the variable...

    i've learned this, this week in college.

  12. #12
    Registered User Dogmasur's Avatar
    Join Date
    Jul 2008
    Posts
    72
    Quote Originally Posted by PkD View Post
    simple, just include math.h , and than:

    result = (1/sqrt(5))*((1+sqrt(5))/2)^n-(1/sqrt(5))*((1-sqrt(5))/2)^n ;

    of course n is the variable...

    i've learned this, this week in college.
    I was going to go with a much simpler a+b=c, where I would simply redefine the variables with each pass through my loop.

    What you're getting into is Binet's formula, which might be a bit excessive for what I need. I have some understanding of mathematics and Fibonacci recursion's similarity to the generating polynomial of the recursion. I was asking more about how to code my program than how to compute the variables involved. Sorry if I wasn't clear and thanks for your input.

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    An adaptation of the formula may help you get to the start point faster, but once you are there, the use of such a formula would only slow you down, since simple addition of the previous two terms would be much faster.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User Dogmasur's Avatar
    Join Date
    Jul 2008
    Posts
    72
    Quote Originally Posted by PkD View Post
    simple, just include math.h , and than:

    result = (1/sqrt(5))*((1+sqrt(5))/2)^n-(1/sqrt(5))*((1-sqrt(5))/2)^n ;

    of course n is the variable...

    i've learned this, this week in college.
    I reread through the posts and thought my reply to you sounded snooty. I just wanted to apologize for that and let you know it wasn't meant to sound rude.

  15. #15
    Registered User
    Join Date
    Aug 2008
    Posts
    3

    Thumbs up

    It 's ok.

    I've just posted the Binet's formula because it's a curiosity, of course it slow down the PC , but if the user whats a number very big,maybe is it better use the formula? or 0+1+1+2+3+5+8+13+21+... ? .

    thats it!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. fibonacci sequence
    By cph in forum C Programming
    Replies: 57
    Last Post: 04-30-2009, 07:17 AM
  2. Fibonacci sequence
    By MuffanMan123 in forum C++ Programming
    Replies: 6
    Last Post: 02-26-2008, 09:15 AM
  3. Immediate programming help! Please!
    By xMEGANx in forum C++ Programming
    Replies: 6
    Last Post: 02-20-2008, 12:52 PM
  4. Fibonacci sequence output statement
    By chocha7 in forum C++ Programming
    Replies: 10
    Last Post: 11-18-2004, 11:04 PM
  5. Fibonacci sequence
    By girliegti in forum C++ Programming
    Replies: 8
    Last Post: 09-30-2003, 10:40 PM