Closed Thread Icon

Topic awaiting preservation: Finding Fibonacci numbers? (Page 1 of 1) Pages that link to <a href="https://ozoneasylum.com/backlink?for=23726" title="Pages that link to Topic awaiting preservation: Finding Fibonacci numbers? (Page 1 of 1)" rel="nofollow" >Topic awaiting preservation: Finding Fibonacci numbers? <span class="small">(Page 1 of 1)</span>\

 
Jimmy
Nervous Wreck (II) Inmate

From: Alderaan
Insane since: Sep 2004

posted posted 10-20-2004 03:58

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

Lord_Fukutoku
Paranoid (IV) Inmate

From: Back in West Texas... How disappointing
Insane since: Jul 2002

posted posted 10-20-2004 17:29

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

Slime
Lunatic (VI) Mad Scientist

From: Massachusetts, USA
Insane since: Mar 2000

posted posted 10-20-2004 23:32
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.)


 

WarMage
Maniac (V) Mad Scientist

From: Rochester, New York, USA
Insane since: May 2000

posted posted 10-21-2004 05:42

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

Jimmy
Nervous Wreck (II) Inmate

From: Alderaan
Insane since: Sep 2004

posted posted 10-21-2004 19:25

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:

code:
$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

Jimmy
Nervous Wreck (II) Inmate

From: Alderaan
Insane since: Sep 2004

posted posted 10-21-2004 19:38

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

Tyberius Prime
Paranoid (IV) Mad Scientist with Finglongers

From: Germany
Insane since: Sep 2001

posted posted 10-21-2004 21:38

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.

Lord_Fukutoku
Paranoid (IV) Inmate

From: Back in West Texas... How disappointing
Insane since: Jul 2002

posted posted 10-21-2004 21:51

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

« BackwardsOnwards »

Show Forum Drop Down Menu