1 算法（Algorithm）

算法通俗来讲，就是为了解决一个适当的公式化表示的问题而必须执行的一系列指令。一个适当的公式化表示的问题必须是清楚和明确的。该书引入了伪代码，它是一种计算机科学家常用来描述算法的语言，它可以忽略了许多程序设计的细节，可以更好的描述算法问题。

image.png

2 什么是正确的算法

当以一个算法能够将每一个输入实例转换为正确的输出时，这个算法才是正确的。对于一个算法而言，若至少有一个输入实例不能产生正确的输出，那么这个算法就是不正确的。 这段简单的描述定义了算法的正确性，它说明了算法的普适性，必须适用于所有场景。但是通常我们考虑问题不够全面，不能一下写出正确的算法。以下将以 “美国找钱问题” 为例，教你怎样写一个正确的算法。

美国找钱问题

美国找钱问题描述：
用最少的硬币个数转换一定金额的钱
输入：金额总数M
输出：最少个数的25分硬币q个，20分硬币a个，10分硬币d个，5分硬币n个，1分硬币p个相加，使总金额等于M（即25q+20a+10d+5n+p=M）并且q+a+d+n+p尽可能的小

（1）错误算法实现:

这种算法是最容易想到的思路，按照币值从大到小依次找钱，先找币值最多的，再找币值虽少的。虽然这种思路可以找到正确的钱数，但是由于没有考虑所有q+a+d+n+p相加为M的各种情况，找到的硬币书不一定是最小的。

#错误算法代码实现(python语言)
c_list = [25,20,10,5,1]#币值类型
def betterchange(M,c_list):
    new_M = M
    d_list = []
    for i in c_list:
        i_number = new_M/i
        new_M = new_M%i
        d_list.append(i_number)
    print d_list
#错误结果：
betterchange(40,c_list)
[1, 0, 1, 1, 0] 

（2）正确算法实现:

正确的思路是：1、考虑所有找钱的方法；2、选择所有正确的找钱方法；3、选择所有正确找钱方法中最小的一种

#正确代码实现(python语言)
from itertools import product
def BetterForceChange(M,c_list):
    #存入所有可能的找钱方法
    all_prob_tuple_list = []
    prob_number_list = []
    for i in c_list:
        prob_number = M/i
        prob_number_list.append(prob_number)
    loop_var_list = []
    for prob_number in prob_number_list:
        loop_var_list.append([x for x in range(prob_number+1)])
    for i in product(*loop_var_list):
        all_prob_tuple_list.append(i)
    #存入所有正确的找钱方法
    all_right_tuple_list = []
    for all_prob_tuple in all_prob_tuple_list:
        money_number = sum(map(lambda (a,b):a*b,zip(c_list,list(all_prob_tuple))))
        if money_number == M :
            all_right_tuple_list.append(all_prob_tuple)
    #对正确的找钱方法进行筛选，找出最小的找钱组合
    coin_number_right_list_dict = {}
    min_coin_number = float('inf') 
    for right_tuple in all_right_tuple_list:
        coin_number = sum(list(right_tuple))
        if not coin_number_right_list_dict.has_key(coin_number):
            coin_number_right_list_dict[coin_number] = [list(right_tuple)]
        else:
            coin_number_right_list_dict[coin_number].append(list(right_tuple))
        if coin_number < min_coin_number :
            min_coin_number = coin_number
    print coin_number_right_list_dict[min_coin_number]
#正确结果
BetterForceChange(40,[25,20,10,5,1])           
[[0, 2, 0, 0, 0]]    
#