Count the coins: Difference between revisions
added FreeBASIC
(→{{header|Lua}}: Aded output and shortened) |
(added FreeBASIC) |
||
Line 967:
100 5 count-change .</lang>
=={{header|FreeBASIC}}==
Translation from "Dynamic Programming Solution: Python version" on this webside [http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/]
<lang freebasic>' 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</lang>
{{out}}
<pre>
There are 242 ways to make change for $ 1 with 4 coins
There are 133423351001 ways to make change for $ 1000 with 4 coins
There are 13398445413854501 ways to make change for $ 1000 with 6 coins</pre>
=={{header|FutureBasic}}==
| |||