1.2.2如何描述算法 (2)

1、1.2算法的描述與設(shè)計(jì)學(xué)習(xí)目標(biāo)：1、理解什么是算法，知道算法的多樣性；2、學(xué)會(huì)用自然語言、流程圖和偽代碼來描述算法；3、能夠?qū)υO(shè)計(jì)的算法做出簡單的評(píng)價(jià)。 算法的描述與設(shè)計(jì)有一個(gè)牧羊人帶著一頭羊,一只狼和一顆大白菜準(zhǔn)備過河,他找到一只很小的船,每次只能帶一樣?xùn)|西過去,可是如果讓狼與羊單獨(dú)在一起,狼會(huì)吃羊,讓羊與白菜單獨(dú)在一起,羊會(huì)吃白菜，牧羊人應(yīng)如何過河？現(xiàn)在請(qǐng)同學(xué)們來設(shè)計(jì)一個(gè)方案,把3樣?xùn)|西安然無恙的帶過河。農(nóng)夫過河問題 思考：123這個(gè)方案總共有多少步？ 哪幾步順序可以顛倒？同學(xué)們農(nóng)夫過河問題解決了，那到底什么是算法？ 過河方案牧羊人過河方案第一步：將羊運(yùn)過去第二步：人返回第三步：將菜運(yùn)過去

2、第四步：將羊運(yùn)過來第五步：將狼運(yùn)過去第六步：人返回第七步：將羊運(yùn)過來算法就是解決問題的方法和步驟。 算法是程序設(shè)計(jì)的“靈魂”，世界著名計(jì)算機(jī)科學(xué)家尼克勞斯沃思（Nwirth）指出：算法+數(shù)據(jù)結(jié)構(gòu)(Data Structure)=程序，可見，算法在程序設(shè)中具有多么重要的地位。算法獨(dú)立于任何具體的程序設(shè)計(jì)語言，一個(gè)算法可以用多種程序設(shè)計(jì)語言來實(shí)現(xiàn)。 算法的概念 算法 那算法都有哪些特征呢？也就是問題的解決都有哪些特點(diǎn)，我們應(yīng)該注意些什么呢？算法的特征有窮性：執(zhí)行有限步，每一步執(zhí)行時(shí)間有限;確定性：每一步都有確切的含義;輸入：有零個(gè)或多個(gè)輸入;輸出：至少產(chǎn)生一個(gè)輸出;可行性：原則上能精確運(yùn)行，用紙和

3、筆做有限次運(yùn)算后即可完成。如何描述算法算法可以用多種方法來描述1、用自然語言來描述。2、用流程圖來描述。3、用偽代碼描述算法。利用計(jì)算機(jī)求解方程：ax2+bx+c=0 (a0) 實(shí)例分析：自然語言Step1：輸入a、b、c的值Step2：令d為 b2- 4acStep3：如果 d大于或等于0 則輸出X1, x1為 ， X2, x2為， 轉(zhuǎn)到step4。 否則輸出方程無實(shí)數(shù)解，轉(zhuǎn)到step4。Step4：結(jié)束程序。 自然語言 用自然語言表達(dá)算法，就是把算法的各個(gè)步驟，依次用人們熟悉的自然語言表示出來。優(yōu)點(diǎn)：容易理解。缺點(diǎn)：書寫較煩、不確定性、對(duì)復(fù)雜的問題難以表達(dá)準(zhǔn)確、不能被計(jì)算機(jī)識(shí)別和執(zhí)行。自然

4、語言描述流程圖YN開始輸入a,b,c的值d=b2-4*a*cd=0X1=(-b+sqr(d)/(2*a)X2=(-b-sqr(d)/(2*a)輸出“此方程無實(shí)數(shù)解”結(jié)束輸出x1,x2的值流程圖Step1：輸入a、b、c的值Step2：令d為 b2- 4acStep3：如果 d大于或等于0 則輸出 X1, x1為 ， X2, x2為， 轉(zhuǎn)到step4。 否則輸出“方程無實(shí)數(shù) 解”，轉(zhuǎn)到step4。Step4：結(jié)束程序。 自然語言開始輸入a,b,c的值d=b2-4*a*cd=0X1=(-b+sqr(d)/(2*a)X2=(-b-sqr(d)/(2*a)輸出“此方程無實(shí)數(shù)解”結(jié)束輸出x1,x2的值

5、流程圖 也稱為程序框圖，它是算法的一種圖形化表示方法。與自然語言描述相比，用流程圖描述算法形象、直觀、更容易理解。流程圖描述 偽代碼偽代碼描述inputbox(“請(qǐng)輸入a,b,c的值”)d=b2-4acIf d=0 then X1=(-b+sqr(d)/(2*a) X2=(-b-sqr(d)/(2*a) 輸出 x1, x2的值Else輸出“此方程無實(shí)數(shù)解” 偽代碼 偽代碼是介于自然語言和計(jì)算機(jī)程序語言之間的一種算法描述。優(yōu)點(diǎn)：簡潔、易懂、修改容易。缺點(diǎn)：不直觀、一旦出現(xiàn)邏輯錯(cuò)誤不容易排查。偽代碼描述小結(jié)特征：有輸入 確定性 有窮性 有輸出 可行性 算法的描述用自然語言描述算法用流程圖描述算法用偽代碼描述算法算法解決問題的方法和步驟 一個(gè)問題，可能有多種算法 ，應(yīng)該通過分析、比較、挑選一種最優(yōu)的算法。一個(gè)好算法必須用到科學(xué)的方法 ，應(yīng)該好好學(xué)習(xí)各學(xué)科處理問題的科學(xué)方法。課堂練習(xí)1.不需要精確計(jì)算時(shí)，我們可以使用估算的方法。例如，考慮班級(jí)外出旅游費(fèi)用時(shí)，如果每人需要21元，則全班48人的費(fèi)用大約為1000元。計(jì)算機(jī)會(huì)這樣解決問題嗎，為什么？2.超市蘋果進(jìn)行打折促