大学计算机基础-基于计算思维课件 第10章 算法思维与应用10.2 蛮力算法

大学计算机基础——基于计算思维（Windows10+Office2016）第10章算法思维与运用10.2.1简单蛮力法10.2蛮力算法问题1简单蛮力算法某国际型运动会开幕式准备策划一个大型团体操，人数在50~500之间，但根据队形变化要求，每10人排成一行要余2人领操，每12人排成一行要余4人领操，每4人排成一行不多不少，问需要的人数可以有多少种方案。1.问题分析既然已知所有可能解的范围为50~500，那么就从下限50开始判断其是否满足所有要求（称为约束条件），是即输出，不是就不输出，同理再逐一判断51、52、53直至上限500是否满足要求，即可求出所有的方案。问题1简单蛮力算法2.算法实现①在所有可能解的范围50~500中逐一判断，明显用循环结构实现。设一个循环变量number初值为50，终值为500，且按步长值为1递增，据此首先构建一层循环结构。初值为50终值为500步长值为1递增问题1简单蛮力算法2.算法实现②循环体内判断number是否满足所有要求，满足则输出number的值，否则不输出。同时满足3个条件可用逻辑运算符and连接，3个条件类似，都是判断number除以某数的余数，可用求余运算符mod。判断number是否满足所有要求问题1简单蛮力算法2.算法实现最后完整的Raptor流程图如图所示。问题1简单蛮力算法3.运行结果问题1简单蛮力算法4．问题总结上述求解问题的算法是直接根据问题的描述，从可能的集合中一一枚举各个元素，用给定的约束条件判定哪些是问题的解，哪些不是问题的解，这种最简单的“justdoit”的设计策略称为蛮力法。力蛮法计算机的“计算能力”大学计算机基础——基于计算思维（Windows10+Office2016）第10章算法思维与运用10.2.2复杂蛮力法10.2蛮力算法问题2复杂蛮力算法刘老师带了41名同学去公园划船，共租了10条船。每条大船坐6人，每条小船坐4人，问大船、小船各租几条则刚好坐下所有人？1.问题分析对于此问题，我们可以马上列出一个二元一次方程组：

small+big=104×small+6×big=42用消元法可以很快解出该方程组问题2复杂蛮力算法但怎么让计算机来解这个方程组呢？用蛮力法试试。①确定穷举对象小船small

大船big②确定穷举范围0~100~10③确定约束条件small+big=104×small+6×big=42④穷举可能的解从（0，0）开始，然后依次判断（0，1）、（0，2）、（0，3）…（0，10），（1，0）、（1，1）…(10，10)是否同时满足两个约束条件问题2复杂蛮力算法2．算法实现①用循环结构内再嵌套循环结构来实现。此问题中，用small作为外循环还是用big作为外循环，都不影响结果。假设用small作外循环，big作内循环：small+big=104×small+6×big=42当small=0时，big分别从0取到10，判断每种组合是否满足两个约束条件；然后再取small=1，big又从0取到10，再判断；最后small=10时，big又从0取到10，再判断，这样就能穷举所有可能的解。问题2复杂蛮力算法2．算法实现操作实现时，则应先搭好完整的外层循环结构（small从0到10），然后在其内的循环体内再搭建内层循环（big从0到10），如图所示。问题2复杂蛮力算法2．算法实现②在内层循环体内（big层内）再判断是否同时满足2个约束条件，是则输出small和big的值，否则不输出，如图所示。问题2复杂蛮力算法3．运行结果问题2复杂蛮力算法4．算法优化本例中为了提高该算法的时间效率，可以减少穷举对象和缩小穷举范围。因为大小船只总数是固定的，所以只要以big为穷举对象，根据方程1的约束条件就可得small=10-big；small=10-bigsmall+big=10问题2复杂蛮力算法4．算法优化再根据方程2可将big的穷举范围缩小为从0到7，这样用一个单循环（big从0到7）就可实现了。4×small+6×big=42Big≤7问题2复杂蛮力算法4．算法优化循环体内首先由big计算出small，即small=10-big，然后只要判断是否满足另一个约束条件：4×small+6×big=42即可。