高中信息技术教科版必修1课件4-3非数值计算（第一课时）

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

＃查找次数加1 ifmid>x: flag2=mid-1 #有边界前移 elifmid<x: flag1=mid+1 #左边界后移 else: break ＃恰好找到目标数据，退出循环print(“查询次数为：”，step) #输出次数如果输入的数据不在范围内，会出现什么结果呢？程序还需要在哪些地方进行完善？大家一起来试试吧。x=int(input(“请输入要查找的数据：＂））step=0 ＃记录查找次数flagl=l ＃目标区域左边界flag2=1000 ＃目标区域右边界ifx>flag2orx<flag1:while(flag2-flag1>1) ＃区间数据范围小于1则结束循环 mid=（flag1+flag2)/2 ＃中间值 step=step+1

＃查找次数加1 ifmid>x: flag2=mid #有边界前移 elifmid<x: flag1=mid #左边界后移 else: break ＃恰好找到目标数据，退出循环print(“查询次数为：”，step) #输出次数else: print(“查询超出范围。”)random包的randint()函数可以生成某个范围内的随机数。活动应用“二分查找”，找出1-1000之间的某个数importrandom

x=random.randint(1,1000)

while0<x<1000:

y=int(input("请输入这个数："))

ifx<y:

print("大了")

elifx>y:

print("小了")

else:

print("就是",x)

breakrandom包可以称为随机包，它有如下函数：random.randint(1,10)#产生1到10的一个整数型随机数random.random()#产生0到1之间的随机浮点数random.uniform(1.1,5.4)#产生1.1到5.4之间的随机浮点数，区间可以不是整数random.choice('tomorrow')#从序列中随机选取一个元素random.randrange(1,100,2)#生成从1到100的间隔为2的随机整数练一练尝试用二分法求解x3-x2+x-1=0操作提示：令f(x)=x3-x2+x-1，针对有解的单调区间(a,b)，取x。=（a+b)/2:若f(a)*f(x。)＜0，则f(x)在(a,x。)内有解；若f(x。）*f（b)<0，则f(x)在(x。,b)内有解；若|f(x。)|＜10-6，则x。为方程的解。巩固提升1．二分查找又叫_________，该方法主要将数列_________排列，采用___________的方式查找数据。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。2．递增数列用二分法查找时，先以________位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列_________为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。巩固提升3.二分法查找的前提条件是被查找的数据__________的。4.结合分治策略，递归也可以用___________三个字概况。分:将原有问题______成K个子问题;治:对这K个子问题______。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。合:将求出的小规模问题的解_______为一个更大规模问题的解，自下而上逐步求出原问题的解。巩固提升5.二分查找又称折半查找，是一种应用于有序数列的高效查找算法。下列数列中适合二分查找算法的是()A.85 78 59 53 19 18B.67 62 68 41 1 7C.11 99 4 25 3 39D.43 71 78 81 6 5