Topic awaiting preservation: Finding Fibonacci numbers? (Page 1 of 1)

A bonus question on my homework is to modify one question (where we print out the first 50 Fibonacci #s) so that the user inputs a number through a form, the program checks to see if its a Fibonacci #, if it displays the form again and tells the user which is the closest Fib. #. If it does, it prints out the sequence starting with that number.

My only problem is the question doesn't say how many Fib #s to include. What I mean is, if it were say the first 50, it would be easy to check if the user inputted # is a Fib #. Without a limit there are infinite possibilities, right? Is there a way to tell if a number is a Fib. #?

The way I'm doing the program now, I'm asking users to input a number between two numbers (the first 65 Fib. numbers). I think check to see if its a Fib #. If it isn't, I load the first 65 Fib #s into an array, push the user defined number in it, sort it, check whether or not the one in front/behind is closest and print it out.

That's easy, but I'm not 100% sure if its correct.

Any ideas?

Jim

You should be able to just take the input, set that as the end of your loop, calculate the Fibonacci sequence (series?) up to that number, then have a test whether the last number you calculated was equal to the limit or less than. If it's less than, find out if it's closer than the next number.

Probably not the easiest/best/most efficient solution, but it should work.

LF

quote:

---

You should be able to just take the input, set that as the end of your loop, calculate the Fibonacci sequence (series?) up to that number...

---

Well, doing up to the n'th fibonacci number will give you numbers much greater than n. (For instance, the 10th fibonacci number is 55, so if you were given 55 as input, by going up to the 55th fibonacci number you'd be doing way more work than necessary.)

That might not have been what you were trying to say; I wouldn't be surprised if you had the same thing in mind that I do:

Jimmy, I think you're overcomplicating the solution. No sorting should be necessary. The nice thing about fibonacci numbers is that each one is greater than the one before. So simply calculate fibonacci numbers in an (otherwise infinite) loop until you get to a number which is greater than or equal to the number you were given as input. Then break from the loop.

Then, the last two numbers you calculated will be surrounding the input number. For instance, if the input was 50, then your loop would stop when it calculated 55, and 50 is between the previous fibonacci number (34) and the last one you calculated (55). So then you simply check which one is closer (in this case, 55 is closer).

The important thing to realize here is that you don't need to know ahead of time how long a loop will go for. You can make the loop's condition more complicated than just checking a counter variable, so that whether or not you break out of it is dependant on what it has calculated so far. (In this case, whether you break from the loop depends on whether you've calculated a number higher than the one given as input. Since fibonacci numbers go on to infinity, you're guaranteed that the loop will eventually stop.)


 

I liked this question so I programmed it. 36 easily readable lines of python code. Ever since I started writing scripts in python programming has become a whole lot more fun.

Following Slime's advice about storing the value of the previous fib number is the way to go. I used a variable for a counter, and an additional two registers. You can make due with only one register but you will have to compute the fib number more than once and that doesn't help anyone.

It is a nice math problem because you need to use two concepts, the fibonocci sequence, and you have to figure out how to find the closest of two numbers.Thanks for posting this question, if you have any questions with this I am sure many here could give you some more help if needed.

Dan @ Code Town

Since, the assignment isn't due for some time I put it off and went back to it two days ago with a fresh start. I definitely was making it more complicated then necessary.

My code looks something like this:

$number = 0;

$next_number = $number + 1;

$fib_number = $number + $next_number;



$f_number = $_POST['num']; //Number entered by user



	while($fib_number <= $f_number)

		{

			$number = $next_number;

			$next_number = $fib_number;

			$last_number = $fib_number; 

			$fib_number = $number + $next_number;

		}

			

			$next_fib_number = $fib_number;

So after that loop I'm left with three variables: $f_number, $last_number, and $next_fib_number. If $f_number equals $last_number the number is a Fibonacci #. If it isn't then I compare $f_number to $last_number & $next_fib_number. Which ever one it's closest to I display.

I don't know if its the best way to do it, but it works.

Thanks for all the help. I really appreciate it.

Jim

Actually, one question I have is how do I pass variables back to the same page? I'm using $_POST to pass variables. If the # the user enters on the original form isn't in the sequence I'm to display the message about which # is closest and then provide a form so the user can re-enter their #s. Should I still be using $_POST for this?

Thanks in advance.

Jim

post is fine. I presume you want to 're-pre-fill-out' the fields? just print a value attribute to them, and have the user resubmit the form.

Sorry about that. I was trying to say what Slime said, but I didn't word it very clearly I guess. Thanks for clarifying for me Slime.

LF