第三章算法基礎(chǔ)課件粵教版高中信息技術(shù)必修12

（1）把羊帶到右岸；（2）空船返回左岸，

把狼帶到右岸；（3）把羊帶回左岸；（4）把卷心菜帶到右岸；（5）空船返回左岸，

把羊帶到右岸。第三章

算法基礎(chǔ)一、算

法1.算法的概念算法是指在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。1.算法的概念通俗地說，算法就是計(jì)算機(jī)求解某一問題的方法，是能被執(zhí)行的動作或指令的有窮集合。2.人工解決問題

VS計(jì)算機(jī)解決問題例1：圓周率的計(jì)算歷史人物研究方法/時間圓周率位數(shù)（范圍）阿基米德（古希臘）內(nèi)外接多邊形（96邊形）3.141851祖沖之（中國）割圓術(shù)（公元480年）3.1415926~3.1415927魯?shù)婪颍ǖ聡?596年1610年20位小數(shù)值35位小數(shù)值梅欽（英國）無窮級數(shù)（1706年）突破100位JurijVega梅欽類公式（1789年）140位（137位正確）弗格森、倫奇1948年808位2.人工解決問題

VS計(jì)算機(jī)解決問題例1：圓周率的計(jì)算時間節(jié)點(diǎn)花費(fèi)時間圓周率位數(shù)1950年70小時2037位1955年13分鐘3089位1973年100萬位1989年10.1億位2010年5萬億位2011年一年（自組裝計(jì)算機(jī)）10萬億位2.人工解決問題

VS計(jì)算機(jī)解決問題例2：韓信點(diǎn)兵西漢大將韓信，善于帶兵，神機(jī)妙算，能征善戰(zhàn)。一次閱兵時，韓信要求士兵排成3路縱隊(duì)，此時末尾多出2人，改排成5路縱隊(duì)，末尾多出3人，再排成7路縱隊(duì)，末尾余下2人。這時，領(lǐng)兵的部下報告說，這隊(duì)士兵一共有2395人，韓信立刻搖頭說：不對，實(shí)際實(shí)際只有（

）人，部下遲疑地回去，又重新清點(diǎn)人數(shù)，果真是那么多人，部下們因此對韓信十分佩服。人數(shù)范圍x：2300~2400從2300開始，逐個數(shù)去試試，如果這個數(shù)能同時被3、5、7整除后的余數(shù)分別為2、3、2，則這個數(shù)就是正確的人數(shù)。分析問題（抽象與建模）例2：韓信點(diǎn)兵例2：韓信點(diǎn)兵設(shè)計(jì)算法①總?cè)藬?shù)x=2300；②判斷x是否在2300~2400之間，滿足則執(zhí)行下一步，否則結(jié)束；③判斷x是否滿足x÷3······2并且x÷5······3并且x÷7······2，滿足則執(zhí)行第⑤步，不滿足則執(zhí)行第④步；④x在原來的基礎(chǔ)上加1，回到第②步；⑤輸出x。思考1：計(jì)算機(jī)解決問題的過程是怎樣的？分析問題設(shè)計(jì)算法編寫程序調(diào)試運(yùn)行程序抽象與建模例2：韓信點(diǎn)兵①總?cè)藬?shù)x=2300；②判斷x是否在2300~2400之間，滿足則執(zhí)行下一步，否則結(jié)束；③判斷x是否滿足x÷3······2并且x÷5······3并且x÷7······2，滿足則執(zhí)行第⑤步，不滿足則執(zhí)行第④步；④x在原來的基礎(chǔ)上加1，回到第②步；⑤輸出x。3.算法的特征（1）有窮性；（2）確定性：每個步驟必須有確切的定義，不能出現(xiàn)模棱兩可的情況；（3）數(shù)據(jù)輸入：算法可以有零個或多個輸入；（4）數(shù)據(jù)輸出：算法必須有一個或多個輸出；（5）可行性：任何步驟都可執(zhí)行，能在有限時間內(nèi)完成。4.算法的描述（1）用自然語言描述算法易掌控當(dāng)算法較復(fù)雜時，用自然語言很難清晰表示自然語言具有歧義性，容易導(dǎo)致算法執(zhí)行的不確定性4.算法的描述（2）用流程圖描述算法使算法的流程描述得清晰、簡潔

流程圖的基本圖形及其功能起始框：表示算法的開始和結(jié)束處理框：表示完成某種操作判斷框：表示根據(jù)一個條件成立與否，決定執(zhí)行兩種不同操作的其中一個輸入、輸出框：表示數(shù)據(jù)的輸入輸出流程線：用箭頭表示程序執(zhí)行的流向朋友的意思程序猿的理解例2：韓信點(diǎn)兵①總?cè)藬?shù)x=2300；②判斷x是否在2300~2400之間，滿足則執(zhí)行下一步，否則結(jié)束；③判斷x是否滿足x÷3······2并且x÷5······3并且x÷7······2，滿足則執(zhí)行第⑤步，不滿足則執(zhí)行第④步；④x在原來的基礎(chǔ)上加1，回到第②步；⑤輸出x。4.算法的描述（3）用偽代碼描述算法偽代碼是介于自然語言和計(jì)算機(jī)語言之間的文字和符號。是一種非正式的，類似于英語結(jié)構(gòu)的，用于描述模塊結(jié)構(gòu)圖的語言。它沒有任何編程語言的語法，因此無法由計(jì)算機(jī)編譯或解釋。4.算法的描述（3）用偽代碼描述算法“韓信點(diǎn)兵”問題：if(x>=2300andx<=2400): if(x%3==2andx%5==3andx%7==2): {輸出對應(yīng)的x的值}4.算法的描述（3）用偽代碼描述算法不用圖形符號，每條指令占一行書寫方便，格式緊湊易于理解便于向計(jì)算機(jī)程序設(shè)計(jì)語言過渡5.常用算法枚舉法：也稱“窮舉法”。將問題的所有可能的答案一一列舉，然后根據(jù)條件判斷此答案是否合適，合適就保留，不合適就丟棄。解析法：用解析的方法，找出表示問題的前提條件與結(jié)果之間關(guān)系的數(shù)學(xué)表達(dá)式，并通過表達(dá)式計(jì)算實(shí)現(xiàn)問題求解。一般使用公式進(jìn)行計(jì)算的計(jì)算機(jī)程序都是用的解析法。遞歸法：通過重復(fù)將問題分解為同類的子問題。分治法：將一個規(guī)模較大的問題分解為若干個規(guī)模較小的子問題，通過解決子問題就可得到原問題的解。《張邱建算經(jīng)》中有一個“百雞問題”：“今有雞翁一,值錢伍;雞母一,值錢三;雞雛三,值錢一。凡百錢買雞百只,問雞翁、母、雛各幾何？”

張邱建：北魏時期數(shù)學(xué)家，“百雞問題”是中古時期關(guān)于不定方程正整數(shù)解的典型問題，張邱建對此有精湛和獨(dú)到的見解。著有《張邱建算經(jīng)》3卷。6.算法的優(yōu)化分析：設(shè)可以買公雞x只，母雞y只，小雞z只，根據(jù)題意可得出：x+y+z=100

5x+3y+z/3=10010000次x+y+z==100

and

5*x+3*y+z/3==100?分析：設(shè)可以買公雞x只，母雞y只，小雞z只，根據(jù)題意可得出：x+y+z=100

5x+3y+z/3=100X的范圍：0<X<=20Y的范圍：0<Y<=33660次x+y+z==100

and

5*x+3*y+z/3==100?分析：設(shè)可以買公雞x只，母雞y只，小雞z只，根據(jù)題意可得出：x+y+z=100

5x+3y+z/3=100x+y=100-z5x+3y=100-z/3x=4*z/3－100y=200－7*z/333次forzinrange(3,100,3):x=4/3*z-100y=200-7/3*zifx>0andy>0:print(int(x),int(y),int(z))分析：設(shè)可以買公雞x只，母雞y只，小雞z只，根據(jù)題意可得出：x+y+z=100

5x+3y+z/3=100x+y=100-z5x+3y=100-z/30<x=4*z/3－100<=200<y=200－7*z/3<=333次forzinrange(78,85,3):x=4/3*z-100y=200-7/3*zifx>0andy>0:print(int(x),int(y),int(z))75<z<85二、計(jì)算機(jī)程序與程序設(shè)計(jì)語言1.計(jì)算機(jī)程序

計(jì)算機(jī)程序是指計(jì)算機(jī)可以識別運(yùn)行的指令集合。二、計(jì)算機(jī)程序與程序設(shè)計(jì)語言2.算法與計(jì)算機(jī)程序的關(guān)系程序算法靈魂代碼實(shí)現(xiàn)算法與程序相互依附，算法要在計(jì)算機(jī)上執(zhí)行，必須將算法的步驟用編程語言的語法描述出來，編譯通過后，方可在計(jì)算機(jī)上執(zhí)行。二、計(jì)算機(jī)程序與程序設(shè)計(jì)語言3.計(jì)算機(jī)程序設(shè)計(jì)語言2023年頂級編程語言交互排行榜Dimx,y,zasintegerForx=1to100Step1Fory=1to100Step1

Z=100-x-yIf5*x+3*y+z/3=100ThenPrintx,y,zEndifNextyNextxVB

forxinrange(1,101):

foryinrange(1,101):

z=100-x-y

ifx+y+z==100and5*x+3*y+z/3==100:print(x,y,z)python3.計(jì)算機(jī)程序設(shè)計(jì)語言（1）機(jī)器語言是由“0”和“1”這樣的二進(jìn)制代碼指令組來表示。每一條機(jī)器指令包含兩個主要部分：操作（指出計(jì)算機(jī)應(yīng)做什么）和被操作的對象（指出處理的數(shù)據(jù)或它的地址），計(jì)算機(jī)能直接識別和執(zhí)行。3.計(jì)算機(jī)程序設(shè)計(jì)語言（1）機(jī)器語言3.計(jì)算機(jī)程序設(shè)計(jì)語言（2）匯編語言使用了一種類似英文縮略詞且?guī)в兄浶苑柕恼Z言，來替代一個特定的指令的二進(jìn)制串，每條指令都和一條機(jī)器指令相對應(yīng)。需要一個專門的語言翻譯器，負(fù)責(zé)將程序中的每條語句都翻譯成用二進(jìn)制數(shù)表示的機(jī)器語言。3.計(jì)算機(jī)程序設(shè)計(jì)語言（2）匯編語言3.計(jì)算機(jī)程序設(shè)計(jì)語言（3）高級語言接近于數(shù)學(xué)語言或人的自然語言，并且不再過度地倚賴某種特定的機(jī)器或環(huán)境，必須經(jīng)過翻譯器將其翻譯成機(jī)器語言。3.計(jì)算機(jī)程序設(shè)計(jì)語言（2）高級語言3.計(jì)算機(jī)程序設(shè)