7.3解决不确定性问题的穷举算法 有些问题很难用确定的算法步骤进行描述,或 根本就没有确定的算法描述方法,但它们具有这样 的特点:如果问题有一组或多组解,则必定全在某 个集合中;如果集合内无解,集合外也肯定无解。 这样,就可以将集合中的元素一一列举出来,验证 是否为问题的解,这就是穷举法。 最简单得一类穷举问题可用线性方程或线性方 程组或不等式解决。 【例7.6】公元五世纪,我国数学家张邱建在 《算经》一书中提出有趣的百钱买百鸡问题:“鸡 翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一, 百钱买百鸡,问翁母雏各几何?
7.3 解决不确定性问题的穷举算法 有些问题很难用确定的算法步骤进行描述，或 根本就没有确定的算法描述方法，但它们具有这样 的特点：如果问题有一组或多组解，则必定全在某 个集合中；如果集合内无解，集合外也肯定无解。 这样，就可以将集合中的元素一一列举出来，验证 是否为问题的解，这就是穷举法。 最简单得一类穷举问题可用线性方程或线性方 程组或不等式解决。 【例7.6】公元五世纪，我国数学家张邱建在 《算经》一书中提出有趣的百钱买百鸡问题：“鸡 翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一， 百钱买百鸡，问翁母雏各几何？
分析:设xyz分别表示买鸡翁,鸡母,鸡雏的数 目,则有 X+y+Z=100 5x+3y+z/3=100 三个未知数,两个方程,有无穷多组解,在本题 中,应只求正整数解。根据可能性分析,得出可能 的取值范围为:鸡翁x:1~19之间;鸡母:1~32之 间;鸡雏:3~98之间; 可用一个三重循环对xyz的所有组合情况,测试 满足条件的解 为减少循环次数,可对上述方程进行优化,用 z=-100-xy带入另一个方程,得:7X+4y=100
分析：设x,y,z分别表示买鸡翁，鸡母，鸡雏的数 目，则有 x+y+z=100 5x+3y+z/3=100 三个未知数，两个方程，有无穷多组解，在本题 中，应只求正整数解。根据可能性分析，得出可能 的取值范围为：鸡翁x：1～19之间；鸡母：1～32之 间；鸡雏：3～98之间； 可用一个三重循环对x,y,z的所有组合情况，测试 满足条件的解。 为减少循环次数，可对上述方程进行优化，用 z=100-x-y带入另一个方程，得：7x+4y=100