--- Michael Chaney <[EMAIL PROTECTED]> wrote: > Here's an even better response from a friend of mine: > The parse tree representation suggests itself since it is inherently > recursive, which makes for easy building of larger solutions from > already computed smaller solutions (a hallmark of dynamic programming). > Note that building possible parse trees recursively (i.e., "top down") > is equivalent to brute-force enumeration. >
Yep. In an alternative solution, I used a recursive function to walk through all the possible combinations. (the source code turns out to be pretty short -- most of the other stuff is simply support code to handle fractions to make sure no rounding off occurs during the intermediate calculations). Also, it was written in python. > Btw, the solution for the problem stated is: 195 > I got the same solution as well (now that I got confirmation of my solution, I can apply at ita software ;^)) See my post at plug-misc about a week ago : http://lists.q-linux.com/pipermail/plug-misc/2001-November/001008.html My solution can also display an expression that can show you how each value in the result set could be generated. Also his solution used an arbitrary epsilon to handle possible rounding-off during the intermediate calculations involving division. My alternate solution used a data structure (a tuple which is built-in to python) to hold a pair of numbers to enable it represent fractions (integers just have 1 as their denominator) and make sure no rounding errors occurs -- I know that's probably overkill. Some solutions for the last 10 numbers (186-196): 186 : (((-((9 / -(-(-9 - 9) + 9)) - 9) * -(-9 - 9)) + 9) + 9) 187 : ((((-(-9 - 9) * 9) - 9) * -((-(-9 - 9) / -9) - 9)) / 9) 188 : ((((-(((-(9 / -9) - 9) - 9) / 9) + 9) + 9) * 9) + 9) 189 : (((((-(-9 - 9) * 9) + 9) * -((9 / -9) - 9)) - 9) / 9) 190 : (((-((((-(-9 - 9) * 9) + 9) + 9) * -9) + 9) / 9) + 9) 191 : (((((-(-9 - 9) * 9) + 9) * -((9 / -9) - 9)) + 9) / 9) 192 : ((-(((-(9 * -9) + 9) / (-(-9 - 9) + 9)) + 9) - 9) * -9) 193 : (-(((((-(-9 - 9) / -9) - 9) / -9) + 9) * (-9 - 9)) + 9) 194 : ((((-(9 / (-9 - 9)) + 9) + 9) * -((9 / -9) - 9)) + 9) 196 : (((((-(-(9 * -9) + 9) - 9) * (-9 - 9)) - 9) - 9) / 9) (there are some extraneous parentheses - they're just there to make sure there's no ambiguity between the order of operations) Cheers, Butch PS. This thread should really be moved to plug-misc :^) __________________________________________________ Do You Yahoo!? Send your FREE holiday greetings online! http://greetings.yahoo.com _ Philippine Linux Users Group. Web site and archives at http://plug.linux.org.ph To leave: send "unsubscribe" in the body to [EMAIL PROTECTED] To subscribe to the Linux Newbies' List: send "subscribe" in the body to [EMAIL PROTECTED]
