4.3非数值计算 课件-江苏省2025年1月普通高中学业水平合格性考试信息技术复习.pptxVIP

第4单元计算与问题解决4.3非数值计算必修1数据与计算

目录1知识梳理2知识拓展3巩固练习

1.分治策略分治的设计思想,是将一个难以直接解决的大问题,分割成一些较小的同类问题,各个击破,最终达到解决问题的目的。二分查找实际上就是分治策略的一种典型运用。

?

?

递推关系是递归的重要组成,而边界条件是递归的另一要素,它保证递归能在有限次的计算后得出结果,而不会产生无限循环的情况。递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言,递推与回归两者缺一不可。结合分治策略,递归也可用“分”“治”“合”三个字概括。（1）分：将原问题分解成k个子问题。（2）治：对这k个子问题分别求解。如果子问题的规模仍然不够小,则将其再分解为k个子问题,如此进行下去,直到问题足够小时,就很容易求出子问题的解。（3）合：将求出的小规模问题的解合并为一个更大规模问题的解,自下而上逐步求出原问题的解。

·迭代与递归的关系迭代算法与递归算法都需要重复执行某些代码,两者既有区别又有着密切的联系。迭代是重复反馈过程的活动,其目的通常是逼近所需目标或结果。递归是重复调用函数自身。递归中,遇到满足终止条件的情况时逐层返回；迭代则通常使用计数器结束循环。迭代程序可以转换成等价的递归程序。

1.“大事化小、小事化了”体现出的问题求解的思想是（C）。A.递推法B.穷举法C.分治法D.归纳法2.二分查找算法利用的算法思想是（A）。A.分治策略B.穷举法C.贪心法D.回溯法3.对线性表进行二分查找时,要求线性表必须（B）。A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储.D.以链接方式存储,且数据元素有序CAB

4.对于数列3,8,11,15,17,19,25,30,44,采用“二分查找”法查找“8”时,需要查找多少次？（A）。A.3B.4C.5D.65.下面关于递归说法中正确的是（B）。A.函数间接调用自己不是递归B.递归出口和递归关系是递归函数编写的关键C.递归函数的嵌套调用次数没有限制D.递归函数的执行效率优于非递归函数AB