3.2算法及其描述《數(shù)據(jù)與計算》粵教版公開課一等獎?wù)n件省賽課獲獎?wù)n件

粵教版一般高中教科書信息技術(shù)必修1數(shù)據(jù)與計算3.2算法及其描述第1頁3.2.1算法角度概念專業(yè)規(guī)則求解某一問題有限步驟明確定義通俗措施-有窮集合動作或指令機械地執(zhí)行第2頁3.2.1討論問題：學(xué)期結(jié)束時，老師打算花50塊錢購買某些筆記本獎勵體現(xiàn)優(yōu)秀同窗，請班長小明幫忙，小明決定買三種單價分別為6元、5元、4元筆記本，請問能夠買多少本？第3頁3.1.1探究“6x+5y+4z=50正整數(shù)解個數(shù)t”①t=0;②x=1;③y=1;④z=1;⑤假如滿足6x+5y+4z=50，則解個數(shù)加1，并輸出這個解。⑥z=z+1;⑦假如z≤12則轉(zhuǎn)步驟⑤，不然繼續(xù)步驟⑧；⑧y=y+1;⑨假如y≤10則轉(zhuǎn)步驟④，不然繼續(xù)步驟⑩;⑩x=x+1；?假如x≤8則轉(zhuǎn)步驟③，不然繼續(xù)步驟?；?結(jié)束。第4頁3.2.1算法特性特性解釋有窮性計算步驟有限確定性每一種步驟都是明確數(shù)據(jù)輸入零個或多種數(shù)據(jù)輸出一種或多種可行性能夠得到成果第5頁3.2.2算法描述算法描述優(yōu)勢不足自然語言表達法用人們?nèi)粘Ｋ谜Z言，比較容易掌握。當(dāng)算法中具有多分支或循環(huán)操作較多時很難清楚地表達出來，由于自然語言歧義性，容易造成算法執(zhí)行不確定性。流程圖表達法用程序框圖來描述，流程描述清楚簡潔。所占篇幅較大，由于允許使用流程線，過于靈活，不受約束。偽代碼表達法用介于自然語言和計算機語言之間文字和符號來描述，書寫方便，格式緊湊，易于理解，便于向計算機程序設(shè)計語言過渡。由于編程語言種類繁多，偽代碼語句不容易規(guī)范，有時會產(chǎn)生誤解。第6頁3.2.2流程圖描述法-流程圖基本圖形及其功能圖形名稱功能開始/結(jié)束算法開始或結(jié)束輸入/輸出變量輸入或輸出處理變量計算與賦值判斷算法中條件判斷流程線表達算法中流向?連接點表達算法中連接第7頁3.2.2流程圖描述法x循環(huán)次數(shù)8y循環(huán)次數(shù)10z循環(huán)次數(shù)12總循環(huán)次數(shù)：8×10×12=960從中找出所有成立解第8頁3.2.2偽代碼描述法概念解釋偽代碼描述法介于自然語言文字和符號計算機語言特點易于轉(zhuǎn)變?yōu)橛嬎銠C程序t=0forxinrange(1,9):

foryinrange(1,11):

forzinrange(1,13):

if(x*6+y*5+z*4==50)

{t=t+1;給出解個數(shù)t及對應(yīng)三個整數(shù)x,y,z}第9頁3.2.2求方程“6x+5y+4z=50正整數(shù)解個數(shù)t”程序及運行成果t=0forxinrange(1,9):foryinrange(1,11):forzinrange(1,13):ifx*6+y*5+z*4==50:t=t+1print(x,y,z)print("總數(shù):",t,"個")方案xyz合計11461121811032271142621053431064241076219第10頁3.2.2求最大條約數(shù)-輾轉(zhuǎn)相除法-自然語言描述法①以m除以n，令所得余數(shù)為R。②若R=0，則輸出成果n，算法結(jié)束；不然，繼續(xù)步驟③。③令m=n，n=R，并返回步驟①繼續(xù)進行。求最大條約數(shù)步驟：第11頁3.2.2求最大條約數(shù)-輾轉(zhuǎn)相除法-程序框圖開始結(jié)束輸入m,nR=m%nR!=0?輸出nm=n,n=RYN在輸入兩個數(shù)字m和n時，是否需要確保m大于n?第12頁3.2.2求最大條約數(shù)-輾轉(zhuǎn)相除法-偽代碼m=int(input(“m=”))#接收一種數(shù)并轉(zhuǎn)換成整數(shù)n=int(input(“n=”))#接收另一種數(shù)并轉(zhuǎn)換成整數(shù)R=m%n#求余數(shù)whileR!=0:#當(dāng)余數(shù)不為0時循環(huán)m=n#將除數(shù)給mn=R#將余數(shù)給nR=m%n#求余數(shù)print(n)#輸出最大條約數(shù)第13頁3.2.2求最大條約數(shù)-更相減損術(shù)-自然語言描述法①以m減去n，令所得差為R。②若R=0，則輸出成果n，算法結(jié)束；不然，繼續(xù)步驟③。③令m=n，n=R，并返回步驟①繼續(xù)進行。求最大條約數(shù)步驟：第14頁3.2.2求最大條約數(shù)-更相減損術(shù)-程序框圖開始結(jié)束輸入m,nR=m-nR!=0?輸出nm=n,n=RYN在輸入數(shù)據(jù)時，要確保m比n大，不然，要在程序中將m和n調(diào)換。第15頁3.2.2求最大條約數(shù)-更相減損術(shù)-偽代碼m=int(input(“m=”))#接收一種數(shù)并轉(zhuǎn)換成整數(shù)n=int(input(“n=”))#接收另一種數(shù)并轉(zhuǎn)換成整數(shù)ifm<n:

m,n=n,m#假如m<n，則二者交換R=m-nwhileR!=0:m=n;n=R;ifm<n:m,n=n,mR=m-nprint(n)第16頁3.2.2求最小公倍數(shù)算法：兩數(shù)相乘，除以最大條約數(shù)m=int(input(“m=”))n=int(input(“n=”))s=m*n#二者相乘R=m%nwhileR!=0:m=nn=RR=m%nprint(int(s/n))#除以最大條約數(shù)第17頁3.2.2三種基本控制構(gòu)造第18頁3.2.2三種基本控制構(gòu)造基本構(gòu)造作用次序按先后次序執(zhí)行選擇條件→分支單選、雙選和多項選擇循環(huán)滿足條件反復(fù)執(zhí)行直到條件不滿足第19頁使用三種基本控制構(gòu)造組合來描述算法，能夠改善算法清楚度，提升算法可讀性。討論試結(jié)合教材P50“圖3-8求整數(shù)解流程圖”當(dāng)中三種基本控制構(gòu)造圖1次序構(gòu)造圖2選擇構(gòu)造