4.3 非数值计算（第一课时）课件-2020-2021学年高中信息技术教科版（2019）必修1

非数值计算 第一课时 第 4 单元 4.3 学习目标 ★运用合适的算法形成解决问题的方案。 ★了解算法设计中的分治思想，并运用二分查找解决实际问题。 ★体验递归算法，并结合具体问题开展编程实践。 在数值计算中，我们更多考虑的是“数” ，但计算应该是一个更广泛的领域。计算的对象可以是自然界和人类社会的一切事物。更确切地说，计算的对象可以是某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思维过程。如果说数值计算主要探讨数学问题的话，那么非数值计算更多探讨＂ 算法” 问题。 许多程序设计问题的解决，要依靠标准算法和现成的模型，更需要编程者开阔思路，提出一些新颖、巧妙的算法，或者设计出一些独特的数据结构来支撑和实现算法。在解决非数值类计算问题时，一些基础的思维方式可以借鉴，如分治、递归、解析等。 活动 统计查字典次数 查汉字、查单词、查成语等查字典的活动，早已成为我们学习生活的部分。假设一本字典大约500页，目标信息在第269页。请记录你翻页过程，和同学们比比，看谁翻的次数最少。 次数 翻至页码 下一步决策 第一次 250 第二次 第三次 第四次 第五次 …… 有的同学翻得特别快，他们用了什么方法呢？原来看似普通的翻字典，不仅是一门技术， 更是一种能力，是算法思想的体现。 分治策略 分治的设计思想，是将个难以直接解决的大问题，分割成些较小的同类问题，各个击破，最终达到解决问题的目的。 二分查找实际上一就是分治策略的种典型运用。 A B C D E F G H I 需要解决的问题 二分查找 二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。 每一次比较后可以将查找区域缩小一半。 第一次分割 第二次分割 第三次分割 需要解决的问题 在翻页过程中借助两个书签，划定目标所属范围，然后翻到两个书签的中间位置。每次目标区域都更新为原来的“二分之一”，当数据范围缩小到只有1个数的时候肯定能得到问题的解。1000以内的页码，最多翻10次肯定能找到解。 目标信息在第269页。 第0页 第1000页 第0页 第500页 第250页 第500页 第250页 第375页 第250页 第312页 有