(
课件网) 4.3非数值计算 第 4 单元 学习目标 4.3非数值计算 ★了解二分思想、递归思想 ★运用二分算法解决实际问题 新课导入 在上节课中我们了解到了数值计算，思考一下，除了数值外，我们哪些数据属于非数值呢？ 非数值数据主要包括字符数据、图形、图像、声音等。这些数据通常用于表示事物现象的属性或类别。 中文字符、英文字符、数字字符和其他ASCⅡ字符。 非数值计算 非数值计算算法主要用于处理事务领域的问题,如排序、查找等。 二分查找 二分查找又称折半查找 ，它是一种效率较高的查找方法。该方法主要将数列有序排列，采用跳跃式的方式查找数据。 原理：以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。 注意：二分查找所查找的序列必须是有序的。 二分查找 例如：我们定义一个1-9的列表，需要找到3这个元素，怎么用二分查找法实现？ 首先会找到最中间的元素，是5，然后判断5这个元素大于3还是小于3 ，很明显5大于3，那么3这个元素就在5之前 1 2 3 4 5 6 7 8 9 mid left right 二分查找 例如：我们定义一个1-9的列表，需要找到3这个元素，怎么用二分查找法实现？ 接下来会从2这个元素开始判断，2小于3，那么3肯定在2之后 1 2 3 4 5 6 7 8 9 mid left right 二分查找 完成书本113页翻页问题代码： flag1<=flag2: (flag1+flag2)//2 step=step+1 二分查找 完成书本113页翻页问题代码： flag1=mid-1 flag2=mid+1 递归 递归：在函数内部调用自己的函数。 设计递归函数需要遵循以下步骤： 1.确定递归函数的终止条件。这是递归函数停止调用自身并返回结果的条件。 2.定义递归函数的基本情况。这是递归函数可以直接解决的小问题，通常与终止条件相关。 递是去，归是回，一去一回是递归 递归 递归：在函数内部调用自己的函数。 递是去，归是回，一去一回是递归 递归 实例：使用递归函数实现任意数n的乘阶。 实现代码 递归 实例：使用递归函数实现任意数n的乘阶。 实现代码 代码解析: 去的过程: n = 5 return jiecheng(n-1) * n => jiecheng(4) * 5 n = 4 return jiecheng(n-1) * n => jiecheng(3) * 4 n = 3 return jiecheng(n-1) * n => jiecheng(2) * 3 n = 2 return jiecheng(n-1) * n => jiecheng(1) * 2 n = 1 return 1 代码解析: 回的过程: n = 2 return jiecheng(1) * 2 => 1 * 2 n = 3 return jiecheng(2) * 3 => 1 * 2 * 3 n = 4 return jiecheng(3) * 4 => 1 * 2 * 3 * 4 n = 5 return jiecheng(4) * 5 => 1 * 2 * 3 * 4 * 5 递归 递归：在函数内部调用自己的函数。 递归函数的特点： 1. 递归函数可以解决复杂的问题，特别适用于可以被分解为相似子问题的情况。 2. 递归函数的实现需要注意基本情况的定义，以避免无限递归导致的程序崩溃。 3. 递归函数的运行效率可能较低，因为它需要重复执行相同的计算。 迭代与递归的关系 递归与迭代的对比：递归和迭代之间的关键区别在于问题的解决方式和性能。 递归通过将问题分解为子问题并递归调用自身来解决问题。这通常更容易理解，但可能导致性能问题。 迭代通过明确的循环结构和终止条件来解决问题，通常更高效。然而，它可能需要更多的代码和难以理解。 迭代与递归的关系 选择递归还是迭代通常取决于问题本身和性能需求： 使用迭代：当性能是主要关注点，或者问题可以更自然地用迭代描述时，可以选择迭代。 使用递归：当问题的结构本身具有递归性质，或者递归更容易理解和实现时，可以选择递归。 谢谢聆听 ... ...
