注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

给定一组指定面额的硬币,有多少中方法可以组合成指定的金额算法

python 水墨上仙 2900次浏览 已收录 手机上查看

给定一组指定面额的硬币,有多少中方法可以组合成指定的金额算法

#!/usr/bin/python
#+
# This script computes the number of different ways that combinations
# of a given set of coin denominations can add up to a specified amount.
#
# Call this script as follows:
#
#     make_change --coins=denomination,denomination... [--total] amount ...
#
# where amount is one or more amounts (in integer cents) to compute change
# for, denomination is the list of available coin denominations, and
# --total means to only list the total number of ways to make change,
# not show the details of the combinations themselves.
#
# The details of the combinations are displayed on standard output as
# follows:
#
#     amount => [n1 * denom1, n2 * denom2 ... ]
#
# where the n are the integer numbers of each coin, and the denom are
# the corresponding coin denomination, to make the total add up to amount.
#-
import sys
import getopt
def CoinsCombination(Coins, Amount) :
    """generator function which yields all possible combinations of
    Coins adding up to Amount. Assumes Coins is sorted by increasing
    value."""
    if len(Coins) == 0 :
        if Amount == 0 :
            yield ()
        else :
            return
        #end if
    else :
        Coeff = 0
        while True :
            for Combi in CoinsCombination(Coins[1:], Amount) :
                yield (Coeff,) + Combi
            #end for
            if Coins[0] > Amount :
                break
            Coeff += 1
            Amount -= Coins[0]
        #end while
    #end if
#end CoinsCombination
(Opts, Args) = getopt.getopt \
  (
    sys.argv[1:],
    "",
    ["coins=", "total"]
  )
Coins = None
TotalOnly = False
for Keyword, Value in Opts :
    if Keyword == "--coins" :
        Coins = []
        for Denom in Value.split(",") :
            Coin = int(Denom)
            if Coin <= 0 :
                raise getopt.error("bad --coins denomination \"%s\"" % Denom)
            #end if
            Coins.append(Coin)
        #end for
        if len(Coins) == 0 :
            raise getopt.error("empty --coins specification")
        #end if
        Coins.sort()
    elif Keyword == "--total" :
        TotalOnly = True
    #end if
#end for
if Coins == None :
    raise getopt.error("missing --coins specification")
#end if
if len(Args) == 0 :
    raise getopt.error("missing amounts")
#end if
for Amount in Args :
    Amount = int(Amount)
    NrWays = 0
    for Combi in CoinsCombination(Coins, Amount) :
        NrWays += 1
        if not TotalOnly :
            print "%u => [%s]" % \
                    (Amount,
                     ", ".join(str(a) + " * " + str(b) for a, b in zip(Combi, Coins)))
        #end if
    #end for
    print "%u nr ways = %u" % (Amount, NrWays)
#end for


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明给定一组指定面额的硬币,有多少中方法可以组合成指定的金额算法
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……