Visit Jeremy's Blog.
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org recursion pitfalls
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 11-23-2009, 09:06 AM #1 icecubeflower Member   Registered: Mar 2008 Location: USA Distribution: Slackware 13.1 Posts: 304 Rep: recursion pitfalls Anybody do topcoder? I'm a rookie. I competed once and solved the 250 point problem. Usually the 500 and 750 point problems are over my head. So now I'm doing practice problems and I'm studying other people's solutions. Anyway worked on a practice problem today. It was SRM 249, DIV 1. Here is the problem statement: Code: ```Problem Statement **** Your restaurant has numTables tables to seat customers. The tables are all arranged in a line. If a large party of customers comes in, a group of adjacent tables will be used. Which group of tables is entirely up to the customer. Since you cannot predict this, assume all possible choices occur with equal probability. What you can predict is the size of each group of customers that arrives. Element i of probs gives the probability, in percent, that an entering party will need i+1 tables. Assuming nobody leaves, return the expected number of tables you will use before a party must be turned away. This only occurs if there is no place to seat them. Definition **** Class: TableSeating Method: getExpected Parameters: int, vector Returns: double Method signature: double getExpected(int numTables, vector probs) (be sure your method is public) **** Notes - Return values must be accurate to 1e-9, relative or absolute. Constraints - numTables will be between 1 and 12 inclusive. - probs will contain between 1 and 12 elements inclusive. - Each element of probs will be between 0 and 100 inclusive. - The elements of probs will sum to 100. Examples 0) **** 4 {100} Returns: 4.0 Since every party needs only 1 table, you will always fill the restaurant before turning someone away. 1) **** 4 {0,100} Returns: 3.3333333333333335 Now every party wants 2 tables. One third of the time, the first party will choose the middle 2 tables blocking anyone else from being seated. Two thirds of the time, the first party will choose 2 tables on the end allowing the restaurant to become full. Thus, the returned value is (1/3)*2 + (2/3)*4 = 10/3. 2) **** 5 {0,0,0,0,0,50,50} Returns: 0.0 You have 5 tables, but every party needs 6 or 7 tables. 3) **** 12 {9,9,9,9,9,9,9,9,9,9,10} Returns: 7.871087929710551 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.``` Here is my solution, it uses recursion: Code: ```#include #include class TableSeating { public: double getExpected(int numTables, std::vector probs); private: void Cruncher(int numTables, std::vector probs, double hotpotato_odds); //recursive thingy int *restaurant; //tables in the restaurant double *odds; //collects odds (0.x/1) for each number of tables filled (0.0,0.0,0.25,0.75) or something int level; //delete this int numfilled; }; int main() { std::vector probs; int numTables; TableSeating funstuff; probs.push_back(9); probs.push_back(9); probs.push_back(9); probs.push_back(9); probs.push_back(9); probs.push_back(9); probs.push_back(9); probs.push_back(9); probs.push_back(9); probs.push_back(9); probs.push_back(10); numTables=12; std::cerr<<"Expected number of filled tables="< probs) { int ix; double hotpotato_odds; //collects current odds, pass recursively and restore double returner=0.0; restaurant=new int[numTables]; odds=new double[numTables+1]; for(ix=0;ix probs, double hotpotato_odds) { int ir,ix,ij,iz; bool fit; int numfits; double oldodds; //go through each element of probs, try all seating arrangements for(ir=0;ir0) //do it all again now that we have new hotpotato_odds, unless there were no fits { for(ix=0;ix
 11-24-2009, 01:57 AM #2 smeezekitty Senior Member   Registered: Sep 2009 Location: Washington U.S. Distribution: M\$ Windows / Debian / Ubuntu / DSL / many others Posts: 2,339 Rep: WTF are you talking about? i am heading off to google it!
 11-24-2009, 09:06 AM #3 neonsignal Senior Member   Registered: Jan 2005 Location: Melbourne, Australia Distribution: Debian Stretch (Fluxbox WM) Posts: 1,389 Blog Entries: 52 Rep: The recursion is fine, but as you say, takes too long to complete. However, it can be sped up. The main thing to notice is that even with 12 tables, there are only 4096 arrangements (2^12) - either a table is occupied or it isn't. For any given arrangement (ie, some tables already occupied), it is possible to calculate how many more parties can arrive (on average), ie, there is only one answer for each arrangement. So as the program recurses through the possibilities (starting with no tables occupied), it will often reach arrangements that have already been seen. If it keeps a cache of these calculations, this can be used to 'snip' later (matching) branches of the recursion without recursing all the way to the bottom. A possible solution would then be something like this: Code: ```// includes #include #include #include #include typedef std::vector Probs; // table seating class class TableSeating { public: double getExpected(int numTables, Probs probs); private: double calculate(unsigned int tableSet); private: Probs probs; int n; double *pCache; }; // set up parameters and calculate solution double TableSeating::getExpected(int numTables, Probs probs0) { // initialize constants n = numTables; probs = probs0; // initialize cache pCache = new double[1<::quiet_NaN(); // calculate average, starting with empty set of tables double average = calculate(0); // remove cache delete[] pCache; // return result return average; } // recursively calculate average number of patrons double TableSeating::calculate(unsigned int tableSet) { // if already calculated, then return if (!std::isnan(pCache[tableSet])) return pCache[tableSet]; // for each of the party sizes double average = 0; for (size_t iProb = 0; iProb < probs.size(); ++iProb) { // for each offset position double sum = 0.; unsigned int nSum = 0; for (size_t iOff = 0; iOff+iProb < n; ++iOff) { // allocate tables to the party unsigned int party = (1<
 11-24-2009, 09:48 AM #4 icecubeflower Member   Registered: Mar 2008 Location: USA Distribution: Slackware 13.1 Posts: 304 Original Poster Rep: Thx, neosignal. I'm studying your post. Also I'm studying another guy's solution. He does it in 8 lines. It's C++ but I can't read the syntax, I'm trying to get help in another thread. He didn't use recursion but I think he might have done something similar with nested for loops.
 11-24-2009, 04:40 PM #5 neonsignal Senior Member   Registered: Jan 2005 Location: Melbourne, Australia Distribution: Debian Stretch (Fluxbox WM) Posts: 1,389 Blog Entries: 52 Rep: True, you can get rid of the recursion by starting at the end of the cache and working backwards (because the sets at the end of the cache will always recurse to sets past that point). The code above then becomes something like this (the outer loop replacing the recursion): Code: ```// includes #include #include typedef std::vector Probs; // table seating class class TableSeating { public: double getExpected(int numTables, Probs probs); }; // calculate average number of patrons double TableSeating::getExpected(int numTables, Probs probs) { // initialize cache double *pCache = new double[1<
 11-24-2009, 06:33 PM #6 icecubeflower Member   Registered: Mar 2008 Location: USA Distribution: Slackware 13.1 Posts: 304 Original Poster Rep: Wow you really put a lot effort into illustrating this, thx.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post easuter Programming 11 07-21-2008 03:14 AM DJOtaku Linux - Software 1 02-05-2008 07:42 PM Earl Parker II Slackware 12 08-17-2004 02:49 AM tracedroute Slackware - Installation 6 05-09-2004 04:54 PM frizzo Linux - Laptop and Netbook 2 01-22-2004 08:57 AM

LinuxQuestions.org

All times are GMT -5. The time now is 01:26 PM.

 Contact Us - Advertising Info - Rules - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -