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...