知恵袋で見つけた小銭の払い方の問題をPythonで解いてみた。

　最近、Google アナリティクスで拙ブログの記事「支払う硬貨の組合せの数の問題をJavaで解いてみた。」が人気のようなので、知恵袋で見つけた小銭の払い方の問題をPythonで解いてみました。(^_^;

千円札、五百円、百円硬貨を使って3000円を支払う方法は何通りあるか。

　よく考えたら千円も含まれるので硬貨だけじゃないよねってことで「支払う硬貨の組合せの数の問題」から「小銭の払い方の問題」にタイトルを変えることにしました。(^_^;
　プログラムはほとんどJavaからの翻訳です。(^_^;
　ちなみに、payCoin()関数内の省略可の行は、省略可というよりは、Coinのリストが[1,5,10･･･]や[10,50,100,･･･]などのように、1：5：10で始まる場合しか使えないようなので、小さい数で省略してもしなくても結果が変わらないかどうか確認してから使いましょう。(^_^;

● Payment1.py

# coding: UTF-8
# Payment1.py

from time import time

def payCoin(n,s,Coin):
    if s%Coin[0]!=0: return -1
    if n< 0: return 0
    if n==0: return 1

    r = 0; m = s//Coin[n]; t = s
    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])   # 省略可
        r+=payCoin(n-1,t,Coin)
        t-=Coin[n]
    return r

def main():
    tm=time()  # Timer Start
    M = 3000
    lCoins = [100,500,1000] # 昇順ソート && 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()

●実行結果

16
Runtime : 0.000 [sec]

※参考URL
●『Javaによるアルゴリズム事典』サポートページ
●支払う硬貨の組合せの数の問題をJavaで解いてみた。
●支払う硬貨の組合せの数の問題をJavaで解いてみた。(2)
●ネットで見つけた小銭の払い方の問題をPythonで解いてみた。