Programming Challenge N

[TheQuirk]

Okay, this one's a bit easier than usual.

Find the minimal number of coins you'd need to get n cents (assume dollar, five dollar, etc. coins don't exist).

For example, if n = 19, the answer is 6 (a nickle, a dime, and four pennies).

[worker201]

Wow, that is a hell of a lot easier than your other challenges.  I wrote a program to do this using C++ when I was in college - using Borland Turbo C++ for MS-DOS (this was when Windows 95 was not yet widespread).

[H_TeXMeX_H]

Perhaps I'll actually attempt this one. Don't have time now tho ... maybe later today.

[solemnwarning]

Code: [Select]

#define n 19

int count = 0;
int count_1 = 0;
int count_2 = 0;
int count_5 = 0;
int count_10 = 0;
int count_20 = 0;
int count_50 = 0;
while(count < n) {
if(count + 50 <= n) {
count += 50;
count_50++;
}else if(count + 20 <= n) {
count += 20;
count_20++;
}else if(count + 10 <= n) {
count += 10;
count_10++;
}else if(count + 5 <= n) {
count += 5;
count_5++;
}else if(count + 2 <= n) {
count += 2;
count_2++;
}else if(count + 1 <= n) {
count++;
count_1++;
}
}

Not tested but it should work

(I used UK coins below

[H_TeXMeX_H]

Here it is in shell script (just for fun):

Code: [Select]

#!/bin/sh

printf "Enter the number of cents ==> "
read number

coins=0

for i in 50 25 10 5 1
do
 while test "$number" -ge "$i"
 do
  let coins++
  let number-=$i
 done
done

echo "The answer is $coins coins"

exit 0


[TheQuirk]

This approach works. However, I challenge you to come up with something more compact!

[H_TeXMeX_H]

I don't think it'll get any more compact than that ... anyone else wanna try ?

[worker201]

I'm a pretty shitty programmer, I can barely slap together a helloworld anymore without a myriad of syntax errors.  But hey, I got this one to work!  For some reason, I got it in my head that integer division was the way to go with this.  I wanted to use perl, just because I'm trying to learn it right now, but perl only does float division.  So does JavaScript.  So I had to pull out a couple C manuals.

 

Code: [Select]

#include

main()
{

int value;
int i;
int total=0;
int coins[5]={50,25,10,5,1};

printf("Enter an integer monetary value: \n");
scanf("%d", &value);

for(i=0; i<5; i++) {
total += value / coins[i];
value = value % coins[i];
}

printf("That's %d coins \n", total);
}Pretty compact, I guess - the actual meat of the program is only 2 lines long.  Keepin' it real - straight-up old skool K&R brace style.

[TheQuirk]

That's essentially what I was thinking about. You can do all this without a loop, however! I challenge youse guys.

[worker201]

Unless you have some shifty if/else ladder in mind, I'm not sure what you're looking for.  Maybe a hint?

[TheQuirk]

The operators / and %.

[sledz41]

Therefore the code would be:

Code: [Select]

#include
 
int main ()
{
 
int value;
int count = 0;
 
printf("Enter an integer monetary value: \n");
scanf("%d", &value);
 
count += value / 50;
value %= 50;
 
count += value / 25;
value %= 25;
 
count += value / 10;
value %= 10;
 
count += value / 5;
value %= 5;
 
count += value / 1;
value %= 1;
 
printf("Minimum number of coins required is: %d\n", count);
 
return 0;
}
?

[TheQuirk]

Yup! Good job.

Now, would anyone be interested in me breaking up the last challenge into multiple parts with hints?

[worker201]

Therefore the code would be:

Code: [Select]

program
?

Well, that works, I guess.  But I don't think it is good style.  To switch to a different currency system, such as Britain, who uses 2pence coins, would be very difficult.  Adding bills to the concept is also problematic, since you would have to at least double the amount of code.  My version, using a single array to contain all the possible values, is much more easily converted - no matter what kind of monetary system you want to implement, you only have to change one line.

Although I realize that this was an exercise in thinking, maintainability and portability are almost as important as algorithm design, these days.  Good computer programming is a marriage of design and implementation.

[worker201]

Yup! Good job.

Now, would anyone be interested in me breaking up the last challenge into multiple parts with hints?

You mean this one?
http://www.microsuck.com/forums/showthread.php?t=10050

Sure, go ahead.