36 lines
1.1 KiB
Text
36 lines
1.1 KiB
Text
DIM uscoins%(3)
|
|
uscoins%() = 1, 5, 10, 25
|
|
PRINT FNchange(100, uscoins%()) " ways of making $1"
|
|
PRINT FNchange(1000, uscoins%()) " ways of making $10"
|
|
|
|
DIM ukcoins%(7)
|
|
ukcoins%() = 1, 2, 5, 10, 20, 50, 100, 200
|
|
PRINT FNchange(100, ukcoins%()) " ways of making £1"
|
|
PRINT FNchange(1000, ukcoins%()) " ways of making £10"
|
|
END
|
|
|
|
DEF FNchange(sum%, coins%())
|
|
LOCAL C%, D%, I%, N%, P%, Q%, S%, table()
|
|
C% = 0
|
|
N% = DIM(coins%(),1) + 1
|
|
FOR I% = 0 TO N% - 1
|
|
D% = coins%(I%)
|
|
IF D% <= sum% IF D% >= C% C% = D% + 1
|
|
NEXT
|
|
C% *= N%
|
|
DIM table(C%-1)
|
|
FOR I% = 0 TO N%-1 : table(I%) = 1 : NEXT
|
|
|
|
P% = N%
|
|
FOR S% = 1 TO sum%
|
|
FOR I% = 0 TO N% - 1
|
|
IF I% = 0 IF P% >= C% P% = 0
|
|
IF coins%(I%) <= S% THEN
|
|
Q% = P% - coins%(I%) * N%
|
|
IF Q% >= 0 table(P%) = table(Q%) ELSE table(P%) = table(Q% + C%)
|
|
ENDIF
|
|
IF I% table(P%) += table(P% - 1)
|
|
P% += 1
|
|
NEXT
|
|
NEXT
|
|
= table(P%-1)
|