第1部分 第二章 § 11.1算法案例分析ppt課件

1、知識(shí)點(diǎn)二知識(shí)點(diǎn)二第第二二章章算算法法初初步步1 1算算法法的的根根本本思思想想知識(shí)點(diǎn)一知識(shí)點(diǎn)一了解教材新知了解教材新知運(yùn)用創(chuàng)新演練運(yùn)用創(chuàng)新演練考點(diǎn)一考點(diǎn)一把握熱點(diǎn)考向把握熱點(diǎn)考向考點(diǎn)二考點(diǎn)二考點(diǎn)三考點(diǎn)三1.11.1算算法法案案例例分分析析返回返回返回11算法案例分析算法案例分析返回返回返回返回 (1)算法是處理某類問題的一系列算法是處理某類問題的一系列 或或 ，只需，只需按照這些按照這些 執(zhí)行，都能使問題得到處理執(zhí)行，都能使問題得到處理 (2)在處理某些問題時(shí)，需求設(shè)計(jì)出一系列可操作或可計(jì)算在處理某些問題時(shí)，需求設(shè)計(jì)出一系列可操作或可計(jì)算的步驟，經(jīng)過實(shí)施這些步驟來(lái)處理問題，通常把這些的步驟，經(jīng)

2、過實(shí)施這些步驟來(lái)處理問題，通常把這些 稱為稱為處理這些問題的算法這種描畫不是算法的嚴(yán)厲定義，但是反處理這些問題的算法這種描畫不是算法的嚴(yán)厲定義，但是反映了算法的根本思想映了算法的根本思想步驟步驟程序程序步驟步驟步驟步驟返回 現(xiàn)代算法的作用之一是使計(jì)算機(jī)能替代人完成某些任務(wù)現(xiàn)代算法的作用之一是使計(jì)算機(jī)能替代人完成某些任務(wù) 算法的主要特征：算法的主要特征： (1)有窮性：一個(gè)算法的步驟是有限的，它應(yīng)在有限有窮性：一個(gè)算法的步驟是有限的，它應(yīng)在有限步操作之后停頓，而不能是無(wú)限的步操作之后停頓，而不能是無(wú)限的 (2)確定性：算法中的每一步應(yīng)該是確定的并且能有確定性：算法中的每一步應(yīng)該是確定的并且能有效

3、地執(zhí)行和得到確定的結(jié)果，而不該當(dāng)模棱兩可，比如效地執(zhí)行和得到確定的結(jié)果，而不該當(dāng)模棱兩可，比如讓學(xué)生求讓學(xué)生求 的近似值卻沒有要求近似的準(zhǔn)確度，不同的的近似值卻沒有要求近似的準(zhǔn)確度，不同的學(xué)生會(huì)得到不同的結(jié)果，或者說(shuō)該問題根本不能求解學(xué)生會(huì)得到不同的結(jié)果，或者說(shuō)該問題根本不能求解返回 (3)有序性：算法從初始步驟開場(chǎng)，分為假設(shè)干明確有序性：算法從初始步驟開場(chǎng)，分為假設(shè)干明確的步驟，每一個(gè)步驟只能有一個(gè)確定的后繼步驟，前一步的步驟，每一個(gè)步驟只能有一個(gè)確定的后繼步驟，前一步是后一步的前提，只需執(zhí)行完前一步才干進(jìn)展下一步，并是后一步的前提，只需執(zhí)行完前一步才干進(jìn)展下一步，并且每一步都要準(zhǔn)確無(wú)誤，才

4、干處理問題且每一步都要準(zhǔn)確無(wú)誤，才干處理問題 (4)不獨(dú)一性：求解某一個(gè)問題的算法不是獨(dú)一的，不獨(dú)一性：求解某一個(gè)問題的算法不是獨(dú)一的，對(duì)于一個(gè)問題可以有不同的算法對(duì)于一個(gè)問題可以有不同的算法 (5)普遍性：很多詳細(xì)的問題都可以設(shè)計(jì)合理的算法普遍性：很多詳細(xì)的問題都可以設(shè)計(jì)合理的算法去處理，如心算、計(jì)算器計(jì)算都要經(jīng)過有限的、事先設(shè)計(jì)去處理，如心算、計(jì)算器計(jì)算都要經(jīng)過有限的、事先設(shè)計(jì)好的步驟加以處理好的步驟加以處理返回返回 例例1以下對(duì)算法的了解不正確的選項(xiàng)是以下對(duì)算法的了解不正確的選項(xiàng)是 () A一個(gè)算法應(yīng)包含有限的步驟，而不能是無(wú)限的一個(gè)算法應(yīng)包含有限的步驟，而不能是無(wú)限的 B算法可以了解為

5、由根本運(yùn)算及規(guī)定的運(yùn)算順序構(gòu)算法可以了解為由根本運(yùn)算及規(guī)定的運(yùn)算順序構(gòu)成的完好的解題步驟成的完好的解題步驟 C算法中的每一步都該當(dāng)有效地執(zhí)行，并得到確定的算法中的每一步都該當(dāng)有效地執(zhí)行，并得到確定的結(jié)果結(jié)果 D一個(gè)問題只能設(shè)計(jì)出一個(gè)算法一個(gè)問題只能設(shè)計(jì)出一個(gè)算法 思緒點(diǎn)撥思緒點(diǎn)撥先正確了解算法的概念及其特點(diǎn)，然后先正確了解算法的概念及其特點(diǎn)，然后逐一驗(yàn)證每個(gè)選項(xiàng)能否正確逐一驗(yàn)證每個(gè)選項(xiàng)能否正確. .返回精解詳析精解詳析選項(xiàng)選項(xiàng)判斷判斷原因分析原因分析A算法的有限性指包含的步驟是有限的算法的有限性指包含的步驟是有限的B算法的明確性是指每一步都是確定的算法的明確性是指每一步都是確定的C算法的每一步

6、都是確定的，且每一步都應(yīng)算法的每一步都是確定的，且每一步都應(yīng)有確定的結(jié)果有確定的結(jié)果D對(duì)于同一個(gè)問題可以有不同的算法對(duì)于同一個(gè)問題可以有不同的算法答案答案 D返回 一點(diǎn)通一點(diǎn)通解答這類問題的方法為特征判別法，主要從解答這類問題的方法為特征判別法，主要從以下三方面判別：以下三方面判別： (1)看能否滿足順序性算法實(shí)踐上就是順序化的解題過看能否滿足順序性算法實(shí)踐上就是順序化的解題過程，是指可以用計(jì)算機(jī)來(lái)處理某一類問題的程序或步驟程，是指可以用計(jì)算機(jī)來(lái)處理某一類問題的程序或步驟 (2)看能否滿足明確性算法的每一步都是確定的，而不看能否滿足明確性算法的每一步都是確定的，而不是模糊的、模棱兩可的是模糊的

7、、模棱兩可的 (3)看能否滿足有限性一個(gè)算法必需在有限步后終看能否滿足有限性一個(gè)算法必需在有限步后終了假設(shè)一個(gè)解題步驟永遠(yuǎn)不能終了，那么就永遠(yuǎn)得不到答了假設(shè)一個(gè)解題步驟永遠(yuǎn)不能終了，那么就永遠(yuǎn)得不到答案因此，有始無(wú)終的解題步驟不是算法案因此，有始無(wú)終的解題步驟不是算法 此外，算法的不獨(dú)一性也要思索到此外，算法的不獨(dú)一性也要思索到返回1以下表達(dá)能稱為算法的個(gè)數(shù)為以下表達(dá)能稱為算法的個(gè)數(shù)為 ()植樹需求運(yùn)苗、挖坑、栽苗、澆水這些步驟植樹需求運(yùn)苗、挖坑、栽苗、澆水這些步驟順序進(jìn)展以下運(yùn)算：順序進(jìn)展以下運(yùn)算：112,213,314，991100.3xx1.求一切能被求一切能被3整除的正數(shù)，即整除的正數(shù)

8、，即3,6,9,12，.A1 B2C3 D4返回解析：根據(jù)算法的含義和特征：都是算法不是解析：根據(jù)算法的含義和特征：都是算法不是算法其中，算法其中，3xx1不是一個(gè)明確的邏輯步驟，不符不是一個(gè)明確的邏輯步驟，不符合邏輯性；的步驟是無(wú)窮的，與算法的有窮性矛盾合邏輯性；的步驟是無(wú)窮的，與算法的有窮性矛盾答案：答案： B返回2有關(guān)算法的描畫有以下幾種說(shuō)法：有關(guān)算法的描畫有以下幾種說(shuō)法：對(duì)一類問題都有效；對(duì)一類問題都有效；對(duì)個(gè)別問題有效；對(duì)個(gè)別問題有效；計(jì)算可以一步一步地進(jìn)展，每一步都有獨(dú)一的結(jié)果；計(jì)算可以一步一步地進(jìn)展，每一步都有獨(dú)一的結(jié)果；是一種通法，只需按部就班地做，總能得到結(jié)果是一種通法，只需

9、按部就班地做，總能得到結(jié)果其中說(shuō)法正確的選項(xiàng)是其中說(shuō)法正確的選項(xiàng)是_解析：算法通常是指可以用計(jì)算機(jī)來(lái)處理的某一類問題解析：算法通常是指可以用計(jì)算機(jī)來(lái)處理的某一類問題的程序或步驟，所以正確，錯(cuò)誤由于程序必需是的程序或步驟，所以正確，錯(cuò)誤由于程序必需是明確的，有效的，而且在有限步之內(nèi)完成，故正明確的，有效的，而且在有限步之內(nèi)完成，故正確綜上知，正確確綜上知，正確答案：答案：返回 例例2寫出解方程寫出解方程x22x30的一個(gè)算法的一個(gè)算法 思緒點(diǎn)撥思緒點(diǎn)撥此題是一個(gè)求一元二次方程的解的問題，此題是一個(gè)求一元二次方程的解的問題，方法很多，可用配方法，也可用判別式法方法很多，可用配方法，也可用判別式法

10、精解詳析精解詳析法一：算法步驟如下：法一：算法步驟如下： 1移項(xiàng)，得移項(xiàng)，得x22x3. 2兩邊同加兩邊同加1并配方，得并配方，得(x1)24. 3式兩邊開方，得式兩邊開方，得x12. 4解，得解，得x3或或x1.返回 一點(diǎn)通一點(diǎn)通對(duì)于數(shù)值型計(jì)算問題的算法，可以借助對(duì)于數(shù)值型計(jì)算問題的算法，可以借助數(shù)學(xué)公式采用數(shù)學(xué)計(jì)算的方法，將過程分解成明晰的步數(shù)學(xué)公式采用數(shù)學(xué)計(jì)算的方法，將過程分解成明晰的步驟，使之條理化即可，但應(yīng)留意多個(gè)數(shù)進(jìn)展四那么運(yùn)算驟，使之條理化即可，但應(yīng)留意多個(gè)數(shù)進(jìn)展四那么運(yùn)算時(shí)應(yīng)分步計(jì)算，依次進(jìn)展，直到算出結(jié)果時(shí)應(yīng)分步計(jì)算，依次進(jìn)展，直到算出結(jié)果返回3求過求過P(a1，b1)，Q(

11、a2，b2)兩點(diǎn)的直線斜率有如下的兩點(diǎn)的直線斜率有如下的算算法，請(qǐng)?jiān)跈M線上填上適當(dāng)步驟：法，請(qǐng)?jiān)跈M線上填上適當(dāng)步驟：1取取x1a1，y1b1，x2a2，y2b2.2判別判別“x1x2能否成立，假設(shè)是，那么輸出能否成立，假設(shè)是，那么輸出“斜率不斜率不存在；否那么，進(jìn)展下一步存在；否那么，進(jìn)展下一步3_.4輸出輸出k.返回返回4寫出求寫出求123456的一個(gè)算法的一個(gè)算法解：算法一：解：算法一：1計(jì)算計(jì)算12得得3；2將第一步中的運(yùn)算結(jié)果將第一步中的運(yùn)算結(jié)果3與與3相加得到相加得到6；3將第二步中的運(yùn)算結(jié)果將第二步中的運(yùn)算結(jié)果6與與4相加得到相加得到10；4將第三步中的運(yùn)算結(jié)果將第三步中的運(yùn)算結(jié)果

12、10與與5相加得到相加得到15；5將第四步中的運(yùn)算結(jié)果將第四步中的運(yùn)算結(jié)果15與與6相加得到相加得到21.返回算法二：算法二：1將原式變形為將原式變形為(16)(25)(34)37；2計(jì)算計(jì)算37；3得到運(yùn)算結(jié)果得到運(yùn)算結(jié)果.返回 例例3一個(gè)人帶著三只狼和三只羚羊過河，只需一一個(gè)人帶著三只狼和三只羚羊過河，只需一條船，該船最多可包容一個(gè)人和兩只動(dòng)物沒有人在的時(shí)條船，該船最多可包容一個(gè)人和兩只動(dòng)物沒有人在的時(shí)候，假設(shè)狼的數(shù)量不少于羚羊的數(shù)量，狼就會(huì)吃羚羊此候，假設(shè)狼的數(shù)量不少于羚羊的數(shù)量，狼就會(huì)吃羚羊此人如何才干將動(dòng)物平安轉(zhuǎn)移過河？請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法人如何才干將動(dòng)物平安轉(zhuǎn)移過河？請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法 思緒

13、點(diǎn)撥思緒點(diǎn)撥人和動(dòng)物同船不用思索狼會(huì)吃羚羊但需人和動(dòng)物同船不用思索狼會(huì)吃羚羊但需思索承載的數(shù)量，另外還應(yīng)思索到兩岸的動(dòng)物都得保證狼思索承載的數(shù)量，另外還應(yīng)思索到兩岸的動(dòng)物都得保證狼的數(shù)量要小于羚羊的數(shù)量，故在算法的設(shè)計(jì)中應(yīng)盡能夠保的數(shù)量要小于羚羊的數(shù)量，故在算法的設(shè)計(jì)中應(yīng)盡能夠保證船里面有狼，這樣才干使得兩岸的羚羊數(shù)量占到優(yōu)勢(shì)證船里面有狼，這樣才干使得兩岸的羚羊數(shù)量占到優(yōu)勢(shì) 返回精解詳析精解詳析詳細(xì)算法步驟如下：詳細(xì)算法步驟如下：1人帶兩只狼過河，并本人前往人帶兩只狼過河，并本人前往2人帶一只狼過河，并本人前往人帶一只狼過河，并本人前往3人帶兩只羚羊過河，并帶兩只狼前往人帶兩只羚羊過河，并帶兩

14、只狼前往4人帶一只羚羊過河，并本人前往人帶一只羚羊過河，并本人前往5人帶兩只狼過河人帶兩只狼過河返回 一點(diǎn)通一點(diǎn)通處理此類問題需先建立過程模型，經(jīng)過處理此類問題需先建立過程模型，經(jīng)過模型進(jìn)展算法設(shè)計(jì)與描畫，設(shè)計(jì)詳細(xì)的數(shù)學(xué)問題的算法，模型進(jìn)展算法設(shè)計(jì)與描畫，設(shè)計(jì)詳細(xì)的數(shù)學(xué)問題的算法，實(shí)踐上就是尋求一類問題的算法，它可以經(jīng)過計(jì)算機(jī)來(lái)完實(shí)踐上就是尋求一類問題的算法，它可以經(jīng)過計(jì)算機(jī)來(lái)完成設(shè)計(jì)算法的關(guān)鍵是把過程分解成假設(shè)干個(gè)明確的步驟，成設(shè)計(jì)算法的關(guān)鍵是把過程分解成假設(shè)干個(gè)明確的步驟，然后用計(jì)算機(jī)能接受的然后用計(jì)算機(jī)能接受的“言語(yǔ)準(zhǔn)確地描畫出來(lái)言語(yǔ)準(zhǔn)確地描畫出來(lái)返回5早上從起床到出門需求洗臉?biāo)⒀涝缟蠌?/p>

15、起床到出門需求洗臉?biāo)⒀?5 min)、刷水壺、刷水壺(2 min)、燒水燒水(8 min)、泡面、泡面(3 min)、吃飯、吃飯(10 min)、聽廣播、聽廣播(8 min)幾個(gè)幾個(gè)步驟從以下選項(xiàng)中選出較好的一種算法步驟從以下選項(xiàng)中選出較好的一種算法 ()A第一步洗臉?biāo)⒀?、第二步刷水壺、第三步燒水、第四第一步洗臉?biāo)⒀?、第二步刷水壺、第三步燒水、第四步泡面、第五步吃飯、第六步聽廣播步泡面、第五步吃飯、第六步聽廣播B第一步刷水壺、第二步燒水同時(shí)洗臉?biāo)⒀馈⒌谌脚莸谝徊剿⑺畨?、第二步燒水同時(shí)洗臉?biāo)⒀?、第三步泡面、第四步吃飯、第五步聽廣播面、第四步吃飯、第五步聽廣播返回C第一步刷水壺、第二步燒水同時(shí)洗

16、臉?biāo)⒀?、第三步泡面、第一步刷水壺、第二步燒水同時(shí)洗臉?biāo)⒀馈⒌谌脚菝?、第四步吃飯同時(shí)聽廣播第四步吃飯同時(shí)聽廣播D第一步吃飯同時(shí)聽廣播、第二步泡面、第三步燒水同時(shí)第一步吃飯同時(shí)聽廣播、第二步泡面、第三步燒水同時(shí)洗臉?biāo)⒀?、第四步刷水壺洗臉?biāo)⒀?、第四步刷水壺解析：完成這個(gè)過程用時(shí)最少的是最好的算法，因此我們可以解析：完成這個(gè)過程用時(shí)最少的是最好的算法，因此我們可以從四個(gè)答案所給出的步驟能否合理，需求破費(fèi)多少時(shí)間入手從四個(gè)答案所給出的步驟能否合理，需求破費(fèi)多少時(shí)間入手答案：答案：C返回6有藍(lán)和黑兩個(gè)墨水瓶，但如今卻錯(cuò)把藍(lán)墨水裝在有藍(lán)和黑兩個(gè)墨水瓶，但如今卻錯(cuò)把藍(lán)墨水裝在了黑墨水瓶中，黑墨水錯(cuò)裝在了藍(lán)墨水瓶中，要求將其互了黑墨水瓶中，黑墨水錯(cuò)裝在了藍(lán)墨水瓶中，要求將其互換回來(lái)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法處理這個(gè)問題換回來(lái)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法處理這個(gè)問題解：算法步驟如下：解：算法步驟如下：1取一只空的墨水瓶，設(shè)其為白色；取一只空的墨水瓶，設(shè)其為白色；2將黑墨水瓶中的藍(lán)墨水裝入白瓶中；將黑墨水瓶中的藍(lán)墨水裝入白瓶中；3將藍(lán)墨水瓶中的黑墨水裝入黑墨水瓶中；將藍(lán)墨水瓶中的黑墨水裝入黑墨水瓶中；4將白瓶中的藍(lán)墨水裝入藍(lán)墨水瓶中；將白瓶中的藍(lán)墨水裝入藍(lán)墨水瓶中；5交換終了交換終了返回1