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

• • 1、货币机找零问题的一般递归解法
  • • 代码
    • 运行结果
  • 2、优化后的递归解法
  • • 优化思路与理念
    • 代码
    • 优化效果
  • 3、补充：Python编程中计算程序运行时间的方法

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))