# Qbasicnews.com

Full Version: Real life problems :)
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2 3
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!
```'  *** '-- 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```