ネットで見つけた小銭の払い方の問題をPythonで解いてみた。

　ネットで見つけた小銭の払い方の問題をPythonで解いてみました。(^_^;
　問題を要約すると次の通りです。

　10円玉、50円玉、100円玉、500円玉の硬貨を使って、1000円を支払う方法は何通りあるか。ただし、使われない硬貨はあってもよいが、支払う硬貨の総数は最大15枚とする。

　元ネタは、『プログラム脳を鍛える数学パズル』のQ05のようです。(^_^;
　拙ブログの記事「知恵袋で見つけた小銭の払い方の問題をPythonで解いてみた。」の再帰プログラムPayment1.pyを雛形にして作ってみました。(^_^;
　プログラムでは、元の関数の引数にリストuを追加して、500円玉、100円玉、50円玉、10円玉の順に硬貨の枚数を得ています。

● Payment2.py

# coding: UTF-8
# Payment2.py

from time import time

def payCoin(n,s,Coin,u):
    if s%Coin[0]!=0: return -1
    if n< 0: return 0
    if n==0:
        u+=[s//Coin[0]]
        if sum(u)> 15: return 0
        print(u)
        return 1

    r,t,m = 0,s,s//Coin[n]
    for i in range(m+1):
##        if n==1: return r+(1+m)
##        if n==2: return r+(1+m)*(1-m+s//Coin[1])   # 省略可
        if i> 15: continue
        r+=payCoin(n-1,t,Coin,u+[i])
        t-=Coin[n]
    return r

def main():
    tm = time()  # Timer Start
    M = 1000
    lCoins = [10,50,100,500] # 昇順ソート && M%lCoins[0]==0
    N = len(lCoins)
    print(payCoin(N-1,M,lCoins,[]))
    print("Runtime : %.3f [sec]"%(time()-tm))   # Timer Stop & Disp

if __name__ == '__main__':
    main()

●実行結果

[0, 5, 10, 0]
[0, 6, 8, 0]
[0, 7, 6, 0]
[0, 8, 4, 0]
[0, 9, 1, 5]
[0, 9, 2, 0]
[0, 10, 0, 0]
[1, 0, 9, 5]
[1, 0, 10, 0]
[1, 1, 7, 5]
[1, 1, 8, 0]
[1, 2, 5, 5]
[1, 2, 6, 0]
[1, 3, 3, 5]
[1, 3, 4, 0]
[1, 4, 0, 10]
[1, 4, 1, 5]
[1, 4, 2, 0]
[1, 5, 0, 0]
[2, 0, 0, 0]
20
Runtime : 0.000 [sec]

※参考URL
●支払う硬貨の組合せの数の問題をJavaで解いてみた。
●支払う硬貨の組合せの数の問題をJavaで解いてみた。(2)
●知恵袋で見つけた小銭の払い方の問題をPythonで解いてみた。

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問