研究生课程-算法设计与分析之枚举算法.ppt

《研究生课程-算法设计与分析之枚举算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课前面试找出“水仙花数”“水仙花数”是一个神奇的3位数，其各位数字立方和等于该数本身。例如，153就是一水仙花数。怎样找出所有的“水仙花数”？3位数（100～999）各位数字立方和等于该数本身课前面试猴子分桃五只猴子一起摘了一堆桃子，因为太累了，它们商量决定，先睡一觉再分。一会其中的一只猴子来了，它见别的猴子没来，便将这堆桃子平均分成5份 ，结果多了一个，就将多的这个吃了，并拿走其中的一份。一会儿，第2只猴子来了，他不知道已经有一个同伴来过，还以为自己是第一个到的呢，于是将地上的桃子堆起来，再一次平均分成5份，发现也多了一个，同样吃了

2、这1个，并拿走其中一份。接着来的第3、第4、第5只猴子都是这样做的……根据上面的条件，问这5只猴子至少摘了多少个桃子?第5只猴子走后还剩下多少个桃子?枚举算法基本思想枚举算法也称之为穷举算法，就是按照问题本身的性质，一一列举出该问题所有可能的解，并在列举的过程中，逐一检验每个可能解是否是问题的真正解。若是，则采纳这个解；否则抛弃它。不能遗漏不要重复枚举算法基本思想枚举算法也称之为穷举算法，就是按照问题本身的性质，一一列举出该问题所有可能的解，并在列举的过程中，逐一检验每个可能解是否是问题的真正解。若是，则采纳这个解；否则抛弃它。解的高

3、准确性和全面性实现简单，枚举算法通过循环来逐一列举和验证可能解效率提升空间比较大枚举三步确定枚举对象枚举对象也可以理解为是问题解的表达形式，一般需要用若干参数来描述参数之间需要相互独立，而且，参数数目越少，问题解的搜索空间的维度也相应地小；每个参数的取值范围越小，问题解的搜索空间也越小。逐一列举可能解根据枚举对象的参数构造循环，一一列举其表达式的每一种取值情况。逐一验证可能解根据问题解的要求，一一验证枚举对象表达式的每一个取值，如果满足条件，则采纳它，否则，抛弃之。模糊数字任务描述：一张单据上有一个5位数的编码，因为保管不善，其百位数

4、已经变得模糊不请。但是知道这个5位数是57和67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计这样的数的个数。输入：每一行对应一个测试样例，每一行包含4个数字，依次是万位数，千位数，十位数和个位数。最后一行包含4个-1，表示输入结束。输出：每组测试样例的结果输出占一行，第一个数字表示满足条件的编码个数，后面按升序输出所有满足条件的编码，数字与数字之间用空格隔开。19？95模糊数字枚举对象Obj(h)：记h百位数数字，h=0～9逐一列举for(h=0;h<10;h++)逐一验证19h95能否整除57和67模糊数字续任务

5、描述：一张单据上有一个5位数的编码，因为保管不善，其万位数字和百位数已经变得模糊不请。但是知道这个5位数是57和67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计这样的数的个数。输入：每一行对应一个测试样例，每一行包含3个数字，依次是千位数，十位数和个位数。最后一行包含3个-1，表示输入结束。输出：每组测试样例的结果输出占一行，第一个数字表示满足条件的编码个数，后面按升序输出所有满足条件的编码，数字与数字之间用空格隔开。？9？95模糊数字续枚举对象obj(d1,d2)万位数数字，记为d1，d1=1～9百位数数字，记为

6、d2，d2=0～9逐一列举for(d1=1;d1<10;d1++)for(d2=0;d2<10;d2++)逐一验证d19d295能否整除57和67模糊数字再续任务描述：一张单据上有一个5位数的编码，因为保管不善，其万位数字和千位数已经变得模糊不请。但是知道这个5位数是57和67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计这样的数的个数。输入：每一行对应一个测试样例，每一行包含3个数字，依次是百位数，十位数和个位数。最后一行包含3个-1，表示输入结束。输出：每组测试样例的结果输出占一行，第一个数字表示满足条件的编码个

7、数，后面按升序输出所有满足条件的编码，数字与数字之间用空格隔开。？？095m钱n鸡任务描述：我国古代数学家张丘建在《算经》中出了一道题“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？”，现在假定各鸡种的价格不变，拥有的钱数为m，需要购买的鸡数为n，试求出所有可能的购买方案总数。输入：每行对应一个测试样例，每一行包含2个数字，分别为n和m。最后一行包含2个-1，表示输入结束。输出：每组测试样例的结果输出占一行，输出可能购买方案总数。m钱n鸡枚举对象obj(n1，n2，n3)鸡翁数，记为n1，n1=

8、0～n鸡母数，记为n2，n2=0～n鸡雏数，记为n3，n3=0～n逐一列举三层for循环嵌套逐一验证n1+n2+n3==n,5n1+3n2+n3/3==mm钱n鸡-改进枚举对象obj(n1，n2)鸡翁数，记为n1，n1=