【課件】非數(shù)值計(jì)算（課件）-高一信息技術(shù)課件（教科版2019必修1）

4.3非數(shù)值計(jì)算2019教科版高中信息技術(shù)學(xué)習(xí)目標(biāo)運(yùn)用合適的算法形成解決問題的方案。了解算法設(shè)計(jì)中的分治思想，并運(yùn)用二分查找解決實(shí)際問題。體驗(yàn)遞歸算法，并結(jié)合具體問題開展編程實(shí)踐。三維目標(biāo)知識(shí)與技能：能夠理解分治思想和遞歸方法；能夠利用遞歸方法設(shè)計(jì)相應(yīng)程序；能夠基于不同場景分析編寫程序。過程與方法通過在練習(xí)活動(dòng)中不斷將問題與大概念相結(jié)合，促進(jìn)和提升問題解決能力。情感態(tài)度價(jià)值觀通過在游戲中體驗(yàn)程序設(shè)計(jì)的樂趣和邏輯思維的嚴(yán)謹(jǐn)。學(xué)科核心素養(yǎng)能夠分析問題時(shí)將其理解為數(shù)學(xué)問題，并通過合理、嚴(yán)謹(jǐn)?shù)乃惴ㄟM(jìn)行程序設(shè)計(jì)，提升問題解決能力和計(jì)算思維。一、游戲?qū)搿緦ふ壹賻庞螒颉坑?00個(gè)硬幣，其中有1個(gè)偽幣，它除了質(zhì)量比真幣輕一點(diǎn)之外，沒有別的區(qū)別，如何通過天平快速找到這個(gè)偽幣。大家自己查找資料并討論1、如何判斷假幣2、如何找到假幣？【在100個(gè)硬幣中找出偽幣】如何判斷假幣？厚薄不均勻色澤不光滑重量不一致如何找到假幣？分治思想【尋找假幣游戲】一、游戲?qū)胧紫仁菍?00個(gè)硬幣分成兩個(gè)50，使用天平進(jìn)行衡量，然后確定偽幣在比較輕的那50個(gè)里，接著再將50分成2個(gè)25，將25分成兩個(gè)12和1個(gè)1，將12分成2個(gè)6，將6分成2個(gè)3，將3分成3個(gè)1，這樣6次就可以找到偽幣，比50次少很多。以重量判斷為例重量輕的是假幣【尋找假幣游戲】一、游戲?qū)攵?、活?dòng)探究請總結(jié)說出如何查找單詞“book”的算法。1、從字典本的中間開始翻找，找到字母b的所在頁碼區(qū)域；2、從字母b的區(qū)域中間翻找，找到o的所在頁碼區(qū)域；3、重復(fù)上述翻找，直到查找到字母k?！静檎覇卧~游戲】【二分查找】（1）數(shù)據(jù)排序?qū)?shù)據(jù)有序排列：先將一個(gè)數(shù)據(jù)集進(jìn)行有序排列（2）數(shù)據(jù)分半：就是將排序好的數(shù)據(jù)集切分成大致相等的兩份數(shù)據(jù)集；（3）查找數(shù)據(jù)：查找的時(shí)候直接和拆分?jǐn)?shù)據(jù)集中的第一個(gè)或最后一個(gè)元素進(jìn)行大小比較，不滿足則表示數(shù)據(jù)不存在于該數(shù)據(jù)集中，滿足則說明要查找的元素存在于當(dāng)前數(shù)據(jù)集中。二、活動(dòng)探究【二分查找】將查找下面數(shù)組中的10數(shù)組1:1、5、6、9、10、20、21數(shù)字2:9、10、33、45、76、90、100【練習(xí)】二、活動(dòng)探究【二分查找】數(shù)組1:1、5、6、9、10、20、21leftright01234561569102021mid=(left+right)/2第一次查找查找結(jié)果為：索引號(hào)3，數(shù)值9二、活動(dòng)探究【二分查找】leftright01234561569102021mid第二次查找查找結(jié)果為：索引號(hào)5，數(shù)值209<10，因此，mid要向右移動(dòng)1個(gè)單位，即left=mid+1left=mid+1二、活動(dòng)探究【二分查找】leftright01234561569102021mid第三次查找查找結(jié)果為：索引號(hào)4，數(shù)值1020＞10，因此，mid要向左移動(dòng)1個(gè)單位，即right=mid-1right=mid-1二、活動(dòng)探究【二分查找】012345691033457690100自主練習(xí)數(shù)組2:9、10、33、45、76、90、100二、活動(dòng)探究【二分查找】012345691033457690100自主練習(xí)數(shù)字2:9、10、33、45、76、90、100第一次leftright06911結(jié)果mid=3號(hào)，45.right=mid-1第二次leftright02933結(jié)果mid=1號(hào)，10二、活動(dòng)探究【二分查找】deferfen(array,key):

left=0

right=len(array)-1

whileleft<=right:

mid=(left+right)//2

ifarray[mid]<key:

left=mid+1

elifarray[mid]>key:

right=mid-1

else:

returnmid核心程序：array=[9,10,33,45,76,90,100]key=10array_index=erfen(array,key)print(array_index)主程序：二、活動(dòng)探究二、活動(dòng)探究【二分查找】【分治與二分】1分治策略分治的設(shè)計(jì)思想，是將一個(gè)難以直接解決的大問題，分割成一些較小的同類問題，各個(gè)擊破，最終達(dá)到解決問題的目的。二分查找實(shí)際上就是分治策略的一種典型運(yùn)用。2二分法二分查找又叫折半查找，該方法主要將數(shù)列有序排列，采用跳躍式的方式查找數(shù)據(jù)。以遞增數(shù)列為例，先以中點(diǎn)位置的元素作為比較對象，如果要找的元素值小于該中點(diǎn)元素，則將待查序列縮小為左半部分，否則為右半部分。每一次比較后都可以將查找區(qū)間縮小一半。二、活動(dòng)探究補(bǔ)充程序代碼【二分查找】while(flag1<=flag2):

mid=（flag1+flag2）/2

ifmid>x:

flag2=mid-1

elifmid<x:

flag1=mid+1

else:

break二、活動(dòng)探究

1、有三根相鄰的柱子，標(biāo)號(hào)為A,B,C。

2、A柱子上從下到上按金字塔狀疊放著n個(gè)不同大小的圓盤。

3、現(xiàn)在把所有盤子一個(gè)一個(gè)移動(dòng)到柱子B上，并且每次移動(dòng)同一根柱子上都不能出現(xiàn)大盤子在小盤子上方。【什么是漢諾塔游戲？】【玩轉(zhuǎn)漢諾塔】二、活動(dòng)探究https://zhangxiaoleiwk.gitee.io/h.html同學(xué)們登錄網(wǎng)址自己玩一玩漢諾塔游戲吧。核心思想是：不斷重復(fù)前面移動(dòng)規(guī)則。當(dāng)擺3層時(shí)，則需要重新擺2層。當(dāng)擺4層時(shí)，則需要重新擺3層。二、活動(dòng)探究【玩轉(zhuǎn)漢諾塔】【遞歸——勾股樹】遞歸是計(jì)算科學(xué)領(lǐng)域中一種重要的計(jì)算思維模式。它既是一種抽象表達(dá)的手段，也是一種問題求解的重要方法。直接或間接地調(diào)用自身的方法稱為遞歸?？梢詫⑦f歸簡單類比為具有自相似性重復(fù)的事物。二、活動(dòng)探究【遞歸】二、活動(dòng)探究【遞歸】在數(shù)學(xué)與計(jì)算機(jī)領(lǐng)域中，遞歸函數(shù)是指用函數(shù)自身來定義該函數(shù)的方法。如著名的斐波那契數(shù)列“1，1，2，3，5，8，13，…”，可以遞歸定義為二、活動(dòng)探究【遞歸】【遞歸的分治】結(jié)合分治策略，遞歸也可用“分”“治”“合”三個(gè)字概括。（1）分：將原問題分解成k個(gè)子問題。（2）治：對這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則將其再分解為k個(gè)子問題，如此進(jìn)行下去，直到問題足夠小時(shí)，就很容易求出子問題的解。（3）合：將求出的小規(guī)模問題的解合并為一個(gè)更大規(guī)模問題的解，自下而上逐步求出原問題的解。二、活動(dòng)探究【遞歸】【練習(xí)】常見遞歸方法有：階乘、等比數(shù)列、等差數(shù)列。1、請你設(shè)計(jì)階乘底數(shù)為5的遞歸程序設(shè)計(jì)，并能正確打印結(jié)果。2、請你設(shè)計(jì)遞歸形式的斐波那契數(shù)列，使其輸入索引號(hào)時(shí)，能夠打印出對應(yīng)數(shù)值。二、活動(dòng)探究【遞歸】deffbnq(n):

ifn<=2:

return1

n=fbnq(n-1)+fbnq(n-2)returnnm=fbnq(int(input('請輸入索引號(hào)')))print(m)【斐波那契數(shù)列】二、活動(dòng)探究【遞歸】【等差數(shù)列】defdengcha(n):#定義一個(gè)函數(shù)名是dengcha，參數(shù)為n的函數(shù)

ifn==1:#當(dāng)參數(shù)n為1時(shí)，返回n的值

returnn#結(jié)束函數(shù)，并返回一個(gè)值n給函數(shù)

n=dengcha(n-1)+10returnnm=dengcha(int(input('請輸入等差項(xiàng)目')))print(m)二、活動(dòng)探究【遞歸】【階乘】defjiecheng(n):#定義一個(gè)函數(shù)名是jiecheng，參數(shù)為n的函數(shù)

ifn==1:#當(dāng)參數(shù)n為1時(shí)，返回n的值

returnn#結(jié)束函數(shù)，并返回一個(gè)值n給函數(shù)

n=n*jiecheng(n-1)#當(dāng)不滿足n==1時(shí)，進(jìn)行遞推，nl=n*（n-1）！

returnn#結(jié)束函數(shù)，并返回一個(gè)值n給函數(shù)m=jiecheng(int(input('輸入階乘底數(shù)