【課件】算法的概念及描述 2023-2024學(xué)年人教中圖版（2019）高中信息技術(shù)必修1

算法的概念及描述1.認(rèn)

識(shí)

算

法2.描

述

算

法認(rèn)識(shí)算法--問(wèn)題探究【案例1】有一個(gè)牧羊人，帶著一頭羊、一只狼和一顆大白菜準(zhǔn)備乘船過(guò)河，但是船很小，每次只能帶一樣?xùn)|西過(guò)去，可是如果狼和羊單獨(dú)在一起，羊就會(huì)被狼吃掉，羊和白菜單獨(dú)在一起，白菜就會(huì)被羊吃掉，那牧羊人怎樣才能將三者都順利的帶過(guò)河呢？以小組為單位，討論幫助牧羊人帶著狼、羊、白菜順利過(guò)河的方案。有一個(gè)牧羊人，帶著一頭羊、一只狼和一顆大白菜準(zhǔn)備乘船過(guò)河，但是船很小，每次只能帶一樣?xùn)|西過(guò)去，可是如果狼和羊單獨(dú)在一起，羊就會(huì)被狼吃掉，羊和白菜單獨(dú)在一起，白菜就會(huì)被羊吃掉，那牧羊人怎樣才能將三者都順利的帶過(guò)河呢？思考以下問(wèn)題：

（1）小組得出的方案共有多少步？（2）這些步驟的順序是固定不變的嗎？認(rèn)識(shí)算法參考方案：

（1）人和羊過(guò)河，人返回，留下羊。認(rèn)識(shí)算法參考方案：

（1）人和羊過(guò)河，人返回，留下羊。（2）人和狼過(guò)河，人和羊返回，留下狼。認(rèn)識(shí)算法參考方案：

（1）人和羊過(guò)河，人返回，留下羊。（2）人和狼過(guò)河，人和羊返回，留下狼。（3）人和菜過(guò)河，人返回，留下菜。認(rèn)識(shí)算法參考方案：

（1）人和羊過(guò)河，人返回，留下羊。（2）人和狼過(guò)河，人和羊返回，留下狼。（3）人和菜過(guò)河，人返回，留下菜。（4）人和羊過(guò)河。認(rèn)識(shí)算法算法的概念為解決一類特定問(wèn)題而采取的確定的、有限的步驟。認(rèn)識(shí)算法參考方案2：

（1）人和羊過(guò)河，人返回，留下羊。（2）人和菜過(guò)河，人和羊返回，留下菜。（3）人和狼過(guò)河，人返回，留下狼。（4）人和羊過(guò)河。參考方案1：

（1）人和羊過(guò)河，人返回，留下羊。（2）人和狼過(guò)河，人和羊返回，留下狼。（3）人和菜過(guò)河，人返回，留下菜。（4）人和羊過(guò)河。認(rèn)識(shí)算法?認(rèn)識(shí)算法算法的概念為解決一類特定問(wèn)題而采取的確定的、有限的步驟。有些步驟可以顛倒，不影響最終結(jié)果。有些步驟不能顛倒，一旦顛倒，最終的結(jié)果就完全不一樣。注意認(rèn)識(shí)算法有輸入算法的每個(gè)步驟都具有確定的含義（沒(méi)有歧義）算法的每一步操作都是可執(zhí)行的算法必須能在執(zhí)行有限個(gè)步驟之后終止（算法步驟不能是無(wú)限的）有輸出一個(gè)算法要求有0個(gè)或1個(gè)輸入一個(gè)算法要求有1個(gè)或多個(gè)輸入有窮性確定性可行性算法特性認(rèn)識(shí)算法參考方案：

（1）人和羊過(guò)河，人返回，留下羊。（2）人和狼過(guò)河，人和羊返回，留下狼。（3）人和菜過(guò)河，人返回，留下菜。（4）人和羊過(guò)河。自然語(yǔ)言描述算法自然語(yǔ)言流程圖偽代碼描述算法描述算法的方法用自然語(yǔ)言描述算法描述算法自然語(yǔ)言：人們?nèi)粘Ｋ玫恼Z(yǔ)言。用自然語(yǔ)言描述算法：使用人們能讀懂的簡(jiǎn)短語(yǔ)句

對(duì)算法的步驟進(jìn)行描述。缺點(diǎn)：容易產(chǎn)生二義性用流程圖描述算法描述算法流程圖：一種常用的表示算法的圖形化工具。順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)描述算法三種基本控制結(jié)構(gòu)描述算法1.順序結(jié)構(gòu)每一個(gè)步驟按先后次序被執(zhí)行，即執(zhí)行處理A,然后執(zhí)行處理B，如圖所示。描述算法2.選擇結(jié)構(gòu)又稱分支結(jié)構(gòu)。根據(jù)條件的成立與否，選擇執(zhí)行不同的分支處理，如圖所示。當(dāng)條件成立時(shí)(用True表示),執(zhí)行處理A;當(dāng)條件不成立時(shí)(用False表示)，執(zhí)行處理B。描述算法3.循環(huán)結(jié)構(gòu)當(dāng)條件成立時(shí)，反復(fù)執(zhí)行處理A，一旦條件不成立就立即結(jié)束循環(huán)，如圖所示。問(wèn)題探究【案例2】中國(guó)古代的第一部數(shù)學(xué)專著《九章算術(shù)》中記載了“更相減損術(shù)”的方法：“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之?！狈g：任意給出兩個(gè)正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡(jiǎn);若不是則用較大的數(shù)減去較小的數(shù),接著把較小的數(shù)與所得的差比較,并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作,直到所得的數(shù)相等為止，則這個(gè)數(shù)(等數(shù))就是所求的最大公約數(shù)。小組討論用流程圖實(shí)現(xiàn)“利用輾轉(zhuǎn)相除法求a和b的最大公約數(shù)”的算法。描述算法參考方案優(yōu)點(diǎn)：克服了自然語(yǔ)言二義性的缺點(diǎn)。直觀易讀，問(wèn)題解決的步驟清晰簡(jiǎn)潔，算法結(jié)構(gòu)表達(dá)明確。a=r輸入a,ba不等于b?r=a-br<b?a=bb=r輸出b結(jié)束開(kāi)始否否是是用偽代碼描述算法描述算法偽代碼描述算法：采用一種類似于程序設(shè)計(jì)語(yǔ)言的代碼來(lái)表示算法。偽代碼沒(méi)有固定的、嚴(yán)格的語(yǔ)法規(guī)則，只要定義合理、沒(méi)有矛盾即可?；乇芰顺绦蛟O(shè)計(jì)語(yǔ)言嚴(yán)格的書寫格式，保持了語(yǔ)言敘述準(zhǔn)確、無(wú)二義性的優(yōu)點(diǎn)，結(jié)構(gòu)性強(qiáng)，比較容易書寫和理解。課堂小結(jié)算法的概念：為解決一類特定問(wèn)題而采取的確定的、有限的步驟。算法的特征：（1）有輸入（2）有輸出（3）有窮性（4）可行性（5）確定性課堂小結(jié)算法描述方法優(yōu)勢(shì)不