专题18 简单遍历算法 课件-2022届高三信息技术选考总复习

专题18 简单遍历算法 1.在查找连续的数字串、多个英文单词、多个区间、压缩字符串等问题时，可以把系列看成是____个小段组成的，每个小段有______位置和______位置。在此类题目解题时，关键把握每一段(每个区间)的开始位置和结束位置。在专题15字符串处理章节中，已经学习了如何找出简单遍历过程中3条线索，第2线索也可以用循环结构来实现区间的开始位置和结束位置元素的遍历。 2.采用双重遍历是对一维数组同时扫描____个元素(开始位置和结束位置)，并且关注这两个元素之间的关系。以计算数组a中28，19，54，36，21共5个数排名为例，找出大于第i个数的个数k(用数组pm(1 To 5)来记录)，那么第i个数的排名为k＋1。方法一：从第1个数开始，与全部数据逐一进行比较，计算第1个数的排名，接着第2个数与全体数据进行比较，计算排名，因此每趟的比较区间是[1，5]。方法二：从第1个数开始，与他后面的数a(j)进行比较，如果该数小于后面的数，将pm(1)将增加1，否则pm(j)将增加1。在计算第j个元素排名时，他已经与前面数进行了比较且记录比较结果，因此不需要再次与前面的数据进行比较，第i个数的比较范围是[i＋1，5]。 开始 结束 多 两 2 3.简单排序即为这种双重遍历的典型例子，是后面将复习的内容，主要是明确查找区间两个位置的重要性。冒泡排序：前后两个元素之间进行比较与交换；选择排序：当前元素与当前为止的最小(或最大)元素进行比较与交换；插入排序：当前元素与前面(已经有序的元素)依次比较与交换。该种范式是循环结构内嵌套一个循环结构，要注意内循环的开始位置和结束位置，即左边界和右边界。 第i趟排序算法 左边界 右边界 从后往前冒泡 i n 从前往后冒泡 1 n－i＋1 选择排序 i＋1 n 插入排序 1 i－1 4.对分查找算法也涉及到左右边界问题。对分查找是在区间[i，j]范围内查找一个中间位置m的值a(m)，与要查找的数key比较。当key不等于a(m)时，如果在左边的半个区间，调整右边界为m－1，如果在右边的半个区间，调整左边界为m＋1，继续查找，直到这个数找到或者区间不存在。 5.尺取法(顾名思义，像尺子一样取一段)，即选取区间的______端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数