【货币机找零问题的递归算法及其优化】

【货币机找零问题的递归算法及其优化】

1、货币机找零问题的一般递归解法

【货币机找零问题的递归算法及其优化】

代码



# @author:wpk
# @time:2021 10 19
# @description: deal the problem change money with recursion
import time

def recMC(coinValueList,change):
    minCoins = change
    # 解决最小规模问题
    if change in coinValueList:
        return 1
    else:
        for i in [c for c in coinValueList if c <= change ]:
            # recMC(coinValueList,change - i)调用自身  +   change - i减小规模
            numCoins = 1 + recMC(coinValueList,change - i)
            if numCoins < minCoins:
                minCoins = numCoins
    return minCoins
start = time.time()
coinValueList =[1,5,10,25]
# print(time.clock())
res = recMC([1,5,10,25],63)
print("在零钱列表为%s的货币政策中,找零%s,需要的最小钱币个数为%s:" %(coinValueList,63,res))
end = time.time()
print('usingtime = %s' %(end-start))

运行结果

非优化情况下的运行时间为: 26.27496314048767
【货币机找零问题的递归算法及其优化】

2、优化后的递归解法

优化思路与理念

在解决找零过程中,递归解法存在多次的重复计算现象

【货币机找零问题的递归算法及其优化】

解决方法:可以对计算过的钱币,进行记录,在下一次进行时候,先判断是否已经计算过,是,直接调用之前的结果;不是,再进行递归调用
思想:以储存空间,换计算时间

代码


# @author:wpk
# @time:2021 10 19
# @description: deal the problem change money with recursion
import time

def recDC(coinValueList,change,KnownResults):
    minCoins = change
    # 递归基本结束条件
    if change in coinValueList:
        #记录存储最优解
        KnownResults[change] = 1  
        return 1
    elif KnownResults[change] > 0:
        # 查表成功,直接调用计算过的最优解
        return KnownResults[change]
    else:
        for i in [c for c in coinValueList if c <= change ]:
            numCoins = 1 + recDC(coinValueList,change - i,KnownResults)
            if numCoins < minCoins:
                minCoins = numCoins
                #找到的最优解,记录到列表中
                KnownResults[change] = minCoins
    return minCoins

start = time.time()
coinValueList =[1,5,10,25]
# print(time.clock())
res = recDC([1,5,10,25],63,[0]*64)
print("在零钱列表为%s的货币政策中,找零%s,需要的最小钱币个数为%s:" %(coinValueList,63,res))
end = time.time()
print('usingtime = %s' %(end-start))


优化效果

【货币机找零问题的递归算法及其优化】

计算时间明显提升,几乎是瞬间得出!

3、补充:Python编程中计算程序运行时间的方法

  • ① time.time()
import time
start = time.time()

run_function()

end = time.time()
print('usingtime = %s' %(end-start))
  • ② time.clock()

import time
start = time.clock()

run_function()

end = time.clock()
print('usingtime = %s' %(end-start))

  • ③ datatime.datetime.now()

import datetime
start = datetime.datetime.now()

run_function():

end = datetime.datetime.now()
print('usingtime = %s' %(end-start))

上一篇:element Plus 中select组件获得当前点击的节点


下一篇:change user name