计算基础教程 7

授课内容枚举法学时2教学目标知识目标理解枚举法的核心定义与基本思想掌握枚举法的适用场景与使用前提理解百钱买百鸡、火柴棒等式的枚举思路掌握枚举范围优化的基本方法能力目标提升问题解的范围界定与规律提炼能力强化枚举算法的逻辑分析与流程设计能力培养枚举方案优化与高效解题的实践能力重点与难点重点枚举法的核心思想与适用场景百钱买百鸡问题的枚举思路与代码实现火柴棒等式问题的枚举逻辑与优化方法枚举范围的合理界定与冗余优化技巧难点结合题目条件精准界定枚举范围掌握枚举算法的优化思路，减少冗余计算教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接简单算法，学习实用的枚举法解题技巧枚举法是竞赛、考级中高频出现的基础算法枚举法思路简单，适配无明显规律的解题场景掌握枚举优化技巧，提升算法运行效率通过实例练习，强化算法设计与问题解决能力第二部分：新课讲解一、枚举法概述枚举法，也称为穷举法或暴力求解法，其思想是：虽然不能正面求出问题的解，但如果能够知道解的范围，就可以将所有可能的解逐一代入问题中进行验证，如果某个解满足问题中所有的限定条件，那么它就是一个正确的解。二、枚举法实例1、百钱买百鸡题目百鸡买百钱是我国古书《算经》中的数学问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？分析针对x、y、z所有可能的取值逐一测试，使上述二个方程同时成立的x、y、z组合就是要求的解。在测试之前，需要先确定x、y、z的最大取值范围，如下：x的取值范围是0～100/5，y的取值范围是0～100/3，z的取值范围是0～3*100。程序见课本说明注意到鸡翁、鸡母、鸡雏总共100只，一旦确定鸡翁x和鸡母y的数值，鸡雏便只能购买100-x-y只。这样，我们就不需要枚举x、y、z的每一种组合，而只需要枚举x、y的每一种组合即可，从而避免了大量无意义的枚举。2、火柴棒等式题目给你n根火柴棒，你可以拼出多少个形如A+B=C的等式？等式中的A、B、C是用火柴棒拼出的整数（若该数非零，则最高位不能是0）。用火柴棒拼数字0～9的拼法如下图所示：注意：①加号与等号各自需要两根火柴棒；②如果A≠B，则A+B=C与B+A=C视为不同的等式（A,B,C≥0）；③n根火柴棒必须全部用上。分析本题的思路为：①计算某个数字所需火柴棒数量先将拼出数字0～9需要用到的火柴棒数量存进数组a里，然后再写一个函数，它能利用数组a求出拼出任意数字x所需的火柴棒数量。②找出使等式成立的A、B、C组合先枚举A和B的取值，并利用C=A+B计算出C。再计算出拼出A，B，C所需的火柴棒数之和，若它等于n−4，那么就算找到了一组合法解。③A、B的取值范围拼出数字1所需的火柴棒数最小，只需要2根。A最多是3位数。同理，B也最多是3位数，即A、B的取值均不超过1000。程序见课本。三、思维开拓这些题目在自洛谷网站，供上课学生们对其解法进行讨论。1、比例简化【题目描述】在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有1498人，反对的有902人，那么赞同与反对的比例可以简单的记为1498:902。不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。现给出支持人数A，反对人数B，以及一个上限L，请你将A比B化简为A’比B’，要求在A’和B’均不大于L且A’和B’互质（两个整数的最大公约数是1）的前提下，A’/B’≥A/B且A’/B’-A/B的值尽可能小。【数据说明】对于100%的数据，1≤A≤1,000,000，1≤B≤1,000,000，1≤L≤100，A/B≤L。2、回文日期【题目描述】在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。牛牛习惯用8位数字表示一个日期，其中，前4位代表年份，接下来2位代表月份，最后2位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表示方法不会相同。牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。现在，牛牛想知道：在他指定的两个日期之间包含这两个日期本身，有多少个真实存在的日期是回文的。一个8位数字是回文的，当且仅当对于所有的i(1≤i≤8)从左向右数的第i个数字和第9-i个数字（即从右向左数的第i个数字）是相同的。例如： 对于2016年11月19日，用8位数字20161119表示，它不是回文的。 对于2010年1月2日，用8位数字20100102表示，它是回文的。 对于2010年10月2日，用8位数字20101002表示，它不是回文的。【输入格式】两行，每行包括一个8位数字。第一行表示牛牛指定的起始日期。第二行表示牛牛指定的终止日期。保证date1和date2都是真实存在的日期，且年份部分一定为4位数字，且首位数字不为0。保证date1—定不晚于date2。【输出格式】一个整数，