This was an exercise in an exam I did in my 2nd course at Computer Engineering. I think it has application for real life plus it helps to demonstrate some programming techniques.
Best coin change
The challenge is coding a function that given a number and an array with numerical values of coins it calculates and returns the combination with the smaller amount of coins.
This is, if the function is given 76 and coins are (1, 5, 10, 25, 50) it returns (50, 25, 1) instead of, for example, (25, 25, 25, 1).
If there are several solutions with the same amount of coins, it returns the first one found.
The prototype should be this one:
Code:
DECLARE FUNCTION Change% (amount AS INTEGER, values() AS INTEGER, sol() AS INTEGER)
The FUNCTION return the number of coins in the sollution, obviously 0 if no combination is possible (imagine amount = 2 and values() = (5, 10, 25), for example).
An example of use may be:
Code:
DIM v%(5)
DIM s%(100)
v%(0)=1
v%(1)=5
v%(2)=10
v%(3)=25
v%(4)=50
v%(5)=100
coins% = Change% (347, v%(), s%())
FOR i%=1 TO coins%
PRINT s%(i%)
NEXT i%
Challenging enough? (It's way easier than it looks like).
Nathan, I love it!
Reminds me of when we programmed the change dispenser for a Point of Sale terminal for a cashier. That was back in 1993, I think I have the Quickbasic code somewhere. Got to read the comments first, because I'm not sure what the requirements were.
It had some tricky stuff becuase not all countries have exact change capablities, in which case, by store policy, you round the change up or down. Oracle wrote up an article about something similar because New Zealand doesn't have pennies, so they invented a national rounding method or algorithm.
*****
I got one that's pretty much what you asked for. (I hope)
[syntax="QBASIC"]DECLARE FUNCTION Change (amount, values(), valuewanted)
CLS
DIM values(4)
values(0) = 1
values(1) = 5
values(2) = 10
values(3) = 25
values(4) = 100
FOR i = 4 TO 0 STEP -1
PRINT values(i); Change(347, values(), i)
NEXT i
FUNCTION Change (amount, values(), valuewanted)
total = amount
DIM a(UBOUND(values))
FOR i = UBOUND(values) TO 0 STEP -1
a(i) = INT(total / values(i))
total = total - (a(i) * values(i))
NEXT i
Change = a(valuewanted)
END FUNCTION[/syntax]
Heres my way, the output section is a little different from what you suggested, nathan, for a little variety =)
[syntax="qbasic"]DECLARE FUNCTION change% (amount%, v%(), s%())
DEFINT A-Z
DIM v(5)
DIM s(5)
v(0) = 1
v(1) = 5
v(2) = 10
v(3) = 25
v(4) = 50
v(5) = 100
CLS
INPUT "Please input the amount to convert to change"; amount
coins = change(amount, v(), s())
PRINT : PRINT "Coins required:": PRINT
FOR i = UBOUND(v, 1) TO 0 STEP -1
IF s(i) THEN PRINT " "; s(i); v(i); "credit coins"
NEXT i
PRINT : PRINT coins; "coins in total"
FUNCTION change (amount, v(), s())
temp = amount
FOR i = UBOUND(v, 1) TO 0 STEP -1
DO WHILE temp >= v(i)
temp = temp - v(i)
coinno = coinno + 1
s(i) = s(i) + 1
LOOP
NEXT
change = coinno
END FUNCTION[/syntax]
Both of your entries compute the fist solution found, but it hasn't to be necessarily the best one. Imagine you have coins (25, 75, 100). You enter 150 as an amount: your functions would return three coins: (100, 25, 25), when there is a better sollution: (75, 75), just two coins
.
Also they assume that the coins array is ordered, and it doesn't have to. You could have a coins array (5, 100, 10, 20, 1, 50).
But they are great approaches
. Keep tryin'.
Those are some hard problems, but i think ive got a new soloution!
I have included the problems that you mentioned. Just unremark the problem you want the program to run.
It incorporates sorting and an efficiency test. (to find the lowest number of coins needed)
[syntax="qbasic"]DECLARE FUNCTION change% (amount%, v%(), s%())
'$STATIC
DEFINT A-Z
DIM s(5)
'Please unremark the problem you wish to run:
'This one doesnt need sorted:
'DIM v(5)
'v(0) = 1
'v(1) = 5
'v(2) = 10
'v(3) = 25
'v(4) = 50
'v(5) = 100
'amount = 347
'This one does need sorted:
'DIM v(5)
'v(0) = 10
'v(1) = 50
'v(2) = 1
'v(3) = 100
'v(4) = 25
'v(5) = 5
'amount = 347
'This one can be done more easily than 1x100 + 2x25:
'DIM v(2)
'v(0) = 25
'v(1) = 75
'v(2) = 100
'amount = 150
CLS
'INPUT "Please input the amount to convert to change"; amount
coins = change(amount, v(), s())
PRINT : PRINT "Coins required:": PRINT
FOR i = UBOUND(v, 1) TO 0 STEP -1
IF s(i) THEN PRINT " "; s(i); v(i); "credit coins"
NEXT i
PRINT : PRINT coins; "coins in total"
FUNCTION change (amount, v(), s())
'init a little siftsort:
FOR i = 1 TO UBOUND(v, 1)
FOR j = 0 TO UBOUND(v, 1) - i
IF v(j) > v(j + 1) THEN SWAP v(j), v(j + 1)
NEXT
NEXT
lowest = 999
FOR ii = UBOUND(v, 1) TO 0 STEP -1
coinno = 0
temp = amount
ERASE s
FOR i = ii TO 0 STEP -1
DO WHILE temp >= v(i)
temp = temp - v(i)
coinno = coinno + 1
s(i) = s(i) + 1
LOOP
NEXT
IF coinno < lowest THEN
lowest = coinno
lowstart = ii
END IF
NEXT
temp = amount
ERASE s
coinno = 0
FOR i = lowstart TO 0 STEP -1
DO WHILE temp >= v(i)
temp = temp - v(i)
coinno = coinno + 1
s(i) = s(i) + 1
LOOP
NEXT
change = coinno
END FUNCTION[/syntax]
Come on nath! I need an answer!
You will have it tomorrow... Now I have to get a bus!
Advance: not the most efficient sollution, but it works. Detailed comments tomorrow
good work!
Code-title comments say it all!..
Hopefully, if I have the time, I'll post a solution optimizer by tomorrow. For your ease of understanding, it'll have the same variable names, and lots of comments. This is for you to see a different implementation; and what's more: it's granular.
Comment, comment, comment (and, when commenting, be building, not destructive :-D ).
Code:
' ***
'-- na_th_an's Coin Challenge: The Greedy Approach
'-- Explore under QB IDE.
' ***
'-- This is a 30-min-code intended as a quick, unoptimized solution
' generator. Posted for you to see the implementation.
' Please comment!..
'-- If I have the time, I'd really like to post the optimized solution finder!..
'-- ToohTooh, in Istanbul.
'-- Nostalgia, anyone? This is much like my Quantitative Decision Making
' Techniques course first-week assignments... Cosy!
' Thanks, na_th_an!..
DEFINT A-Z
DECLARE FUNCTION Change (Amount, Va(), So()) '>> This definition changed a lot
DECLARE FUNCTION FindLimit (Va())
DECLARE FUNCTION Sort (Va())
OPTION BASE 1 '>> I opt this...
CONST logicalEndSentinel = -1
'-- I can't dynamically dimension those due to BASIC limitations.
DIM values(10), solution(10) '>> INFO: {x: End of So() | So(x) = -1}
'-- Fill in values() to feed Va().
values(1) = 75
values(2) = 25
values(3) = 100
values(4) = -1 '>> End-of-array-value to differ the logical and physical
values(5) = 50 ' bounds of values(). values() won't be sorted or process-
values(6) = 1 ' ed after -1.
myAmount = 150
CLS
PRINT "Solution to"; myAmount;
sortResult = Sort(values()) '>> Returns always -1.
changeResult = Change(myAmount, values(), solution())
'-- Lecturer:
' Couldn't we have said
' changeResult = Change(myAmount, Sort(values()), solution())
' Why? Why not?
'-- changeResult table
' -1 Success
' 1 Empty Va()
' 2 Can't meet criteria with present Va()
' 999 Debug with current assign - something bad occured
'-- Lecturer:
' Will
' myAmount
' survive down here? Why? Why not?
PRINT "is:";
FOR i = 1 TO UBOUND(solution)
IF solution(i) = logicalEndSentinel THEN EXIT FOR
PRINT solution(i);
NEXT i
PRINT '>> Feed a new line
END
FUNCTION Change (Amount, Va(), So()) '>> ZZZZ: No bounds checking
' anywhere within this FUNC for So()!
nxtSo = 1 '>> Track for solution appending.
'-- Find the logical end of "Va()".
nxtVa = FindLimit(Va())
IF nxtVa = -1 THEN
GOSUB prepareToBailOut '>> Not even a single So() for empty Va().
Change = 1 '>> Empty Va().
EXIT FUNCTION
END IF
DO
'-- Find the nearest integer divisor of "amount" for "Va(nxtVa)".
divisor = Amount \ Va(nxtVa)
'-- Append that much to our solution.
FOR i = 1 TO divisor
So(nxtSo) = Va(nxtVa)
nxtSo = nxtSo + 1
NEXT i
'-- Done so far.
Amount = Amount - Va(nxtVa) * divisor
IF Amount = 0 THEN
GOSUB prepareToBailOut
Change = -1 '>> Change success.
EXIT FUNCTION
END IF
'-- We're done with current Va().
nxtVa = nxtVa - 1
IF nxtVa < 1 THEN '>> Has Va() exhausted?
GOSUB prepareToBailOut
IF Amount > 0 THEN '>> Still have some Amount?
Change = 2 '>> Couldn't meet the criteria with present Va().
EXIT FUNCTION
END IF
Change = -1 '>> Change success.
EXIT FUNCTION
END IF
LOOP
Change = 999 '>> Debug - won't ever reach here. Left as a sentinel
' to prevent absent-mindedness after some revision.
EXIT FUNCTION
prepareToBailOut:
So(nxtSo) = logicalEndSentinel '>> Cut So() off.
RETURN
END FUNCTION
'
'-- Finds the logical end of an array.
'
FUNCTION FindLimit (Va())
FOR i = UBOUND(Va) TO 1 STEP -1
IF Va(i) = logicalEndSentinel THEN
IF i > 1 THEN
FindLimit = i - 1 '>> Limit for Va().
EXIT FOR
ELSE
FindLimit = -1 '>> Va() exhausted - still can't find limit.
EXIT FUNCTION
END IF
END IF
NEXT i
END FUNCTION
'
'-- Simple bubble sort.
'
FUNCTION Sort (Va())
limit = FindLimit(Va()) '>> No need to sort the entire array.
DO
switch = 0
FOR current = 1 TO (limit - 1)
'-- Two adjacent elements are out of order, so swap their values.
IF Va(current) > Va(current + 1) THEN
SWAP Va(current), Va(current + 1)
switch = current
END IF
NEXT current
'-- Sort on next pass only to where the last switch was made.
limit = switch
LOOP WHILE switch
Sort = -1 '>> FUNC Sort() default.
END FUNCTION
O_O your code is so... neat... and commented...