/***********************************************************
change.c -- 小銭の払い方
***********************************************************/

Function change(n As Long, k As Long) As Long /* 再帰版 */

Dim s As Long
change = 0
If n < 0 Then Exit Function
s = 1 + n / 5 + change(n - 10, 10)
If k >= 50 Then s = s + change(n - 50, 50)
If k >= 100 Then s = s + change(n - 100, 100)
change = s
End Function


Function change1(n As Long) As Long /* 非再帰版 */
Dim i As Long, j As Long, s As Long, t As Long, u As Long
s = 0
i = n / 100 : While i >= 0 : i=i-1 /* 100円玉 */
t = n - 100 * i
j = t / 50 : While j >= 0 : j=j-1 /* 50円玉 */
u = t - 50 * j
s = s + ((1 + u / 5 - u / 10) * (1 + u / 10))
Wend
Wend
change1 = s
End Function

'main
#N88BASIC
Dim i As Long
Print "お金の払い方"
Print " 金額  再帰版 非再帰版"
For i=0 To 500 Step 5
Print i, change(i, i), change1(i)
Next