Thread: help with an algorithms View Single Post

## help with an algorithms

Hello math crew!

Here's the problem: http://www2.edc.org/makingmath/mathp...ins/trains.asp

just in case somebody doesn't want to click on the above link,

trains:
You can use rods of integer sizes to build "trains" that all share a common length. A "train of length 5" is a row of rods whose combined length is 5. Here are some examples:

Notice that the 1-2-2 train and the 2-1-2 train contain the same rods but are listed separately. If you use identical rods in a different order, this is a separate train.

* How many trains of length 5 are there?
* Come up with a formula for the number of trains of length n. (Assume you have rods of every possible integer length available.) Prove that your formula is correct.
* Come up with an algorithm that will generate all the trains of length n.

Now I solved this problem, at least I think I solved it.
A formula for the number of trains of length n will be
a=length of a train
h=how many trains of a given length
2^(a-2) + 2^(a-3) + 2^(a-4)+........+ 2^2 + 2^1 + 2^0 = h
if a > 3
I'm not truly sure, if this formula is right, it works for 4,5,6,7 and seems to work for every length above 7, it doesn't work for lengths 1,2,3 though,
Also I have a problem with an algorithm.
Can anyone help me make one, or at least give some clues ont "how to make a good algorithm?" (eventually you may post some good books on algorithms. I got some books in my eye on algorithms, however still have not enough money or time to read 'em)

thanks for all the help fellows,
 PhysOrg.com science news on PhysOrg.com >> Ants and carnivorous plants conspire for mutualistic feeding>> Forecast for Titan: Wild weather could be ahead>> Researchers stitch defects into the world's thinnest semiconductor