Lesson 9 穷举法/暴力法 (二) (Brutal Force)¶

思考题1¶

给定一按顺序排列的数组（有可能有重复），如[-7, -5, -3, -1, 1, 2, 5, 6, 7, 9], 请找出其中两数，且两数的和为0。

解法思路：从上一节课中，我们已经知道了如何使用两个嵌套的循环，就能够完全的把所有两两数之和进行一遍比较，但是现在题目的条件已经改变，使用上节课的程序会得到重复的解。

先看上节课的解题方法：

def find_sum(array, k):
    i = 0
    while i < len(array) - 1:
        j = i + 1
        while j < len(array):
            if array[i] + array[j] == k:
                print(array[i], array[j])
            j += 1
        i += 1

我们使用数组[-7, -6, -4, -3, -2, -2, -2, -1, 0, 0, 0, 1, 2, 2, 2, 3, 5, 7, 9]进行一下测试，看一看结果：

array = [-7, -6, -4, -3, -2, -2, -2, -1, 0, 0, 0, 1, 2, 2, 2, 3, 5, 7, 9]
find_sum(array, 0)

运行后得到输出结果：

可以看到，其中的[-2, 2], [0, 0]两组数在解中重复了多次，那怎么样才能解决这个问题呢？

首先我们一定要注意题目的条件：这是一个有序的数组（即数组是从小到大进行排列的，所以我们知道相同的数字一定是紧挨在一起的），所以利用这个特点，我们可以将重复的数排除出去或者直接跳过。
分析在数组中，当循环i, j分别处于什么情况下的时候需要跳过。
- i的情况：当前i位置的数字与前一个位置即i-1处的数字相同时，需要跳过。
- j的情况：当前j位置的数字与前一个位置即j-1处的数字相同时，需要跳过。
特别要注意边界情况：比如i == 0时，和j == i+1时。

请看动画

请将下面的空行填补上正确的语句

def find_sum_v2(array, k):
    i = 0
    while i < len(array) - 1:
        # 此处应该跳过重复的数
        ______________________
        ______________________
        ______________________
        j = i + 1
        while j < len(array):
            # 此处同样应该跳过重复的数
            ________________________
            ________________________
            ________________________
            if array[i] + array[j] == k:
                print(array[i], array[j])
            j += 1
        i += 1

思考题2¶

今有雉（鸡）兔同笼，上有三十五头，下有九十四足。问雉兔各几何？

解题思路： 1. 首先确定鸡的数量可能的范围是0 ~ 94//2, 兔的数量可能的范围是0 ~ 94 // 4; 2. 使用穷举的方法，将所以头数和足数与题目结果相比较，符合则记录答案。

def chickens_and_rabbits(heads, feet):
    i = 0
    while ______________:
        j = 0
        while _____________:
            currentHeads = ____________________
            currentFeet = ____________________
            if _________________________:
                return {
                    "chickens": i,
                    "rabbits": j,
                }
            j += 1
        i += 1

    return None

results = chickens_and_rabbits(32, 94)

print(results)

就穷举法来说，有没有值得优化的点？

例题3 （逻辑推理类）¶

如何快速委派任务：某侦查队接到一项紧急任务，要求在A、B、C、D、E、F六个队员中尽可能多地挑若干人，但有以下限制条件：

A和B两人中至少去一人；
A和D不能一起去；
A、E和F三人中要派两人去；
B和C都去或都不去；
C和D两人中去一个；
若D不去，则E也不去；

请问应当让哪几个人去？

这种题目是难点是，你如何把现实生活中的情况给抽象到计算机数据中，只要完成了此步，这种题非常简单就能完成。

解题思路： 1. 假设我们使用 0和1来表示某人去或者不去(例： a=0表示a不去，b=1表示b可去，那么我们只要穷举所有人的情况, 那么就能将所有情况一一与限制条件相对比，如果满足即是题目的解。

2. 题目中的限制条件如何用表达式写出？

a = 0
while ___________:
    b = 0
    while __________:
        c = 0
        while __________:
            d = 0
            while __________:
                e = 0
                while ___________:
                    f = 0
                    while ___________:
                        cond1 = ____________
                        cond2 = ____________ 
                        cond3 = ____________
                        cond4 = ____________ 
                        cond5 = ____________ 
                        cond6 = ____________
                        if cond1 and cond2 and cond3 and cond4 and cond5 and cond6:
                            print("a={}, b={}, c={}, d={}, e={}, f={}".format(a, b, c, d, e, f))
                        f += 1
                    e += 1
                d += 1
            c += 1
        b += 1
    a += 1

思考题：¶

派出所抓了A、B、C、D共4名犯罪嫌疑人。已知其中肯定有一名是小偷，警查在审讯过程中分别得到以下口供：
- A说：我不是小偷
- B说：c是小偷
- C说：小偷肯定是d
- D说：c胡说
其中有3个人说的是实话，1个人说的是假话，请用穷举法推断谁是小偷。
穷举法的优点是什么？缺点呢？