4.3非数值计算 课件-高中信息技术同步备课系列（教科版2019 必修1）.pptxVIP

4.3非数值计算第4单元

学习目标4.3非数值计算★了解二分思想、递归思想★运用二分算法解决实际问题

新课导入在上节课中我们了解到了数值计算，思考一下，除了数值外，我们哪些数据属于非数值呢？非数值数据主要包括字符数据、图形、图像、声音等。这些数据通常用于表示事物现象的属性或类别。中文字符、英文字符、数字字符和其他ASCⅡ字符。

非数值计算非数值计算算法主要用于处理事务领域的问题,如排序、查找等。

二分查找二分查找又称折半查找，它是一种效率较高的查找方法。该方法主要将数列有序排列，采用跳跃式的方式查找数据。原理：以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。注意：二分查找所查找的序列必须是有序的。

二分查找例如：我们定义一个1-9的列表，需要找到3这个元素，怎么用二分查找法实现？首先会找到最中间的元素，是5，然后判断5这个元素大于3还是小于3，很明显5大于3，那么3这个元素就在5之前123456789midleftright

二分查找例如：我们定义一个1-9的列表，需要找到3这个元素，怎么用二分查找法实现？接下来会从2这个元素开始判断，2小于3，那么3肯定在2之后123456789midleftright

二分查找完成书本113页翻页问题代码：flag1=flag2:(flag1+flag2)//2step=step+1

二分查找完成书本113页翻页问题代码：flag1=mid-1flag2=mid+1

递归递归：在函数内部调用自己的函数。设计递归函数需要遵循以下步骤：1.确定递归函数的终止条件。这是递归函数停止调用自身并返回结果的条件。2.定义递归函数的基本情况。这是递归函数可以直接解决的小问题，通常与终止条件相关。递是去，归是回，一去一回是递归

递归递归：在函数内部调用自己的函数。递是去，归是回，一去一回是递归

递归实例：使用递归函数实现任意数n的乘阶。实现代码

递归实例：使用递归函数实现任意数n的乘阶。实现代码代码解析:去的过程:n=5returnjiecheng(n-1)*n=jiecheng(4)*5n=4returnjiecheng(n-1)*n=jiecheng(3)*4n=3returnjiecheng(n-1)*n=jiecheng(2)*3n=2returnjiecheng(n-1)*n=jiecheng(1)*2n=1return1代码解析:回的过程:n=2returnjiecheng(1)*2=1*2n=3returnjiecheng(2)*3=1*2*3n=4returnjiecheng(3)*4=1*2*3*4n=5returnjiecheng(4)*5=1*2*3*4*5

递归递归：在函数内部调用自己的函数。递归函数的特点：1.递归函数可以解决复杂的问题，特别适用于可以被分解为相似子问题的情况。2.递归函数的实现需要注意基本情况的定义，以避免无限递归导致的程序崩溃。3.递归函数的运行效率可能较低，因为它需要重复执行相同的计算。

迭代与递归的关系递归与迭代的对比：递归和迭代之间的关键区别在于问题的解决方式和性能。递归通过将问题分解为子问题并递归调用自身来解决问题。这通常更容易理解，但可能导致性能问题。迭代通过明确的循环结构和终止条件来解决问题，通常更高效。然而，它可能需要更多的代码和难以理解。

迭代与递归的关系选择递归还是迭代通常取决于问题本身和性能需求：使用迭代：当性能是主要关注点，或者问题可以更自然地用迭代描述时，可以选择迭代。使用递归：当问题的结构本身具有递归性质，或者递归更容易理解和实现时，可以选择递归。

谢谢聆听