
#1
Nov2005, 06:52 PM

P: 214

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 122 train and the 212 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^(a2) + 2^(a3) + 2^(a4)+........+ 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, 



#2
Nov2005, 09:04 PM

Sci Advisor
HW Helper
P: 2,589

The formula can be made much simpler. Write out a list of the h values for a = 1, 2, 3, 4, 5, 6, 7, .... There's a very obvious pattern. The idea for the algorithm should follow from the way you think about solving the first problem. Here's a hint: how do you figure out how many ways you can build an ntrain if you know how many ways you can build an n1train, and n2train, ..., a 1train, (and a 0train)? Everything about this problem screams "recursion" so your algorithm should be recursive. You should probably end up using some sort of "recursive thinking" to solve the first problem, and you can apply this recursive thinking to figure out your algorithm.



Register to reply 
Related Discussions  
Need help with Algorithms  Engineering, Comp Sci, & Technology Homework  0  
Discrete algorithms.  Calculus & Beyond Homework  1  
need help in factoring algorithms  Linear & Abstract Algebra  13  
course on Data structures and algorithms  Computing & Technology  14  
resources on proving algorithms correct?  General Math  3 