資源簡介

(共23張PPT)
第二單元 算法的效率
目 錄
第9課 算法的評價方法
第8課 算法的多樣性
第11課 “韓信點(diǎn)兵”篩選法的實(shí)現(xiàn)
第10課 “韓信點(diǎn)兵”枚舉法的實(shí)現(xiàn)
第12課 “韓信點(diǎn)兵”同余法的實(shí)現(xiàn)
學(xué)習(xí)目標(biāo)
能依照算法的描述和問題實(shí)例評估算法的效率。
知道算法具有多樣性。
能根據(jù)簡單問題求解的需求設(shè)計出合適的算法。
前 言
解決同一個問題可能會有多種算法不同算法的效率也有可能是不一樣的在利用算法解決問題時，要根據(jù)問題求解的需求設(shè)計出合適的算法。
思 考
猜數(shù)字游戲，你能用多種算法來解決嗎
你覺得怎樣的算法才是“好”的算法
第8課 算法的多樣性
學(xué)習(xí)內(nèi)容
同一問題的多種算法驗(yàn)證
同一問題存在多種算法
討 論
下圖中，童童從學(xué)校到家有哪幾條路線可走
建 構(gòu)
日常生活中，算法具有多樣性，即可用多種不同的算法來解決同一個問題。
例如，解決猜數(shù)字游戲問題，除了前面學(xué)過的算法外，還可以采用順序查找和二分查找算法。
一、問題分析
猜數(shù)字游戲中，同學(xué)A輸入數(shù)字的過程其實(shí)是一個“查找”問題，即在1-100范圍內(nèi)查找目標(biāo)數(shù)da，可采用多種不同的策略來解決。
例如:
方法一:按順序依次查找
依次將1，2，3， ，98,，99，100(或100，99， ，3，2，1)與da比較直到找到為止。
方法二:取中間數(shù)查找
1-100范圍內(nèi)的數(shù)是依次增加的，依據(jù)該有序性可依次取中間數(shù)來杏找。先取1-100的中間數(shù)50與da比較，若da等于50，則查找成功；若da小于50，則取1-49的中間數(shù)25與da比較；若da大于50，則取51-100的中間數(shù)75與da比較......如此反復(fù)，直到找到為止。在1-100范圍內(nèi)查找目標(biāo)數(shù)37的過程如下所示:
一、問題分析
目標(biāo)數(shù)為37，初始范圍為1-100
第一次比較:37<50，范圍調(diào)整為 1-49
第二次比較:37>25，范圍調(diào)整為 26-49
第三次比較:37=37，查找成功。
小知識
計算機(jī)中的“查找”指根據(jù)既定條件找出滿足條件的對象，也就是說在存儲的大量數(shù)據(jù)內(nèi)找出一個特定的數(shù)據(jù)，或者判定在一批數(shù)據(jù)內(nèi)是否存在特定的數(shù)據(jù)。
試一試
采用“按順序依次查找”的方法，在1-100范圍內(nèi)查找數(shù)37，則需比較的次數(shù)是多少
二、解決問題的多種算法設(shè)計
根據(jù)解決問題采用的策略，將其設(shè)計成算法。例如，上述猜數(shù)字游戲就可將“按順序依次查找”設(shè)計成順序查找算法，“取中間數(shù)查找”設(shè)計成二分查找算法。
算法一:順序查找。
假設(shè)目標(biāo)數(shù)為37，并用變量da表示，取到的數(shù)用變量cai表示。對應(yīng)的算法流程圖如下:
二、解決問題的多種算法設(shè)計
二、解決問題的多種算法設(shè)計
算法二:二分查找。
假設(shè)目標(biāo)數(shù)為37，并用變量da表示，計算得到的中間值用變量cai表示，用變量cz和zz表示可取數(shù)的范圍，初始查找范圍為1-100，則cz的初值為1，zz的終值為100。對應(yīng)的算法流程圖如下:
二、解決問題的多種算法設(shè)計
三、解決問題的多種算法驗(yàn)證
上述順序查找算法和二分查找算法可以通過編寫并運(yùn)行程序或流程圖來進(jìn)行驗(yàn)證。
程序驗(yàn)證算法一:
想一想
算法一的程序，若變量da的值為137，那么運(yùn)行結(jié)果會是什么 如果想要顯示相應(yīng)的提示，那么應(yīng)該如何修改程序
三、解決問題的多種算法驗(yàn)證
用流程圖驗(yàn)證算法二:
根據(jù)剛才講到的算法二的流程圖，通過下方表格的形式列出變量cz、變量zz和變量cai的值來進(jìn)行驗(yàn)證。
找到數(shù)37，共進(jìn)行了3次循環(huán)。
試一試
請同學(xué)們試一試，當(dāng)變量da的值為137時，怎樣用表格列出變量cz、變量zz和變量cai的值。
練 習(xí)
在本節(jié)課講到的算法一中，如果變量cai的取值依次是100，99，98， ，3，2，1那么應(yīng)如何修改相應(yīng)的算法和程序
謝謝！

展開更多......

收起↑