高考信息技术专题16 算法思想.pptx

第七单元数据结构与算法;知识点;;;1.迭代算法思想：让计算机重复执行一组______(或一些步骤)，这组指令(或这些步骤)每执行一次，都会让变量从______递推出一个新值。

2.利用迭代算法处理问题需要考虑三个方面：(1)确定__________；(2)建立____________；(3)控制__________。

3.为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解中方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法。当______到达某个边界，能直接得到解。;4.递归是指在函数的定义中调用______自身的方法，这里的调用分两种：直接调用与间接调用。递归就是有去有回：“有去”指递归问题必须可以分解为若干个规模较小且与原问题相同的子问题，这些子问题可以用相同的______思路来解决；“有回”指这些问题的演化过程是一个从大到小、由近及远的过程，并且存在一个明确的终点(临界点)，一旦到达这个临界点，就不用再往更小、更远的方向走下去。最后，从这个临界点开始，原路返回到原点，解决原问题。;5.利用递归算法解决问题的关键步骤：(1)抽象建立__________，确定__________；(2)确定__________(即递归结束条件)。

算法复杂度又分为算法的时间复杂度和空间复杂度，其中时间复杂度反映了算法执行所需要的时间，而空间复杂度反映了算法执行所需要占用的存储空间。;时间复杂度常用符号O表述，不包括低阶项和首项系数。时间复杂度从低到高可以分为常量阶O(1)、对数阶O(log2n)，线性阶O(n)、平方阶O(n2)等。迭代算法是用计算机处理问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值，是要解决上次计算与下次计算之间数据传递的问题。递归算法设计三步曲：①函数的参数和返回值。这个递归函数的功能是什么，怎样调用这个函数，即设计好递归函数的返回值和参数列表。②找到递归出口。什么时候应该结束这个递归，它的边界条件(出口)是什么(边界条件)。③设计递推公式。一层递归的逻辑。在非边界情况时，怎样从第n层转变成第n＋1层。;; ;【例2】有一堆桃子，猴子第一天吃掉其中的一半，并再多吃一个。之后每天猴子都吃掉剩余桃子的一半，再多吃一个。假设到第十天时，猴子发现只剩下了一个桃子，问原来这堆桃子最初有多少个。实现上述问题的两段Python程序如下：;C;;【变式2】定义如下两个函数，fac_1和fac_2：;;;;;;;;6.定义如下函数：

defpell(n)：

ifn＝＝1：

return0

elifn＝＝2：

return1

elifn2：

returnpell(n－1)*2＋pell(n－2);;;8.对于如下两个Python程序段：;;;10.已知：任取两个自然数，其互质(没有大于1的共同因数)的概率是6/(π*π)，小蓝据此编写了程序：

frommathimportsqrt

fromrandomimportrandint

deffun(a，b)：

ifb＝＝0：

returna

else：

returnfun(b，a%b)

cnt＝0

n＝1000；m＝100000

foriinrange(n)：

a＝randint(1，m)

b＝randint(1，m)

iffun(a，b)＝＝1：

cnt＋＝1

print(sqrt(6*n/cnt));;;;;3.有如下Python程序段判断是否为素数：

frommathimportsqrt

defprime(x，y)：

ifyint(sqrt(x))＋1：

return____________

elifx2orx%y＝＝0：

return____________

else：

return____________

a＝int(input(″请输入正整数：″))

ifprime(a，2)：

print(a，″是素数！″)

else：

print(a，″不是素数！″)

划线处应填代码的顺序为()

①True②False③prime(x，y＋1)

A.②③① B.②①③ C.①③② D.①②③;;;5.有两个自定义函数如下：;;;;;;;11.有如下Python程序段：

deffun(k)：

ifk＝＝0：

return″″

elifk%2＝＝1：

returnchr(k＋ord(A))＋fun(k－1)

else：

returnfun(k－1)＋chr(k＋ord(A))

有关该程序段，下列说法正