教科版 (2019)4.3 非数值计算一等奖课件ppt

这是一份教科版 (2019)4.3 非数值计算一等奖课件ppt，文件包含43非数值计算二新教材2024-2025学年教科版2019高中信息技术必修一课件pptx、43非数值计算一新教材2024-2025学年教科版2019高中信息技术必修一课件pptx等2份课件配套教学资源，其中PPT共28页， 欢迎下载使用。
4.3非数值计算（二）
运用合适的算法形成解决问题的方案；
体验递归算法，并结合具体问题开展编程实践。
“汉诺塔”游戏源于印度一个古老传说的益智类游戏。传说上帝创造世界的时候做了三根金刚石柱子，在一根柱子自下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
三个圆盘时的移动过程：
n个圆盘时的移动过程：
2个圆盘时的移动过程：
n个圆盘时：①将n-1个圆盘借助t柱从s柱移到m柱；②将最大的圆盘从s柱移到t柱；③将n-1个圆盘借助s再从m柱移到t柱；
直接或间接地调用自身的方法称为递归。
递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对于递归而言，递归与回归，二者缺一不同。结合分治策略，递归也可用“分”、“治”、“合”三个字概括：分：将原问题分解成k个子问题；治：对这k个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为k个子问题，如此进行下去 ，直到问题足够小时，就很容易求出子问题的解。合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。
使用递归思想解决问题时，需要考虑以下三个问题：明确递归终止条件；给出递归终止时的处理办法；提取重复的逻辑，缩小问题规模。
def hani(n,s,m,t): #定义一个函数，将n个圆盘从s柱借助m柱移到t柱 if n==1: #当只有一个圆盘时，直接从s柱移到t柱，移完终止； #print(s+'->'+t) print("%s->%s"%(s,t)) else: #将n-1个圆盘借助t柱从s柱移到m柱，缩小规模后递归调用 ； hani(n-1,s,t,m) #print(s+'->'+t) print("%s->%s"%(s,t)) #将n-1个圆盘借助s再从m柱移到t柱， 缩小规模后递归调用 ； hani(n-1,m,s,t)#主程序n=int(input("请输入圆盘的个数："))#调用函数，将n个圆盘从A借助B移动到Chani(n,"A","B","C")
可以将递归简单类比为具有相似性重复的事物。
turtle库是pythn的标准库之一，它能够进行基本的图形绘制；turtle库绘制图形有一个基本框架，即一个小海龟在坐标系中爬行，其爬行轨迹形成了绘制的图形。刚开始绘制时，小海龟位于画布的正中央，此处坐标为（0,0)，前进方向为水平方向的右方。
分形图像分析：从一个三角形开始绘制。对三角形的三边中点连线将其分为四个三角形，中间的小三角形不考虑，其余三个小三角形继续由中点连线划分成更小的四个小三角形，同理不断地划分下去，就可以形成如左图所示的谢尔宾斯基三角形；我们把每一次划分看成一层操作的话，右图为每一次划分 操作后得到的谢尔宾斯基三角形。每一次的划分就是递归中每一次层的划分。
imprt turtle#给出坐标绘制三角形def draw_triangle(a,b,c): ax,ay=a bx,by=b cx,cy=c turtle.penup() turtle.gt(ax,ay) turtle.pendwn() turtle.gt(bx,by) turtle.gt(cx,cy) turtle.gt(ax,ay) turtle.penup()#求两点中点坐标def get_midpint(a,b): ax,ay=a bx,by=b return (ax+bx)/2,(ay+by)/2
#递归过程实现谢尔宾斯基三角形def draw_sierpinski(a,b,c, depth): draw_triangle(a,b,c) if depth==0: return else: d=get_midpint(a,b) e=get_midpint(b,c) f=get_midpint(c,a) draw_sierpinski(a,d,f,depth-1) #左下三角形 draw_sierpinski(d,b,e,depth-1) #上面三角形 draw_sierpinski(f,e,c,depth-1) #右下三角形
# 设置初始参数turtle.speed(0)turtle.penup()turtle.gt(-200, -200)turtle.pendwn()a=-200,-200b=0,100*(3)**0.5c=200,-200# 绘制谢尔宾斯基三角形draw_sierpinski(a,b,c, 3)# 关闭绘图窗口turtle.dne()
谢尔宾斯基三角形0.py
1、对于数列3,8,11,15,17,19,25,30,44采用“二分法”查找8时，需要查找多少次？A.3B.4C.5D.62、下列关于斐波那契数列：1，1，2，3，5…的递归描述错误的是（）。