Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fibonacci sequence

  1. Jun 4, 2012 #1
    My program needs to prompt the user to input a number, and using that number, I tell them what number in the Fibonacci sequence their input corresponds to.
    So the Fibonacci sequence is 0 1 1 2 3 5 8 13
    So if they input the number 6, the program will return "5" as the number in the sequence.
    Anyone have any ideas how I would do this? I need a loop for it, I'm sure, and I was trying the "for" loop, but I can't figure out how to just give them the single number in the sequence, and not the whole sequence up to that number.

    Thanks.
     
  2. jcsd
  3. Jun 4, 2012 #2

    rcgldr

    User Avatar
    Homework Helper

    You can calculate the entire sequence, but only output a single number. You don't need to save all the numbers in the sequence either, just the last two numbers of the sequence.
     
  4. Jun 4, 2012 #3
    why don't you post the code that you've got so far? I would be a lot easier to help you that way.
     
  5. Jun 4, 2012 #4

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    If you write a recursive function to calculate it, you don't need to "remember" anything explicitly. The process of carrying out the recursion does the "remembering" for you. YOu don't need any loops, either.

    For example a recursive function to calculate factorials (warning - untested!) could be
    Code (Text):

    int fact(int i)
    {
       if (i < 1) return 1;
       else return i*fact(i-1);
    }
     
    and then your main program could just do
    Code (Text):

    int n;
    cin >> n;
    cout << fact(n);
     
     
  6. Jun 5, 2012 #5
    What language are you programming in? If you've got the sequence, then there should be a way of simply indexing the last number in the sequence and displaying that.
     
  7. Jun 5, 2012 #6
    $$\begin{bmatrix}0&1\end{bmatrix} \cdot
    \begin{bmatrix}1&1\\1&0\end{bmatrix} ^ n \cdot
    \begin{bmatrix}0\\1\end{bmatrix}$$
     
  8. Jun 5, 2012 #7
    I'm using C. How do I index the last number in the sequence? I can get the sequence to show up to the number they put in, but I don't know how to isolate that number.
     
  9. Jun 5, 2012 #8
    How are you creating the sequence? Can you post the code?
     
  10. Jun 5, 2012 #9
    #include<stdio.h>

    main()
    {
    int n, fib1 = 0, fib2 = 1, fib, c;

    printf("Enter the number of terms\n");
    scanf("%d",&n);

    printf("First %d terms of Fibonacci series are: ",n);

    for ( c = 0 ; c < n ; c++ )
    {
    if ( c <= 1 )
    fib = c;
    else
    {
    fib = fib1 + fib2;
    fib1 = fib2;
    fib2 = fib;
    }
    printf("%d ", fib);
    }

    return 0;
    }
     
  11. Jun 5, 2012 #10
    Ah, OK. It looks as though you are writing out the answer for every iteration. Try moving the printf statement outside the loop, as shown in the amended code above
     
  12. Jun 5, 2012 #11
    Thanks a lot. I can't believe that was so easy. I'm trying my best on this programming stuff and it's driving me nuts. I'm going to fail, but I need to make at least a D to get reimbursed so I don't lose all of that money.

    Can you help me with another one? I have to make a program where if the user types in, for example, 12345, the program prints out this...
    12345
    2345
    345
    45
    5

    I don't even know where to begin with this one.

    Thanks.
     
  13. Jun 6, 2012 #12
    Ah. Now you're entering 'blind leading the blind' country. I know how to do it algorithmically, but I haven't touched C programming for so long that we used to call it Alpha. I tend to use much higher-level languages. Consequently, all the messy, low-level defining memory stuff is detail that I no longer even know, or care, about. Do you have to use C or can you use something slightly more friendly, such as C++, C# or Basic?

    A rough outline for C would be something like ...

    Code (Text):
    sin = <get user input>
    int n
    int k

    n = strlen(s)
    char sout[n+1]

    for (k = n ; k>0 ; k--){       // starting with the full string and working down to 1 character
       strncpy(sin,sout,k)        // copy k characters into sout
       sout[k+1]='\0'              // and terminate with the null character
       printf("countdown: %d",sout)   // print out the reduced string
    }
    But, ... you would need to get the loop format correct and ensure that the size of sout allowed for the '0' string terminator. Note that it could probably also have been done by simply setting sin[k+1] to be the null character and forgetting about strncpy, or a myriad of other ways that regular C users could tell you about. A while loop would be a nice counterpoint to the for loop.
     
  14. Jun 6, 2012 #13
    we do not solve homework around here...
    you need to start,
    take a shot at it,
    post the code
    explain what it is you can't figure out
    etc.

    so, I will spell out an algorithm, here, that you can follow...which is actually more work than writing the program :-) ...oh well, it's either that or not post at all.

    basically

    you have to read the string
    then
    knowing that every string ends with the null character '\0'
    you can have two nested while loops
    the outer one keeps increasing the index of the starting character
    the inner one prints from such index and until the character is the null character

    so, here is an idea for you to proceed

    first write a little program that reads an input from the screen
    and using a while loop (you will need a counter variable as index), writes it back out to the screen, one character at a time and without going beyond the terminating null character
    can you do that?

    then write an inner while loop (you will need another counter variable)
    that writes one character at a time, but starting from the value of the index of the outer loop
    again, it does not go beyond the null character.

    you will need to get a bit tricky when using or not using "\n" in your print statements to create the desired output...

    this algorithm does not use any of the string functions (no need to include "string.h")

    setting the counters and the two nested while loops, printing, etc. is only 9 lines
    the entire program, variable declaration, and input reading 20 lines.

    you can do it! ...ready, set, go!
     
  15. Jun 6, 2012 #14
    I know. I don't know where I implied I was looking for a solution.
    I can't start on a program I don't know where to begin with. I don't know what could possibly replicate what the program is supposed to do.

    I just started programming a few weeks ago. Before that I have done nothing in my life that is remotely close to this, so a lot of the terminology you're using is alien to me.
     
  16. Jun 6, 2012 #15

    rcgldr

    User Avatar
    Homework Helper

    Where to begin ... how about a program that prints out what the user types in. The program would read a line of text and output a line of text, or the program would read a number and output the number. (You didn't specify if the 12345 could be any letters or just a number.)
     
  17. Jun 6, 2012 #16

    jtbell

    User Avatar

    Staff: Mentor

    Does this have to work for any character string (which could include letters and punctuation marks), or does it just have to work for integers? If it's just integers, is it restricted to integers that you can store in a single variable, or can they be arbitrarily long (which would probably have to use strings)?
     
  18. Jun 6, 2012 #17
    Ok sorry for the lack of information, and sorry if I sounded like a jerk in my last post. I don't like the way I said that. But anyway, I got some more information from my teacher, and he helped me a little bit, and the program asks the user to input a number between 1 and 32767 and it will return their answer like this...

    *****
    ****
    ***
    **
    *

    So if they input 32766, it will give them...

    32766
    2766
    766
    66
    6

    And if they input less than 5 numbers, such as 766, it will give them...

    00766
    0766
    766
    76
    6

    Here's what I got so far.

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

    int main()
    {
    int num;
    int d1, d2, d3, d4, d5;
    printf("Enter a number between 1 and 32767: ");
    scanf("%d", &num);
    d1 = num / 10000;
    d2 = (num / 1000) %10;
    d3 = (num / 100) %10;
    d4 = (num / 10) %10;
    d5 = (num % 10);

    printf("%d\n %d\n %d\n %d\n %d\n", &d1, &d2, &d3, &d4, &d5);
    return 0;
    }

    It's producing this sequence when I type in, for instance, 32767...

    2993528
    2993747
    2994283
    2993278
    2997325

    So they're the wrong numbers, with too many digits, and it's not getting smaller.

    Thanks.
     
  19. Jun 6, 2012 #18
    Ok I already see a problem. I put the & signs in the printf command.
    It seems like it's working. 3 spaces are supposed to be between the digits.

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

    int main()
    {
    int num;
    int d1, d2, d3, d4, d5;
    printf("Enter a number between 1 and 32767: ");
    scanf("%d", &num);
    d1 = num / 10000;
    d2 = (num / 1000) %10;
    d3 = (num / 100) %10;
    d4 = (num / 10) %10;
    d5 = (num % 10);

    printf("%d %d %d %d %d\n", d1, d2, d3, d4, d5);
    printf("%d %d %d %d\n", d2, d3, d4, d5);
    printf("%d %d %d\n", d3, d4, d5);
    printf("%d %d\n", d4, d5);
    printf("%d", d5);

    return 0;
    }

    I think I'm supposed to separate the first part from the second part in two different functions. Like, for example, the part where the printing is done should be in a second function. I'm not sure how to do that. Do I like define the function at the top and then use that same definition after the first function or something?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook