实用枚举算法(上课)

1、第一讲第一讲 枚举算法枚举算法 数计学院 计算机系 简武斌 什么是枚举法什么是枚举法例例1 1：有个人有一百块钱，打算买一百只鸡。有个人有一百块钱，打算买一百只鸡。市场价格是：公鸡一只市场价格是：公鸡一只3 3元元, ,母鸡一只母鸡一只5 5元元, ,小鸡小鸡3 3只只1 1元。元。试求用试求用100100元买元买100100只鸡只鸡, ,各为多少才合适各为多少才合适? ? 什么是枚举法什么是枚举法算法分析：算法分析：用用x,y,zx,y,z分别表示买的公鸡分别表示买的公鸡, ,母鸡母鸡, ,小鸡的小鸡的数数目，可以得到一个很简单的方程组目，可以得到一个很简单的方程组3 3* *x+5x+5*

2、 *y+z/3=100 y+z/3=100 x+y+z=100 x+y+z=100枚举法的定义枚举法的定义 枚举法（通常也称为穷举法）枚举法（通常也称为穷举法） 指的是从可能的解的集合中一一枚举指的是从可能的解的集合中一一枚举 各元素，各元素， 用题目给定的检验条件判用题目给定的检验条件判 定哪些是无用的，哪些是有用的。定哪些是无用的，哪些是有用的。 能使命题成立的，即为其解。能使命题成立的，即为其解。枚举法解题的基本思路枚举法解题的基本思路（1 1） 确定枚举对象、枚举范围和判定条件确定枚举对象、枚举范围和判定条件 （2 2） 一一枚举可能的解，验证是否是问一一枚举可能的解，验证是否是问 题

3、的解题的解（3 3） 枚举算法的一般结构：各种循环语句枚举算法的一般结构：各种循环语句例例1 百鸡问题百鸡问题int x,y,z;for(x=0;x100;x+) for(y=0;y100;y+) for(z=0;z100;z+) /枚举所有可能枚举所有可能的解的解 if (x+y+z=100)and(x*3+y*2+z/ 3=100)and(z mod 3=0) printf(x=+x+y=+y+z=+z); 例例1 百鸡问题百鸡问题int x,y,z;for(x=0;x100;x+) for (y=0;y100-x;y+)z=100-x-y;if (x*3+y*2+z/3=100)and(

4、z mod 3=0) printf(x=+x+y=+y+z=+z); 三种鸡的和是固定的，我们只要枚举二种鸡（x,y），第三种鸡就可以根据约束条件求得（z=100-x-y），缩小了枚举范围，例例2 Joseph问题问题 有有n n个人围坐在一个圆桌周围，把这个人围坐在一个圆桌周围，把这n n个人依次编号个人依次编号为为1 1，n n。从编号是。从编号是1 1的人开始报数，数到第的人开始报数，数到第m m个个人出列，然后从出列的下一个人重新开始报。人出列，然后从出列的下一个人重新开始报。 现有前面现有前面k k个中国人个中国人, ,后面后面k k个日本人坐在一起个日本人坐在一起. .对于对于给定

5、的给定的k k。求出。求出m m的最小值的最小值, ,使得中国人是在所有日本使得中国人是在所有日本人出列之后出列。人出列之后出列。假设假设：1k141k14样例样例输入：输入：k=3输出：输出：m=5 算法分析：算法分析： 我们可以枚举我们可以枚举m=k+1,m=k+1,然后来判断每个然后来判断每个m m是否符合条件是否符合条件, ,如果符合条件如果符合条件, ,那么就输那么就输出结果。因为出结果。因为k k最大为最大为14,14,所以这个题可所以这个题可以用枚举法。以用枚举法。例例2 Joseph问题问题提示：提示：按照某个长度按照某个长度m遍历一个长度为遍历一个长度为2k的数组环的方法：的数组环的方法： int count=0; int travel=-1; while(count=1。要求由小到大依次在同一行输出这三个实根要求由小到大依次在同一行输出这三个实根(根根与根之间留有空格与根之间留有空格)，并精确到小数点后，并精确到小数点后2位。位。提示：提示：记方程记方程f(x)=0，若存在，若存在2个数个数x1和和x2，且，且