66 lines
1.5 KiB
Text
66 lines
1.5 KiB
Text
' version 09-10-2016
|
|
' compile with: fbc -s console
|
|
|
|
|
|
Function count(S() As UInteger, n As UInteger) As ULongInt
|
|
|
|
Dim As Integer i, j
|
|
' calculate m from array S()
|
|
Dim As UInteger m = UBound(S) - LBound(S) +1
|
|
Dim As ULongInt x, y
|
|
|
|
'' We need n+1 rows as the table is consturcted in bottom up manner using
|
|
'' the base case 0 value case (n = 0)
|
|
Dim As ULongInt table(n +1, m)
|
|
|
|
'' Fill the enteries for 0 value case (n = 0)
|
|
For i = 0 To m -1
|
|
table(0, i) = 1
|
|
Next
|
|
|
|
'' Fill rest of the table enteries in bottom up manner
|
|
For i = 1 To n
|
|
For j = 0 To m -1
|
|
'' Count of solutions including S[j]
|
|
x = IIf (i >= S(j), table(i - S(j), j), 0)
|
|
'' Count of solutions excluding S[j]
|
|
y = IIf (j >= 1, table(i, j -1), 0)
|
|
''total count
|
|
table(i, j) = x + y
|
|
Next
|
|
Next
|
|
|
|
Return table(n, m -1)
|
|
|
|
End Function
|
|
|
|
' ------=< MAIN >=------
|
|
|
|
Dim As UInteger n
|
|
Dim As UInteger value()
|
|
|
|
ReDim value(3)
|
|
value(0) = 1 : value(1) = 5 : value(2) = 10 : value(3) = 25
|
|
|
|
n = 100
|
|
print
|
|
Print " There are "; count(value(), n); " ways to make change for $";n/100;" with 4 coins"
|
|
Print
|
|
|
|
n = 100000
|
|
Print " There are "; count(value(), n); " ways to make change for $";n/100;" with 4 coins"
|
|
Print
|
|
|
|
ReDim value(5)
|
|
value(0) = 1 : value(1) = 5 : value(2) = 10
|
|
value(3) = 25 : value(4) = 50 : value(5) = 100
|
|
|
|
n = 100000
|
|
Print " There are "; count(value(), n); " ways to make change for $";n/100;" with 6 coins"
|
|
Print
|
|
|
|
' empty keyboard buffer
|
|
While Inkey <> "" : Wend
|
|
Print : Print "hit any key to end program"
|
|
Sleep
|
|
End
|