教科版 (2019)4.3 非數(shù)值計(jì)算一等獎(jiǎng)?wù)n件ppt

這是一份教科版 (2019)4.3 非數(shù)值計(jì)算一等獎(jiǎng)?wù)n件ppt，文件包含43非數(shù)值計(jì)算二新教材2024-2025學(xué)年教科版2019高中信息技術(shù)必修一課件pptx、43非數(shù)值計(jì)算一新教材2024-2025學(xué)年教科版2019高中信息技術(shù)必修一課件pptx等2份課件配套教學(xué)資源，其中PPT共28頁(yè)， 歡迎下載使用。
4.3非數(shù)值計(jì)算（二）
運(yùn)用合適的算法形成解決問(wèn)題的方案；
體驗(yàn)遞歸算法，并結(jié)合具體問(wèn)題開(kāi)展編程實(shí)踐。
“漢諾塔”游戲源于印度一個(gè)古老傳說(shuō)的益智類(lèi)游戲。傳說(shuō)上帝創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子自下往上按大小順序摞著64片黃金圓盤(pán)。上帝命令婆羅門(mén)把圓盤(pán)從下面開(kāi)始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤(pán)上不能放大圓盤(pán)，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤(pán)。
三個(gè)圓盤(pán)時(shí)的移動(dòng)過(guò)程：
n個(gè)圓盤(pán)時(shí)的移動(dòng)過(guò)程：
2個(gè)圓盤(pán)時(shí)的移動(dòng)過(guò)程：
n個(gè)圓盤(pán)時(shí)：①將n-1個(gè)圓盤(pán)借助t柱從s柱移到m柱；②將最大的圓盤(pán)從s柱移到t柱；③將n-1個(gè)圓盤(pán)借助s再?gòu)膍柱移到t柱；
直接或間接地調(diào)用自身的方法稱為遞歸。
遞歸的基本思想是把規(guī)模較大的問(wèn)題層層轉(zhuǎn)化為規(guī)模較小的同類(lèi)問(wèn)題求解。對(duì)于遞歸而言，遞歸與回歸，二者缺一不同。結(jié)合分治策略，遞歸也可用“分”、“治”、“合”三個(gè)字概括：分：將原問(wèn)題分解成k個(gè)子問(wèn)題；治：對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則將其再分解為k個(gè)子問(wèn)題，如此進(jìn)行下去 ，直到問(wèn)題足夠小時(shí)，就很容易求出子問(wèn)題的解。合：將求出的小規(guī)模問(wèn)題的解合并為一個(gè)更大規(guī)模問(wèn)題的解，自下而上逐步求出原問(wèn)題的解。
使用遞歸思想解決問(wèn)題時(shí)，需要考慮以下三個(gè)問(wèn)題：明確遞歸終止條件；給出遞歸終止時(shí)的處理辦法；提取重復(fù)的邏輯，縮小問(wèn)題規(guī)模。
def hani(n,s,m,t): #定義一個(gè)函數(shù)，將n個(gè)圓盤(pán)從s柱借助m柱移到t柱 if n==1: #當(dāng)只有一個(gè)圓盤(pán)時(shí)，直接從s柱移到t柱，移完終止； #print(s+'->'+t) print("%s->%s"%(s,t)) else: #將n-1個(gè)圓盤(pán)借助t柱從s柱移到m柱，縮小規(guī)模后遞歸調(diào)用 ； hani(n-1,s,t,m) #print(s+'->'+t) print("%s->%s"%(s,t)) #將n-1個(gè)圓盤(pán)借助s再?gòu)膍柱移到t柱， 縮小規(guī)模后遞歸調(diào)用 ； hani(n-1,m,s,t)#主程序n=int(input("請(qǐng)輸入圓盤(pán)的個(gè)數(shù)："))#調(diào)用函數(shù)，將n個(gè)圓盤(pán)從A借助B移動(dòng)到Chani(n,"A","B","C")
可以將遞歸簡(jiǎn)單類(lèi)比為具有相似性重復(fù)的事物。
turtle庫(kù)是pythn的標(biāo)準(zhǔn)庫(kù)之一，它能夠進(jìn)行基本的圖形繪制；turtle庫(kù)繪制圖形有一個(gè)基本框架，即一個(gè)小海龜在坐標(biāo)系中爬行，其爬行軌跡形成了繪制的圖形。剛開(kāi)始繪制時(shí)，小海龜位于畫(huà)布的正中央，此處坐標(biāo)為（0,0)，前進(jìn)方向?yàn)樗椒较虻挠曳健?br/>分形圖像分析：從一個(gè)三角形開(kāi)始繪制。對(duì)三角形的三邊中點(diǎn)連線將其分為四個(gè)三角形，中間的小三角形不考慮，其余三個(gè)小三角形繼續(xù)由中點(diǎn)連線劃分成更小的四個(gè)小三角形，同理不斷地劃分下去，就可以形成如左圖所示的謝爾賓斯基三角形；我們把每一次劃分看成一層操作的話，右圖為每一次劃分 操作后得到的謝爾賓斯基三角形。每一次的劃分就是遞歸中每一次層的劃分。
imprt turtle#給出坐標(biāo)繪制三角形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()#求兩點(diǎn)中點(diǎn)坐標(biāo)def get_midpint(a,b): ax,ay=a bx,by=b return (ax+bx)/2,(ay+by)/2
#遞歸過(guò)程實(shí)現(xiàn)謝爾賓斯基三角形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) #右下三角形
# 設(shè)置初始參數(shù)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)# 關(guān)閉繪圖窗口turtle.dne()
謝爾賓斯基三角形0.py
1、對(duì)于數(shù)列3,8,11,15,17,19,25,30,44采用“二分法”查找8時(shí)，需要查找多少次？A.3B.4C.5D.62、下列關(guān)于斐波那契數(shù)列：1，1，2，3，5…的遞歸描述錯(cuò)誤的是（）。