1、教科版教科版 2019 信息技术必修信息技术必修 1 数据与计算数据与计算第第 4 单元计算与问题解决单元计算与问题解决 4.3 非数值计算教学设计非数值计算教学设计教材分析教材分析强调“项目任务活动”结构与核心素养达成的一体化设计思想，强调在项目的真实情境下，通过任务的达成，展开一系列活动，在活动过程中通过搭建思维支架，不断建构知识，发展思维，使得生活、学习、知识技能、思维发展浑然一体，最终促进学生核心素养的全面、均衡发展。“项目任务活动”式结构不是一个静态的结构，它反映了学生知识建构与思维生成的动态过程。知识建构、思维发展乃至核心素养的形成都是在特定情境中围绕活动而自然生成的。如果说本单元
2、 4.1 为模仿阶段，4.2 为形象思维阶段，4.3 就是抽象思维阶段。本项目的重点应是基本思想和方法的教学，要能够恰当地引导，就能够使学生准确地领悟思想，从而较好地掌握基本方法。分治是最常用的算法设计思想，查找是算法中最常见的操作，递归是算法在实现时的常用手段。本节我们将围绕项目“生活中的算法”展开学习，尝试用计算机的视角去解决实际问题。本项目主要包含“巧翻字典”和“玩转汉诺塔游戏”两个任务。任务一主要介绍分治中最经典的二分思想；任务二借助汉诺塔游戏重在介绍递归思想及算法实现。教学建议教学建议针对学生的认知水平及认知习惯，通过引导、启发、设问等方式，为学生设置真实项目或问题情境，在活动中为学
3、生知识建构关键点和思维生发关键点搭建思维支架，使学生在自主探究或解决问题的过程中产生较强的学习动机，在不断发现中习得知识、发展思维、提升能力。在该课程的教学方法上，应以程序设计的实例带动语言知识的学习，把程序设计当作科学方法的训练，把语言知识的应用作为技能的培养，全面推行“模仿形象思维抽象思维”三个由浅入深的阶段的教学。学生的主要活动是积极思考、广泛交流、主动探究。他们学到的不仅仅是新知识，更重要的是学会了解决问题的方法，知道了什么时候、在什么地方去应用所学的知识。任务一通过巧翻字典的情境引出二分查找的思想，分治的思想学生很容易理解，理解二分查找也不是难点，算法的实现需要给学生充足和时间和必要
4、的帮助。任务二汉诺塔问题，重点应落在对问题状态的描述及状态间的转移上。在 4.2 中回顾了函数的定义及调用方式，为递归函数设计做了很好的铺垫。教学目标教学目标1.运用合适的算法形成解决问题的方案。2.了解算法设计中的分治思想，并运用二分查找解决实际问题。3.体验递归算法，并结合具体问题开展编程实践。教学重点、难点教学重点、难点运用合适的算法形成解决问题的方案。算法设计中的分治思想，并运用二分查找解决实际问题。递归算法，并结合具体问题开展编程实践。教学方法教学方法讲授法，演示法，任务引导法教学过程教学过程第一课时第一课时引入引入在数值计算中，我们更多考虑的是“数”，但计算应该是一个更广泛的领域。
5、计算的对象可以是自然界和人类社会的一切事物。更确切地说，计算的对象可以是某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思维过程。如果说数值计算主要探讨数学问题的话，那么非数值计算更多探讨“算法”问题。数据是普遍存在的，甚至可以说对象即数据;对数据的分析、处理都属于计算的范畴。选择一个合适的算法，设计出平实、易读、易懂的程序，正确、高效地解决实际需求，是计算的本质。新课新课许多程序设计问题的解决，要依靠标准算法和现成的模型，更需要编程者开阔思路，提出一些新颖、巧妙的算法，或者设计出一些独特的数据结构来支撑和实现算法。在解决非数值类计算问题时，一些基础的思维方式可以借鉴，如分治、递归、
6、解析等。本节我们将围绕“生活中的算法”项目，尝试用“算法的眼睛”看待生活，用“算法的思维”去解决实际问题。本项目主要包含“巧翻字典”和“玩转汉诺塔游戏”两个任务。任务一巧翻字典任务一巧翻字典活动统计查字典次数活动统计查字典次数查汉字、查单词、查成语等查字典的活动，早已成为我们学习生活的一部分。假设一本字典大约 1000 页，目标信息在第 328 页。请在表 4.3.1 中记录你的翻页过程，和同学们比一比，看谁翻的次数最少。有的同学翻得特别快，他们用了什么方法呢?原来看似普通的翻字典，不仅是一门技术，更是一种能力，是算法思想的体现。分治策略分治策略 分治的设计思想，是将一个难以直接解决的大问题，
7、分割成一些较小的同类问题，各个击破，最终达到解决问题的目的。二分查找实际上就是分治策略的一种典型运用。二分查找二分查找 二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较查找的基本算对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。在一个有 n 个元素的有序序列中，利用二分查找大约需要 log2n次。但是，二分法查找的前提条件是被查找的数据必须是有序的。实践操作实践操作 在翻页过程中借助两个书
8、签，划定目标所属范围，然后翻到两个书签的中间位置。每次目标区域都更新为原来的“二分之一”，当数据范围缩小到只有 1 个数的时候肯定能得到问题的解。1000 以内的页码，最多翻 10 次肯定能找到解。有了翻字典的实际操作经验，我们来尝试完善下面的二分查找程序。x=int(input(请输人要查找的数据:)step=0#记录查找次数flag1=1#目标区域左边界flag2=1000#目标区域右边界while():#区间数据范围小于 1 则结束循环mid=#中间值#查找次数加 1if midx:#右边界前移elif midx:#左边界后移else:break#恰好找到目标数据，退出循环print(查
9、找次数为:,step)#输出次数问题：问题：如果输入的数据不在范围内，会出现什么结果呢?程序还需要在哪些地方进行完善?大家一起来试试吧。算法研究涉及计算机科学和数学中令人着迷的话题。面对海量数据的处理，算法选择得当，解决问题时便游刃有余;算法选择不当，则可能出现程序运行错误、运行时间长或占用空间大等问题。所有这些都促使我们深入学习，感悟化繁为简的编程魅力。if f(x0)=0:breakprint(解为:,x0)input(运行完毕，请按回车键退出.)5.计算“汉诺塔”游戏移动的次数。参考答案：def f(n):if n=0:return 0 else:return 2*f(n-1)+1x=i
10、nt(input(请输入塔的个数：)print(需要移动,f(x),次)input(运行完毕，请按回车键退出.)第二课时任务二玩转“汉诺塔”游戏活动剖析问题，设计游戏策略第二课时任务二玩转“汉诺塔”游戏活动剖析问题，设计游戏策略 “汉诺塔”游戏源于一个古老的印度传说。如图 4.3.1 所示，木板上有 A、B、C 三根杆，A 杆上有若干木盘，规定每次移动一个木盘，且小的木盘只能叠在大的木盘上面。请设计算法，用尽可能少的次数把所有木盘从 A 杆全部移到 C 杆上。要使移动次数尽可能少，必须排除无效移动。现在有 8 个木盘，不妨先以 3 个木盘为例，观察一下移动的过程。请在图 4.3.2 中 记录木
11、盘移动的过程。递归递归 递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。图 4.3.3 所示 就是递归的一-种形象表示。在数学与计算机领域中，递归函数是指用函数自身来定义该函数的方法。如著名的斐波那契数列“1，1,2,3,5,8，13，.”，以递归定义为2)(n2)-F(n+1)-F(n2)=n1=1(n=F(n)或 递推关系是递归的重要组成，而边界条件是递归的另一要素，它保证递归能在有限次的计算后得出结果，而不会产生无限循环的情况。面对一个大规模复杂问题的求解，递
12、归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归，二者缺一-不可。结合分治策略，递归也可用“分”“治”“合”三个字概括。(1)分:将原问题分解成 k 个子问题。(2)治:对这 k 个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为 k 个子问题，如此进行下去，直到问题足够小时,就很容易求出子问题的解。(3)合:将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。实践操作实践操作 移动 3 个木盘的方法是:根据木盘叠放规则，要使 A 杆上最大的木盘(记为 x)移动到 C杆上(子问题 1，如图 4.3.2 中的第 4 步)，
13、必须先把 x 上方的所有木盘移动到 B 杆上(子问题 2，如图 4.3.2 中的前 3 步)，然后再将 B 杆上所有的木盘移动到 C 杆上(子问题 3，如图 4.3.2 中的后 3 步)。3 个木盘的移动问题成功解决了，就可以解决更多木盘的移动问题了。将 n 个木盘从 A杆移动到 C 杆，需要借助中间的 B 杆。只要超过一个木盘，在移动过程中，总会存在起始杆、过渡杆及目标杆的问题。因此，定义函数时，用到了 4 个参数:hanoi(n,s,m,l)，n 表示需要移动的盘子数量，s 表示盘子的起始杆，m 表示中间过渡杆，l 表示目标杆，如图 4.3.4所示。让我们根据图示一起完善程序吧。def h
14、anoi(n,s,m,t):#定义一个函数,将 n 个木盘从 s 借助 m 移到 tif n=1:#当只有一个木盘时，直接从起始杆移动到目标杆print()else:#将前 n-1 个木盘借助 t 从 s 移到 mhanoi(,s,)print()#将最下面的木盘从 s 移到 t#将 m 上的 n-1 个木盘借助 s 移到 thanoi(,t)#主程序n=int(input(请输人木盘的个数:)#调用函数，将 n 个木盘从 A 借助 B 移动到 Chanoi(n,A,B,Cc)hanoi(n,s,m,t)hanoi(n-1,s,t,m)从 s 移到 thanoi(n-1,m,s,1)运行程序，
15、输入 3 个木盘，记录程序运行结果。将一个难以直接解决的大问题，分割成一些规模较小的同类问题，以便各个击破，分而治之，此为分治。分治与递归就像一-对孪生兄弟，经常同时应用在算法设计中，并由此产生了许多高效的算法。练习练习1.结合 4.2 的知识，计算“汉诺塔”游戏移动的次数。2.尝试用二分法求解 x3-x2+x-1=0。操作提示:令 f(x)=x3-x2+x-1,针对有解的单调区间(a,b),取 xo=(a+b)/2:若 f(a)*f(x0)0,则 f(x)在(a,x)内有解;若 f(xo)*f(b)0,则 f(x)在(Xo,b)内有解;若|f(x0)|1e-6:x0=(a+b)/2 if f(a)*f(x0)0:b=x0 if f(b)*f(x0)0:a=x0
