《算法案例一課時市公開課金獎市賽課一等獎?wù)n件》由會員分享，可在線閱讀，更多相關(guān)《算法案例一課時市公開課金獎市賽課一等獎?wù)n件（45頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算 法 案 例,第1頁,第1頁,案例1 輾轉(zhuǎn)相除法與更相減損術(shù),第2頁,第2頁,1.回顧算法三種表述：,自然語言,程序框圖,程序語言,（三種邏輯結(jié)構(gòu)）,（五種基本語句）,第3頁,第3頁,2.思考：,小學(xué)學(xué)過求兩個數(shù)最大公約數(shù)辦法？,先用兩個公有質(zhì)因數(shù)連續(xù)清除，始終除到所得商是互質(zhì)數(shù)為止，然后把所有除數(shù)連乘起來.,第4頁,第4頁,1、求兩個正整數(shù)最大公約數(shù),（1）求25和35最大公約數(shù),（2）求49和63最大公約數(shù),25,（1）,5,5,35,7,49,（2）,7,7,63,9,因此，25和35最大公約數(shù)為5
2、,因此，49和63最大公約數(shù)為7,2、除了用這種辦法外尚有無其它辦法？,算出8256和6105最大公約數(shù).,第5頁,第5頁,輾轉(zhuǎn)相除法（歐幾里得算法）,觀測用輾轉(zhuǎn)相除法求8251和6105最大公約數(shù)過程,第一步,用兩數(shù)中較大數(shù)除以較小數(shù)，求得商和余數(shù)8251=61051+2146,結(jié)論：8251和6105公約數(shù)就是6105和2146公約數(shù)，求8251和6105最大公約數(shù)，只要求出6105和2146公約數(shù)就能夠了。,第二步,對6105和2146重復(fù)第一步做法6105=21462+1813同理6105和2146最大公約數(shù)也是2146和1813最大公約數(shù)。,為什么呢？,思考：從上述的過程你體會到了什
3、么？,第6頁,第6頁,完整過程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,例2 用輾轉(zhuǎn)相除法求225和135最大公約數(shù),225=1351+90,135=901+45,90=452,顯然37是148和37最大公約數(shù)，也就是8251和6105最大公約數(shù),顯然45是90和45最大公約數(shù)，也就是225和135最大公約數(shù),思考1：從上面兩個例子能夠看出計算規(guī)律是什么？,S1：用大數(shù)除以小數(shù),S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù),S3：重復(fù)S1，直到余數(shù)為0,第7頁,第7頁,輾轉(zhuǎn)相除法
4、是一個重復(fù)執(zhí)行直到余數(shù)等于0停止環(huán)節(jié)，這事實上是一個循環(huán)結(jié)構(gòu)。,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,m=n q r,用程序框圖表示出右邊過程,r=m MOD n,m=n,n=r,r=0?,是,否,思考2：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？,第8頁,第8頁,1、輾轉(zhuǎn)相除法（歐幾里得算法）,（1）算理：所謂輾轉(zhuǎn)相除法，就是對于給定兩個數(shù)，用較大數(shù)除以較小數(shù)。若余數(shù)不為零，則將余數(shù)和較小數(shù)構(gòu)成新一對數(shù)，繼續(xù)上面除法，直到大數(shù)被小數(shù)除盡，則這時較小數(shù)就是本來兩個數(shù)最大公
5、約數(shù)。,第9頁,第9頁,（2）算法環(huán)節(jié),第一步：輸入兩個正整數(shù)m,n(mn).,第二步：計算m除以n所得余數(shù)r.,第三步：m=n,n=r.,第四步：若r0,則m,n最大公約數(shù)等于m；,不然轉(zhuǎn)到第二步.,第五步：輸出最大公約數(shù)m.,第10頁,第10頁,（3）程序框圖,（4）程序,INPUT “m,n=“;m,n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,開始,輸入m,n,r=m MOD n,m=n,r=0?,是,否,n=r,輸出m,結(jié)束,第11頁,第11頁,九章算術(shù)更相減損術(shù),算理：,可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損
6、，求其等也，以等數(shù)約之。,第一步：,任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。,第二步：,以較大數(shù)減較小數(shù)，接著把所得差與較小數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得減數(shù)和差相等為止，則這個等數(shù)就是所求最大公約數(shù)。,第12頁,第12頁,2、更相減損術(shù),（1）算理,：所謂更相減損術(shù)，就是對于給定兩個數(shù)，用較大數(shù)減去較小數(shù)，然后將差和較小數(shù)構(gòu)成新一對數(shù)，再用較大數(shù)減去較小數(shù)，重復(fù)執(zhí)行此環(huán)節(jié)直到差數(shù)和較小數(shù)相等，此時相等兩數(shù)便為本來兩個數(shù)最大公約數(shù)。,第13頁,第13頁,（2）算法環(huán)節(jié),第一步：輸入兩個正整數(shù)a,b(ab);,第二步：若a不等于b,則執(zhí)行第
7、三步；不然轉(zhuǎn)到第五步；,第三步：把a-b差賦予r;,第四步：假如br,那么把b賦給a,把r賦給b;不然把r賦給a，執(zhí)行第二步；,第五步：輸出最大公約數(shù)b.,第14頁,第14頁,（3）程序框圖,（4）程序,INPUT “a,b=“;a,b,WHILE ab,r=a-b,IF br THEN,a=b,b=r,ELSE,a=r,END IF,WEND,PRINT b,END,開始,輸入a,b,a,b?,是,否,輸出b,結(jié)束,b=r,a=b,r=a-b,r,b?,a=r,否,是,第15頁,第15頁,例3 用更相減損術(shù)求98與63最大公約數(shù),解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減,9
8、863356335283528728721,21721,1477,因此，98和63最大公約數(shù)等于7,用更相減損術(shù)求兩個正數(shù)84與72最大公約數(shù),練習(xí)：,先約簡，再求21與18最大公約數(shù),然后乘以兩次約簡質(zhì)因數(shù)4,第16頁,第16頁,例3、求324、243、135這三個數(shù)最大公約數(shù)。,思緒分析：求三個數(shù)最大公約數(shù)能夠先求出兩個數(shù)最大公約數(shù)，第三個數(shù)與前兩個數(shù)最大公約數(shù)最大公約數(shù)即為所求。,第17頁,第17頁,比較輾轉(zhuǎn)相除法與更相減損術(shù)區(qū)別,（1）都是求最大公約數(shù)辦法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，尤其當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)區(qū)別較
9、明顯。,（2）從結(jié)果表達(dá)形式來看，輾轉(zhuǎn)相除法表達(dá)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到,小結(jié),第18頁,第18頁,案例2 秦九韶算法,第19頁,第19頁,1.回顧算法三種表述：,自然語言,程序框圖,程序語言,（三種邏輯結(jié)構(gòu)）,（五種基本語句）,第20頁,第20頁,案例2、秦九韶算法,問題,如何求多項式f(x)=x,5,+x,4,+x,3,+x,2,+x+1當(dāng)x=5時值呢？,第21頁,第21頁,計算多項式,(,),=,當(dāng),x,=5值,算法1：,由于,(,),=,因此,(,5)=5,5,5,5,5,=,3125625125255,=,3906,算法2：,(,5)=5,5,5
10、,5,5,=,5(5,5,5,5,),=,5(5(5,5,5,),=,5(5(5(,5,+,5,+)+)+)+,=,5(5(5(,5,(,5,+)+)+)+)+,分析：兩種算法中各用了幾次乘法運算？和幾次加法運算？,第22頁,第22頁,算法1：,由于,(,),=,因此,(,5)=5,5,5,5,5,=,3125625125255,=,3906,算法2：,(,5)=5,5,5,5,5,=,5(5,5,5,5,),=,5(5(5,5,5,),=,5(5(5(,5,+,5,+)+)+)+,=,5(5(5(,5,(,5,+)+)+)+)+,共做了1+2+3+4=10次乘法運算，5次加法運算。,共做了4
11、次乘法運算，5次加法運算。,第23頁,第23頁,數(shù)書九章秦九韶算法,設(shè),是一個,n,次多項式,對該多項式按下面方式進(jìn)行改寫：,思考：當(dāng)知道了x的值后該如何求多項式的值？,這是如何一個改寫方式？最后結(jié)果是什么？,第24頁,第24頁,要求多項式值，應(yīng)當(dāng)先算最內(nèi)層一次多項式值，即,然后，由內(nèi)到外逐層計算一次多項式值，即,最后一項是什么？,這種將求一個n次多項式,f,(x)值轉(zhuǎn)化成求n個一次多項式值辦法，稱為,秦九韶算法,。,思考：在求多項式的值上，這是怎樣的一個轉(zhuǎn)化？,第25頁,第25頁,算法環(huán)節(jié)：,第一步：輸入多項式次數(shù)n、最高次項系數(shù)a,n,和x值.,第二步：將v值初始化為a,n,，將i值初始化
12、為1.,第三步：輸入i次項系數(shù)a,n-i,.,第四步：v=vx+a,n-i,i=i+1.,第五步：判斷i是否小于或等于n，若是，則返回第三步；不然，輸出多項式值v。,第26頁,第26頁,程序框圖：,這是一個在,秦九韶算法中重復(fù)執(zhí)行環(huán)節(jié)，因此可用循環(huán)結(jié)構(gòu)來實現(xiàn)。,輸入a,n-i,開始,輸入n,a,n,x,i,n 是否成立.若是，則輸 出b值；不然，返回第三步.,第一步，輸入a和n值.,第三步，i=i+1.,第39頁,第39頁,思考4:,按照上述思緒，把k進(jìn)制數(shù) 化為十進(jìn)制數(shù)b算法環(huán)節(jié)如何設(shè)計？,第四步，判斷in 是否成立.若是，則輸出b值；不然，返回第三步,.,第一步，輸入a，k和n值.,第二步
13、，令b=0，i=1.,第三步，i=i+1.,第40頁,第40頁,思考5:,上述把k進(jìn)制數(shù) 化為十進(jìn)制數(shù)b算法程序框圖如何表示？,開始,輸入a，k，n,b=0,i=1,把a右數(shù)第i位數(shù)字賦給t,b=b+tk,i,-,1,i=i+1,in?,結(jié)束,是,輸出b,否,第41頁,第41頁,思考6:,該程序框圖相應(yīng)程序如何表述？,開始,輸入a，k，n,b=0,i=1,把a右數(shù)第i位數(shù)字賦給t,b=b+tk,i,-,1,i=i+1,in?,結(jié)束,是,輸出b,否,INPUT a，k，n,b=0,i=1,t=a MOD10,DO,b=b+t*k,（i-1）,a=a10,t=a MOD10,i=i+1,LOOP
14、UNTIL i,n,PRINT b,END,第42頁,第42頁,例1 將下列各進(jìn)制數(shù)化為十進(jìn)制數(shù).,（1）10303,（4）,；（2）1234,（5）,.,理論遷移,10303,（4）,=14,4,+34,2,+34,0,=307.,1234,（5）,=15,3,+25,2,+35,1,+45,0,=194.,第43頁,第43頁,例2 已知10b1,（2）,=a02,（3）,求數(shù)字a，b值.,因此2b+9=9a+2，即9a-2b=7.,10b1,（2）,=12,3,+b2+1=2b+9.,a02,（3）,=a3,2,+2=9a+2.,故a=1，b=1.,第44頁,第44頁,1.k進(jìn)制數(shù)使用0（k-1）共k個數(shù)字，但左側(cè)第一個數(shù)位上數(shù)字（首位數(shù)字）不為0.,小結(jié),2.用 表示k進(jìn)制數(shù)，其中k稱為基數(shù)，十進(jìn)制數(shù)普通不標(biāo)注基數(shù).,3.把k進(jìn)制數(shù)化為十進(jìn)制數(shù)普通算式是：,第45頁,第45頁,
算法案例一課時市公開課金獎市賽課一等獎?wù)n件
