10.2.4　穷举查找

10.2.4　穷举查找

当查找的答案不确定时，其中一个比较简单的算法就是穷举法（Method of Exhaustion），通过某种方式列举所有答案的过程。常见的列举方法有顺序列举、排列列举、组合列举三种。如10.2.1节的线性查找，就是顺序列举，其是穷举查找的一种；排列列举是答案的值之间有顺序关系，如x、y和y、x属于顺序不一致的两种答案；而组合列举是答案的值之间没有顺序关系，如x、y和y、x属于同一个答案。

我国南北朝时期（公元420年—589年），著名的数学家张丘建在《张丘建算经》中提出了世界著名的不定方程问题——百钱百鸡问题：今有鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买鸡百只，问鸡翁母雏各几何？

从百钱百鸡问题可以知道，1只公鸡值5元，1只母鸡值3元，3只小鸡值1元，其对应公式为

式中：x为公鸡数，y为母鸡数，z为小鸡数，它们与各自钱数积的和刚好为100元。

这显然是x、y、z三种鸡只数的组合要满足式（10.1），同时要满足式（10.2）的要求，即

两个公式求3个不确定变量的解的过程，可以用穷举法求组合答案的过程，其解题思路如下：

第一步，100元÷5元/只=20只的情况下，同时考虑至少有1只母鸡、至少有3只小鸡情况下，至多有16只公鸡；(https://www.daowen.com)

第二步，100元-5元=95元且能被3整除的情况下，至少有1只母鸡、至少有3只小鸡情况下，最多只能买96元÷3元/只=32只母鸡；

在公鸡、母鸡最大可能只数得到预估的情况下，3种鸡总数100固定的情况下，可以通过穷举法求其3种鸡的组合答案。

其代码实现过程如下：

代码文件：10_2_4_100chicken.py

通过穷举法求得解如下：

从输出答案可以知道，百钱百鸡问题有3种答案。