资源简介

(共13张PPT)
第4单元　计算与问题解决
4.3非数值计算
必修1　数据与计算
目
录
1
知识梳理
2
知识拓展
3
巩固练习
1.分治策略
分治的设计思想,是将一个难以直接解决的大问题,分割成一些较小的同类问题,各个击破,最终达到解决问题的目的。二分查找实际上就是分治策略的一种典型运用。
2.二分查找
二分查找又叫折半查找,该方法主要将数列有序排列,采用跳跃式的方式查找数据。它是一种高效的查找方法,可以明显减少比较次数,提高查找效率。在一个有n个元素的有序序列中,利用二分查找大约需要lo次。二分法查找的前提条件是被查找的数据必须是有序的。
查找的基本算法有：顺序查找、二分查找、分块查找和哈希查找等。
3.递归
直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。
在数学与计算机领域中,递归函数是指用函数自身来定义该函数的方法。如著名的斐波那契数列“1,1,2,3,5,8,13,…”,可以递归定义为：
F（n）＝
递推关系是递归的重要组成,而边界条件是递归的另一要素,它保证递归能在有限次的计算后得出结果,而不会产生无限循环的情况。
递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言,递推与回归两者缺一不可。结合分治策略,递归也可用“分”“治”“合”三个字概括。
（1）分：将原问题分解成k个子问题。
（2）治：对这k个子问题分别求解。如果子问题的规模仍然不够小,则将其再分解为k个子问题,如此进行下去,直到问题足够小时,就很容易求出子问题的解。
（3）合：将求出的小规模问题的解合并为一个更大规模问题的解,自下而上逐步求出原问题的解。
·迭代与递归的关系
迭代算法与递归算法都需要重复执行某些代码,两者既有区别又有着密切的联系。
迭代是重复反馈过程的活动,其目的通常是逼近所需目标或结果。递归是重复调用函数自身。
递归中,遇到满足终止条件的情况时逐层返回；迭代则通常使用计数器结束循环。
迭代程序可以转换成等价的递归程序。
1.“大事化小、小事化了”体现出的问题求解的思想是（　C　）。
A.递推法 B.穷举法 C.分治法 D.归纳法
2.二分查找算法利用的算法思想是（　A　）。
A.分治策略 B.穷举法
C.贪心法 D.回溯法
3.对线性表进行二分查找时,要求线性表必须（　B　）。
A.以顺序方式存储 B.以顺序方式存储,且数据元素有序
C.以链接方式存储. D.以链接方式存储,且数据元素有序
C
A
B
4.对于数列3,8,11,15,17,19,25,30,44,采用“二分查找”法查找“8”时,需要查找多少次？ （　A　）。
A.3 B.4 C.5 D.6
5.下面关于递归说法中正确的是（　B　）。
A.函数间接调用自己不是递归
B.递归出口和递归关系是递归函数编写的关键
C.递归函数的嵌套调用次数没有限制
D.递归函数的执行效率优于非递归函数
A
B

展开更多......

收起↑