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

五、经典算法应用

学科大概念二：算法目录五、经典算法应用(一)解析算法(二)枚举算法(三)二分查找算法(四)迭代算法(五)递归算法(六)算法的优劣

五、经典算法应用信息技术

解析算法是指用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。解析法解决问题的步骤：分析问题、抽象建模、解析表达式、解决问题。解析式是用运算符号和括号把数字和字母按一定规则连接成式子。比如利用海伦公式求三角形的面积等。知识梳理(一)解析算法

知识梳理答案：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轮0941029Right＝Mid－1第2轮031107Left＝Mid＋1第3轮23210＝10查找成功！

知识梳理注：①二分查找的前提条件是被查找的数据必须是有序的。②二分查找中左、右边界的设置和调整很关键。此外，要注意二分查找条件的限定(LeftRight)。③二分查找的时间复杂度：对长度为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：