这个程序在Python中意外的行为 [英] unexpected behaviour in this program in python

问题描述

我有这个代码来计算最小数量的硬币从一个总数与给定的命名清单。
例如： 69的最小变化[25,10,5,1]：[25,25,10,5,1,1,1,1] $ b

  def get_min_coin_configuration（sum = None，coins = None，cache = {}）：
 #if缓存==无：＃这是非常重要的，如果它在定义中它的存在...... 
＃cache = {} 
如果在缓存中求和：
 return cache $ 
 elif sum in coins：＃如果以硬币结算，则无关，只能返回。 
高速缓冲存储器= 
返回高速缓冲存储器
 elif min（硬币）>总和：＃如果最大的硬币大于总和，那么我们无能为力。 
 #cache [] = [] 
 #return cache 
 return [] 
 else：＃检查每个硬币，记录最小配置，然后返回它。 
 min_length = 0 
 min_configuration = [] 
对于硬币中的硬币：
 results = get_min_coin_configuration（总和 - 硬币，硬币，缓存）
如果结果！= [] ：如果min_length == 0或（1 + len（结果）），则
< len（min_configuration）：
 #printmin config，min_configuration 
 min_configuration = [coin] + results 
 #printmin config，min_configuration 
 min_length = len（min_configuration） 
高速缓存总数= min_configuration 
返回高速缓冲存储器
如果__name__ ==__main__：
 print带有分量的最小变化69 [25,10,5， 1]通过递归：，get_min_coin_configuration（69，[25,10,5,1]）$ ​​b $ b print** 45 
 print带有分号的7的最小变化[4,3,1]通过递归：，get_min_coin_configuration（7，[4,3,1]）$ ​​b $ b  

该程序似乎当我注释掉主要中的任何一个打印语句时工作正常。
当我有两个函数调用时，它打印错误。注释掉主要的打印语句，你会发现它正确打印了最小的硬币。

  [25,10,5,1]递归：[25，25，10，5，1，1，1，1] 
 ***************** **************************** 
最小变化为7，具有分数[4,3,1]递归：[5 ，1，1] 
  




解决方案

  if __name__ ==__main__：
 cache_denom_set1 = {} 
 cache_denom_set2 = {} 
 print通过递归[25,10,5,1]打印69的最小变化：，get_min_coin_configuration（69，[25,10,5,1]，cache_denom_set1）
 print** 45 
 print通过递归[4,3,1] ：，get_min_coin_configuration（7，[4,3,1]，cache_denom_set2）
  

单独传递缓存每一组面额

问题是您的缓存已经知道如何进行更改为7作为5,1,1所以它只是返回...缓存不知道5不再在面额集...

字典是可变的像列表...这应该证明问题
$ b $ pre $ code def dict_fn（cache = {}）：
cache [len （cache.keys（））] = 1
print cache

dict_fn（）
dict_fn（）


I have this code to calculate minimum number of coins from a sum with given list of denomiations. for eg : minimum change for 69 with denomiations [25,10,5,1] : [25, 25, 10, 5, 1, 1, 1, 1]

def get_min_coin_configuration(sum=None, coins=None, cache={}):
    #if cache == None:  # this is quite crucial if its in the definition its presistent ...
    #    cache = {}
    if sum in cache:
        return cache[sum]
    elif sum in coins:  # if sum in coins, nothing to do but return.
        cache[sum] = [sum]
        return cache[sum]
    elif min(coins) > sum:  # if the largest coin is greater then the sum, there's nothing we can do.
        #cache[sum] = []
        #return cache[sum]
        return []
    else:  # check for each coin, keep track of the minimun configuration, then return it.
        min_length = 0
        min_configuration = []
        for coin in coins:
            results = get_min_coin_configuration(sum - coin, coins, cache)
            if results != []:
                if min_length == 0 or (1 + len(results)) < len(min_configuration):
                    #print "min config", min_configuration
                    min_configuration = [coin] + results
                    #print "min config", min_configuration
                    min_length = len(min_configuration)
                    cache[sum] = min_configuration
        return cache[sum]
if __name__ == "__main__":
    print "minimum change for 69 with denomiations [25,10,5,1] by recursive : ",get_min_coin_configuration(69,[25,10,5,1])
    print "*"*45
    print "minimum change for 7 with denomiations [4,3,1] by recursive : ",get_min_coin_configuration(7,[4,3,1])

The program seems to work fine when I comment out either of the print statements in the main. when I have both function calls, it is printing wrongly. comment out either print statements in the main and you would see that it prints the minimum coins correctly.

minimum change for 69 with denomiations [25,10,5,1] by recursive :  [25, 25, 10, 5, 1, 1, 1, 1]
*********************************************
minimum change for 7 with denomiations [4,3,1] by recursive :  [5, 1, 1]

解决方案

if __name__ == "__main__":
    cache_denom_set1 = {}
    cache_denom_set2 = {}
    print "minimum change for 69 with denomiations [25,10,5,1] by recursive : ",get_min_coin_configuration(69,[25,10,5,1],cache_denom_set1)
    print "*"*45
    print "minimum change for 7 with denomiations [4,3,1] by recursive : ",get_min_coin_configuration(7,[4,3,1],cache_denom_set2)

pass in a separate cache for each set of denominations

the problem is that your cache already knows how to make change for 7 as 5,1,1 so it just returns that ... the cache is unaware that 5 is no longer in the denomination set ...

dictionaries are mutable like lists ... this should demonstrate the problem

def dict_fn(cache={}):
    cache[len(cache.keys())] = 1
    print cache

dict_fn()
dict_fn()

这篇关于这个程序在Python中意外的行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！