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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、起床到出門需求洗臉刷牙(5 min)、刷水壺、刷水壺(2 min)、燒水燒水(8 min)、泡面、泡面(3 min)、吃飯、吃飯(10 min)、聽廣播、聽廣播(8 min)幾個幾個步驟從以下選項中選出較好的一種算法步驟從以下選項中選出較好的一種算法 ()A第一步洗臉刷牙、第二步刷水壺、第三步燒水、第四第一步洗臉刷牙、第二步刷水壺、第三步燒水、第四步泡面、第五步吃飯、第六步聽廣播步泡面、第五步吃飯、第六步聽廣播B第一步刷水壺、第二步燒水同時洗臉刷牙、第三步泡第一步刷水壺、第二步燒水同時洗臉刷牙、第三步泡面、第四步吃飯、第五步聽廣播面、第四步吃飯、第五步聽廣播返回C第一步刷水壺、第二步燒水同時洗

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