コイン支払い問題（２）の考察

　コイン支払い問題（２）の考察を示します。

(考察）コイン支払い問題（２）を解くBasicプログラム

' n円を1円硬貨で支払う方法の数をP(n)とする。
' n円を5円硬貨と1円硬貨で支払う方法の数をQ(n)とする。
' n円を10円硬貨と5円硬貨と1円硬貨で支払う方法の数をR(n)とする。
' n円を50円硬貨と10円硬貨と5円硬貨と1円硬貨で支払う方法の数をS(n)とする。
' nは1以上100以下。
'
Dim P(1000),Q(1000),R(1000),S(1000)
'
N=100:  ' 支払金額。
'
Do
  Read N
  Data 100,200,300,400,500,600,700,800,900,1000,0
  '
  If N = 0 Then Exit Do
  '
  For I=0 to N: P(I)=1: Next I 
  '
  For I=0 To 4: Q(I)=P(I): NEXT I
  For I=5 To N: Q(I)=Q(I-5)+P(I): Next I
  '
  For I=0 To 9: R(I)=Q(I): NEXT I
  For I=10 To N: R(I)=R(I-10)+Q(I): Next I
  '
  For I=0 To 49: S(I)=R(I): NEXT I
  For I=50 To N: S(I)=S(I-50)+R(I): Next I
  '
  Print Using"######円を1円、5円、10円、50円で支払う方法 ";N;
  Print S(N);"通り"
Loop
End

実行結果

100円を1円、5円、10円、50円で支払う方法 158通り
200円を1円、5円、10円、50円で支払う方法 855通り
300円を1円、5円、10円、50円で支払う方法 2492通り
400円を1円、5円、10円、50円で支払う方法 5469通り
500円を1円、5円、10円、50円で支払う方法 10186通り
600円を1円、5円、10円、50円で支払う方法 17043通り
700円を1円、5円、10円、50円で支払う方法 26440通り
800円を1円、5円、10円、50円で支払う方法 38777通り
900円を1円、5円、10円、50円で支払う方法 54454通り
1000円を1円、5円、10円、50円で支払う方法 73871通り
OK