C/C++ Help
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
 
User Name:
Password:
Remember me
 
Go Back   Dev Articles Community ForumsProgrammingC/C++ Help

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Display Modes
 
Unread Dev Articles Community Forums Sponsor:
  #1  
Old September 28th, 2005, 02:52 PM
Cminus Cminus is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Sep 2005
Posts: 3 Cminus User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 h 4 m 6 sec
Reputation Power: 0
Question 2 New To have a Clue

I am a complete novice in C++ as this is my first programming class ever. I am completely stuck on this problem:

Develop a progrm which displays all possible ways to break up a $100 bill. It should be formatted as shown:

No fifity twenty ten five two one
*** *** ***** *** *** *** ***
1 1 1 2 1 2 1


The example shows these add up to 100.

Print out the total number of possible combinations.




OK, I'm not asking for someone to write this, but I need some direction. Our prof is under the impression that self-learning is the way to teach. I've never seen an example program that prints out in columns like he's asking. Would I use a "for" or "if" or "while" loop or "else"? I really have no clue where to start.
I can understand the logic that it should start by printing 2 fifties, then next line 1 fifty, 2 twenties, 1 ten...or am I looking at that the wrong way? ANY help would be appreciated. It would be a lot easier if the prof actually explained this stuff. Thanks.

Reply With Quote
  #2  
Old September 28th, 2005, 03:39 PM
Itsacon's Avatar
Itsacon Itsacon is offline
Command Line Warrior
Click here for more information
 
Join Date: Aug 2004
Location: Sector ZZ9 Plural Z Alpha
Posts: 995 Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)  Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2
Time spent in forums: 6 Days 13 h 57 m 35 sec
Reputation Power: 5
Send a message via ICQ to Itsacon
Printing in columns is easy using the printf() statement. You can specify the minimum length of a variable printed by adding a number between the percent sign (%) and the type (d for an integer, f for a float, etc).
The following example will print all numbers from 0 to 24 in a 5 by 5 square, where every number takes up 2 digits, with one digit in between:
cpp Code:
Original - cpp Code
  1. #include <stdio.h>
  2.  
  3. int main(void)
  4. {
  5.     int i;
  6.     for(i = 0; i < 25; i += 5)
  7.         printf(" %2d %2d %2d %2d %2d \n", i, i+1, i+2, i+3, i+4);
  8.  
  9.     return 0;
  10. }


As for the assignment, the best way to do this is write a recursive function, that takes two arguments, a value and a denomination,
The function should go through all possible amounts that can be made with that denomination specified, and call itself again, with the remaining value and the next lower denomination. Unless denomination is 1, in which case the current combination should be printed.

I know this explanation can be a bit fuzzy if you don't know what recursion is, but in that case, it would be a good thing to go to your teacher and ask him to explain recursion a bit.

Hope this gets you on your way
__________________
This is my code. Is it not nifty?

"The biggest problem encountered while trying to design a system that was completely foolproof, was, that people tended to underestimate the ingenuity of complete fools."
---Douglas Adams


Join the Itsacon fanclub!    
Zero Tolerance: Spammers banned so far: 275

Last edited by Itsacon : September 28th, 2005 at 04:07 PM.

Reply With Quote
  #3  
Old September 28th, 2005, 03:55 PM
Itsacon's Avatar
Itsacon Itsacon is offline
Command Line Warrior
Click here for more information
 
Join Date: Aug 2004
Location: Sector ZZ9 Plural Z Alpha
Posts: 995 Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)  Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2
Time spent in forums: 6 Days 13 h 57 m 35 sec
Reputation Power: 5
Send a message via ICQ to Itsacon
Ok, I've got a working version, so if you're really stuck, just say.

Be aware that there are 4562 different ways to break up that 100 dollar bill...

Reply With Quote
  #4  
Old September 28th, 2005, 04:10 PM
Cminus Cminus is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Sep 2005
Posts: 3 Cminus User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 h 4 m 6 sec
Reputation Power: 0
Please do post your version. I would like to see if what you have is anything similar to what we have been taught. I've been searching through books for days trying to figure this one out. That number seems awful high for where we are...and I have never heard of recursion, so I'll have to look it up. Thanks for the advice.







Quote:
Originally Posted by Itsacon
Ok, I've got a working version, so if you're really stuck, just say.

Be aware that there are 4562 different ways to break up that 100 dollar bill...

Reply With Quote
  #5  
Old September 29th, 2005, 12:37 AM
Itsacon's Avatar
Itsacon Itsacon is offline
Command Line Warrior
Click here for more information
 
Join Date: Aug 2004
Location: Sector ZZ9 Plural Z Alpha
Posts: 995 Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)  Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2
Time spent in forums: 6 Days 13 h 57 m 35 sec
Reputation Power: 5
Send a message via ICQ to Itsacon
Recursion is, simply put, breaking up a problem into smaller, decreasing steps.

For instance, calculating x! (a mathematical expressiong meaning x * x-1 * x-2 *..... * 2 * 1) can easily be done by recursion:
cpp Code:
Original - cpp Code
  1. int fac(int x)
  2. {
  3.     if(x == 1)
  4.         return 1;
  5.     else
  6.         return x * fac(x - 1);
  7. }


I'll post my solution later today, if you still can't figure it out.

Reply With Quote
  #6  
Old September 29th, 2005, 12:12 PM
Itsacon's Avatar
Itsacon Itsacon is offline
Command Line Warrior
Click here for more information
 
Join Date: Aug 2004
Location: Sector ZZ9 Plural Z Alpha
Posts: 995 Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)  Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2
Time spent in forums: 6 Days 13 h 57 m 35 sec
Reputation Power: 5
Send a message via ICQ to Itsacon
Post Solution

Ok, here's my solution.

Expanded it a bit to optionally take the amount from the command line, but when called without parameters, it defaults to 100 dollars.

See if you can figure out what makes it tick.
cpp Code:
Original - cpp Code
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // global variable to store the set we're currently working on
  5. int amounts[6];
  6.  
  7. // recursive function, takes a value, a bill to start at, and the number of options so far.
  8. int calculate_options(int value, int denom, int counter)
  9. {
  10.     // set possible denominations
  11.     static int vals[] = {1, 2, 5, 10, 20, 50};
  12.    
  13.     // at the 1 dollar bill yet?
  14.     if(denom > 0)      // no, for all the possible amounts the current bill fits in the current value, get all possible sub-amounts.
  15.     {
  16.         for(amounts[denom] = 0; value - amounts[denom] * vals[denom] >= 0; amounts[denom]++)
  17.             counter = calculate_options((value - amounts[denom] * vals[denom]), (denom - 1), counter);
  18.     }
  19.     else                // yes, output current set of values
  20.     {
  21.         // another option completed, increment counter
  22.         counter++;
  23.         // print the current set of bills
  24.         printf(" %2d * %5d * %6d * %3d * %4d * %3d * %3d \n", counter, amounts[5], amounts[4], amounts[3], amounts[2], amounts[1], value);
  25.     }
  26.     return counter;
  27. }
  28.  
  29. // main, takes arguments to read the command line
  30. int main(int argc, char **argv)
  31. {
  32.     // declarations
  33.     int bill, counter;
  34.  
  35.     // see if there's a value on command line
  36.     if(argc == 1)   // no, default to 100
  37.         bill = 100;
  38.     else            // yes, read value
  39.         bill = atoi(argv[1]);
  40.  
  41.     // print table header
  42.     printf(" No * fifty * twenty * ten * five * two * one \n");
  43.     printf("**********************************************\n");
  44.  
  45.     // call function
  46.     counter = calculate_options(bill, 5, 0);
  47.  
  48.     // print number of possibilities
  49.     printf("There are %d different ways to break up %d dollars\n", counter, bill);
  50.  
  51.     // exit
  52.     return 0;
  53. }

Reply With Quote
  #7  
Old September 29th, 2005, 01:43 PM
MadCowDzz's Avatar
MadCowDzz MadCowDzz is offline
I'm Internet Famous
Dev Articles Frequenter (2500 - 2999 posts)
 
Join Date: Jan 2003
Location: Toronto, Canada
Posts: 2,890 MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level) 
Time spent in forums: 1 Week 16 h 14 m 9 sec
Reputation Power: 8
Now do it for Canada... we do'nt have $1 or $2 bills.

Recursion, simple-r put... a function is recursive when it calls itself.
Keep in mind, there needs to be a way out... as in Itsacon's code, IF (something) call_myself ELSE print something
Otherwise you end up in an infinite loop.

Reply With Quote
  #8  
Old September 29th, 2005, 02:19 PM
Itsacon's Avatar
Itsacon Itsacon is offline
Command Line Warrior
Click here for more information
 
Join Date: Aug 2004
Location: Sector ZZ9 Plural Z Alpha
Posts: 995 Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)Itsacon User rank is Lance Corporal (50 - 100 Reputation Level)  Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2Folding Points: 802356 Folding Title: Super Ultimate Folder - Level 2
Time spent in forums: 6 Days 13 h 57 m 35 sec
Reputation Power: 5
Send a message via ICQ to Itsacon
I bet you have 1 and 2 dollar coins...
Same here in europe... Only we call them euros....

Reply With Quote
  #9  
Old September 29th, 2005, 03:58 PM
Cminus Cminus is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Sep 2005
Posts: 3 Cminus User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 h 4 m 6 sec
Reputation Power: 0
Thanks for the help and explanations! I will go through it with a fine-toothed comb. It looks like we haven't gone over some of this yet. I will discuss this with the prof. Thanks.

Reply With Quote
  #10  
Old September 29th, 2005, 04:26 PM
Geo.Garnett's Avatar
Geo.Garnett Geo.Garnett is offline
Registered Loser
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Jul 2005
Location: Retardation Nation...
Posts: 347 Geo.Garnett User rank is Private First Class (20 - 50 Reputation Level)Geo.Garnett User rank is Private First Class (20 - 50 Reputation Level) 
Time spent in forums: 4 Days 3 h 13 m 45 sec
Reputation Power: 4
Send a message via AIM to Geo.Garnett
@ Itsacon or MadCowDzz ???

Another side question, How would you substitute the printf, for a cout<< statement or is that even possible to do and still keep the same functionality? Just wondering