经典算法应用同步复习课件-2024-2025学年教科版（2019）高中信息技术必修一

五、经典算法应用学科大概念二：算法目录五、经典算法应用(一)解析算法(二)枚举算法(三)二分查找算法(四)迭代算法(五)递归算法(六)算法的优劣五、经典算法应用信息技术解析算法是指用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。解析法解决问题的步骤：分析问题、抽象建模、解析表达式、解决问题。解析式是用运算符号和括号把数字和字母按一定规则连接成式子。比如利用海伦公式求三角形的面积等。知识梳理(一)解析算法知识梳理答案：x＝(v*v－v0*v0)/(2*a)或x＝(v**2－v0**2)/(2*a)枚举算法又称穷举法，是一种最为直接，实现最为简单，同时又最为耗时的解决问题的算法思想。通常采用“循环＋判断”把所有可能的答案一一列举，合适就保留，不合适就丢弃。•枚举算法的三要素：枚举对象、枚举范围和判断条件。•枚举解决问题的一般结构：循环＋判断。其优势在于正确性容易证明。•枚举算法的经典应用：百钱百鸡和模糊数字。知识梳理(二)枚举算法知识梳理【试一试】一张单据上有一个5位数的编码，因为保管不善，其百位数字已经变得模糊不清，即为19？88，但知道这个数是2和3的倍数，有________个这样的数。答案：3解析：百位上的数字可能为0—9十个数字，因为该数的末尾为8，所以肯定是2的倍数，只要对百位上的数据进行枚举(0—9)，如果该5位数各位数字之和为3的倍数，则满足条件，满足条件的数字是1，4和7。经穷举，这样的数有19188，19488，19788三个数。二分查找又叫折半查找，主要将数列有序排列，采用跳跃式的方式查找数据。二分查找是一种高效的查找方法，可以明显减少比较次数，提高查找效率。以递增数列为例，先以中间位置的元素作为比较对象，如果要找的元素小于该中间位置的元素，则待查序列缩小为左半部分，如果大于该中间位置的元素，则为右半部分。每次比较后都可以将查找区间缩小一半，直至找到。知识梳理(三)二分查找算法知识梳理例如：在列表nums＝[1，7，10，13，29，37，57，71，97，100]中查找x＝10过程如下表所示。查找x＝10左边界Left右边界Right中间位置Mid比较x与nums[Mid]相应操作第1轮09410<29Right＝Mid－1第2轮03110>7Left＝Mid＋1第3轮23210＝10查找成功！知识梳理注：①二分查找的前提条件是被查找的数据必须是有序的。②二分查找中左、右边界的设置和调整很关键。此外，要注意二分查找条件的限定(Left<Right)。③二分查找的时间复杂度：对长度为n的有序线性表中进行二分查找，所需时间最长为O(log2n)。迭代法也称辗转法，每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果用来作为下一次迭代的初始值，通常是为了接近并到达所需的目标或结果。使用迭代算法解决问题，有三个关键步骤：①确定迭代变量；②建立迭代关系式；③对迭代过程进行控制。知识梳理(四)迭代算法典型例题【例1】猴子吃桃：一只猴子摘了若干桃子，每天吃现有桃子数的一半多一个，到第6天时就只剩下一个桃子，求原来一共有多少个桃子？#不要更改源程序结构，删除原题里的①②③。填写正确的代码，完善程序。x＝1foriinrange(2，__①__)：x＝__②__print(x)答案：①7②(x＋1)*2解析：设第n天的桃子为xn，就是前一天的桃子的二分之一减去一，即xn＝xn－1/2－1，则使用后一天的桃子数推出前一天的桃子数的迭代关系式为xn－1＝(xn＋1)*2，现已知第6天的桃子数，求解第1天的桃子数，往前推算5次即可，所以循环次数为5次。递归是用于设计算法的一种思想方法，也是计算机科学中一个十分重要的概念。它通常是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，通过构建递归关系式，将解决小问题作为解决大问题的入口，由此，大问题也就“迎刃而解”。知识梳理(五)递归算法知识梳理1.一个问题能够适用递归方法解决，必须符合两个条件：(1)一个规模较大的问题可以分解为若干性质相同的规模较小的问题，这些规模较小的问题仍然可以进一步分解，分解出的新问题的解法和原问题的解法相同，只是处理对象的规模不同。(2)必须有一个明确的结束递归的条件，不得无限递归。递归不仅仅是设计算法的一种思想方法，也是一种简化问题的思维方式。典型例题【例2】已知n！＝1*2*3*......*(n－1)*n，利用递归法求5！。#不要更改源程序结构，删除原题里的①②③。填写正确的代码，完善程序。x＝1deff(n)：ifn＝＝1：return__①__else：return__②__print(”5！＝”，__③__)典型例题答案：①1②n*f(n－1)③f(5)解析：递归算法有重要的特点：(1)把规模较大的问题分解为若干性质相同的小问题，构建递归关系式f(n)＝n*f(n－1)；(2)必须有一个结束条件，当n＝1时，n！＝1；(3)递归包括递推和回归两个过程(具体过程如图所示)。知识梳理2.迭代和递归的关系①相同点：迭代算法与递归算法都需要重复执行某些代码。②不同点：迭代是重复反馈过程的活动，其目的是逼近所需目标或结果，通常使用计数器结束循环。递归是重复调用函数自身，遇到满足终止条件的情况时逐层返回。知识梳理③迭代程序和递归程序可以等价转换，以计算斐波那契数列第n项的值为例，程序间的转换如下表所示：递归迭代deffib1(n)：#递归求Fibonacci数列的第n个数

ifn＝＝1orn＝＝2：

return1else：

returnfib1(n－1)＋fib1(n－2)deffib2(n)：#迭代求Fibonacci数列的第n个数f1＝f2＝1foriinrange(3，n＋1)：

f1，f2＝f2，f1＋f2returnf2同一问题可用不同算法解决，而一个算法的质量优劣将影响到程序的效率。算法分析的目的在于选择合适算法和改进算法；一个算法的评价主要从时间复杂度和空间复杂度来考虑。1.时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n的函数f(n)，算法的时间复杂度也因此记做T(n)＝Ο(f(n))，因此，问题的规模n越大，算法执行的时间的增长率与f(n)的增长率正相关，称作渐进时间复杂度(AsymptoticTimeComplexity)。知识梳理(六)算法的优劣知识梳理2.空间复杂度算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。3.正确性算法的正确性是评价一个算法优劣的最重要的标准。知识梳理4.可读性算法的可读性是指一个算法可供人们阅读的容易程度。5.健壮性健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。典型例题【例3】素数：(1)素数又叫质数，是指除了1与本身以外没有其他因数的数，2是自然数中最小的素数。(2)请填空完善该程序，实现功能：键盘输入一个自然数n(n<1000)，输出1至n范围内的所有素数。n＝int(input(”输入自然数n＝”))foriinrange(2，n＋1)：#枚举范围内的每一个数字flag＝0forjinrange(2，__①__)：if__②__：#判断i是否为素数flag＝1__③__#退出循环ifflag＝＝0：print(i，end＝′′)典型例题答案：①i或int(i**0.5)＋1②i%j＝＝0③break解析：本程序通过穷举法判断2—n(使用变量i枚举)中素数，判断i是否为素数的标准是2—(i－1)(使用变量j枚举)均不是i的约数，若j为i的约数，则标识flag赋值为1，并跳出循环(break)，所以②的答案为i%j＝＝0，③的答案为break，①的答案为i，这个程序的运行时间为3*10－7s。程序优化：因为一个数的因数是成对出现的，其中一个因数在开方后的前面，一个在开方后的后面，所以只需判断它前面的数就可以了，这样①的答案可以为int(i**0.5)＋1，这样修改之后程序的运行程序为1*10－7s，从时间复杂度角度考虑，第二个算法更优。程序进一步优化方案：因为3—n中，有近一半的偶数，除2以外，其他的偶数均不为素数，所以可以先去除偶数再进行判断，但是该方案需要修改程序结构，不采用。典型例题【例4】输入已知三角形三条边的长a，b，c，利用海伦公式s＝sqrt(p*(p－a)*(p－b)*(p－c))[其中p为半周长，即p＝(a＋b＋c)/2]求三角形面积。该算法属于()A.枚举算法B.递归算法C.迭代算法D.解析算法答案：D解析：本题考查的是解析算法。解析算法为在分析具体问题的过程中，抽取出一个数学模型，用若干个解析表达式表示，再计算表达式来实现问题的求解。而本题利用海伦公式计算三角形的面积即为解析算法。典型例题【例5】下列适合使用枚举算法解决的是()A.计算三角形的面积

B.判断2023年是否为闰年C.找出1000以内所有的素数D.计算班级男生的平均身高答案：C解析：本题考查的是枚举算法。枚举算法又称为穷举法，通过把所有可能的答案一一列举，逐一判断每个可行解是否符合要求，从而得到问题的答案。选项C就是通过枚举法一一判断1000以内的每一个数是否为素数，从而解决问题。典型例题【例6】报名参加跳远比赛的某5位同学的编号为5，11，25，36，50，利用二分查找法查找36号同学的过程中，依次被访问到的编号为()A.5，11，25，36

B.25，36

C.11，36D.11，25，36答案：B解析：本题考查的二分查找算法。初始状态：左边界为0，右边界为4，中间值的下标为(0＋4)//2＝2，对应的值为25；经过判断25<36，调整左边界为3，右边界依然为4，中间值的下标为(3＋4)//2＝3，对应的值正好是36，因此访问的编号顺序为25，36。典型例题【例7】________是重复反馈过程的活动，其目的通常是逼近所需目标或结果。________是直接或间接地调用函数自身。()A.枚举递归

B.递归迭代

C.迭代递归

D.递归迭代答案：C解析：本题考查的知识点是迭代和递归的区别。迭代是重复反馈过程的活动，其目的是逼近所需目标或结果，通常使用计数器结束循环。递归是重复调用函数自身，遇到满足终止条件的情况时逐层返回。所以选项C为正确答案。典型例题【例8】已知递归式为F(n)＝F(n－1)＋2，且F(1)＝5，则当n＝3时，F的值为()A.7B.9C.11D.13答案：B解析：本题考查的知识点是递归。根据递归式可以知道F(3)＝F(2)＋2＝F(1)＋2＋2＝5＋2＋2＝9，所以选项B为正确答案。同步训练1.numpy是一个科学计算包，其中包含很多数学函数，以下哪一个函数返回最大值()A.sum函数

B.sqrt函数C.max函数

D.arange函数2.四叶玫瑰数是指四位数各位上的数字的四次方之和等于本身的数。如果要求出所有的玫瑰花数，下列算法最合适的是()A.枚举法

B.查找法C.解析法

D.排序法CA同步训练3.走楼梯的问题可以利用迭代算法来解决，解决该问题的正确顺序应该是()①建立迭代关系式②让迭代过程无休止地重复执行③对迭代过程进行控制④确定迭代变量A.④①③②

B.①②③C.④①③

D.①④③C同步训练D同步训练5.运用分治策略将一个难以直接解决的大问题分割成规模较小的子问题分别解决，最终达到解决大问题的目的。这要求原问题和子问题的()A.问题性质相同，问题规模相同B.问题性质不同，问题规模相同C.问题性质相同，问题规模不同D.问题性质不同，问题规模不同C同步训练6.小明和小华玩猜数字的游戏，所猜数字不超过800，小明首先猜400，小华说大了，小明又猜200，当小华再次说大了，小明猜100，当小华说小了，小明猜150，以此类推，直到猜到正确的数字。上述方法中蕴含的算法思想是