Winamp & Shoutcast Forums Computer programming / Algorithm related question
 User Name Remember Me? Password

 Thread Tools Search this Thread Display Modes
 21st May 2007, 21:46 #1 Triton4 Major Dude   Join Date: Feb 2003 Location: CA Posts: 1,307 Computer programming / Algorithm related question String of Digits ---------------- We have a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the string of digits. After all plus signs are inserted, evaluate the sum as usual. For example, consider the string "12" . With zero additions, we can achieve the number 12. If we insert one plus sign into the string, we get "1+2", which evaluates to 3. So, in that case, given "12", a minimum of 1 addition is required to get the number 3. As another example, consider "303" and a target sum of 6. The best stategy is not "3+0+3", but "3+03". You can do this because leading zeros do not change the result. Write an algorithm or flowchart for above problem. It should also give an error message if the sum is not logically possible in any way
 21st May 2007, 21:57 #2 zootm Forum King     Join Date: Jan 2002 Location: the nether reaches of bonnie scotland Posts: 13,375 This sounds suspiciously like something you're supposed to do yourself. Also the brute force approach isn't very difficult to work out.
 21st May 2007, 22:18 #3 k_rock923 \m/(Forum King)     Join Date: Jul 2003 Location: /bin/bash Posts: 7,850 Not difficult at all to brute force it. Never underestimate the bandwidth of a station wagon full of tapes hurtling down the highway.
 21st May 2007, 23:35 #4 dlinkwit27 has no CT(Forum King)     Join Date: Sep 2000 Posts: 13,235 Brute force will take exponentially longer with each digit added though.
 22nd May 2007, 01:10 #5 k_rock923 \m/(Forum King)     Join Date: Jul 2003 Location: /bin/bash Posts: 7,850 Well, yeah. But we're not doing his homework for him and if he's this lazy, he won't find a good solution, either. Never underestimate the bandwidth of a station wagon full of tapes hurtling down the highway.
 22nd May 2007, 03:18 #6 dlinkwit27 has no CT(Forum King)     Join Date: Sep 2000 Posts: 13,235 Tossing ideas out aren't the same as doing it for him though. He'd still have to code it. I've gotten plenty of HW help from this and other boards. Sometimes you just need a push and then the rest of the dominos fall almost by themselves. Anyways... To make it complete, the first thing I would do would be to see if the desired number is smaller than the sum of all the numbers summed together; i.e. don't ask for 9 if the sequence is 325. There is no way to get 9, in fact, the smallest sum of 325 is 10. Next, I'd make sure the number is larger than the sequence. With a large sequence this would be nearly a given, but again, don't ask for 500 with the 325 sequence, because clearly the largest "sum" for that sequence is 325 (with no "additions"). This would be my first and second step to attempt to ensure that the process is even possible. Off the top of my head I don't think you would get stuck in an infinite loop in either case, but this just makes the program better. As for a method other than the brute force method, I'm still thinking about this. This is an intriguing problem and I am actually trying it myself. /edit I see now that the problem is merely to design a flowchart or algorithm. Pretty simple to do with a brute force method. I may try to actually code this though.
 22nd May 2007, 09:36 #7 ujay Forum King     Join Date: Jul 2001 Location: London Posts: 6,072 It should also give an error message if the sum is not logically possible in any way. You should do this test first. Check the bounds as suggested by dlink and then use the 'casting out nines' technique to check whether a solution is possible. Note that this will not tell you if a solution actually exists. This is a particularly useful test where the data is presented as a string since you can use cyclic redundancy to establish the result.  Thinking about it some more you should check the bounds after this test, not before. UJ Last edited by ujay; 22nd May 2007 at 10:22.
 22nd May 2007, 15:44 #8 dlinkwit27 has no CT(Forum King)     Join Date: Sep 2000 Posts: 13,235 Also, if you are using a string, remember that '9' - '0' = 9 (and so on)
 22nd May 2007, 22:39 #9 xzxzzx Forum King     Join Date: Aug 2002 Posts: 7,254 I suspect you can't do much better than brute-force here, except for certain special cases, but I could be completely wrong... Freedom of speech is the basic freedom of humanity. When you've lost that, you've lost everything. 1\/\/4y 34|<\$p4y 1gp4y 33714y, 0d4y 0uy4y? | Roses are #FF0000; Violets are #0000FF; chown -R \${YOU} ~/base The DMCA. It really is that bad. : Count for your life.
 23rd May 2007, 18:39 #10 Triton4 Major Dude   Join Date: Feb 2003 Location: CA Posts: 1,307 Ok, I have done some code work in C++ for this problem. Can you check and see if this is ok: PHP Code: ``` #include  #include  class SimpleSums { private:     int sum;      public:     SimpleSums()     { }     SimpleSums(const char* digits, int sum)     {         char fres[256]={0};         if(MinSums(fres, digits, sum, 1))             cout<
 Winamp & Shoutcast Forums Computer programming / Algorithm related question
 User Name Remember Me? Password

 Thread Tools Search this Thread Search this Thread: Advanced Search Display Modes Linear Mode

 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 On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Tech Support Greatest Hits Winamp     Winamp Technical Support     Winamp Discussion     Winamp Wishlist     Winamp Bug Reports     Winamp for Android     Winamp Site Design Shoutcast     Shoutcast Technical Support     Shoutcast Discussions     Shoutcast For Business & Monetization     Shoutcast Site Design International Connection     International Connection     Русскоязычный форум (Russian)     Français: de l'aide pour les francophones (French)     Winamp Deutsch (German) Community Center     General Discussions     Breaking News     Music O'Rama     Games Center     Movies and Television     The Bitchlist Skinning and Design     Skinning Tips and Tricks     Classic Skins     Modern Skins     Arts and Design Developer Center     Winamp Development     NSIS Discussion         NSIS Translations Visualizations     AVS         AVS Presets         AVS Wishlist         AVS Troubleshooting     MilkDrop         MilkDrop Presets         MilkDrop Development         MilkDrop Feature Requests         MilkDrop Troubleshooting Forum

 -- Deutsch -- English (US) -- Polish -- Russian Winamp.com - Help - Archive - Top