第二單元算法的效率目

錄第9課

算法的評(píng)價(jià)方法第8課

算法的多樣性第11課“韓信點(diǎn)兵”篩選法的實(shí)現(xiàn)第10課“韓信點(diǎn)兵”枚舉法的實(shí)現(xiàn)第12課“韓信點(diǎn)兵”同余法的實(shí)現(xiàn)學(xué)習(xí)目標(biāo)能依照算法的描述和問(wèn)題實(shí)例評(píng)估算法的效率。知道算法具有多樣性。能根據(jù)簡(jiǎn)單問(wèn)題求解的需求設(shè)計(jì)出合適的算法。前

言

解決同一個(gè)問(wèn)題可能會(huì)有多種算法不同算法的效率也有可能是不一樣的在利用算法解決問(wèn)題時(shí)，要根據(jù)問(wèn)題求解的需求設(shè)計(jì)出合適的算法。思

考

猜數(shù)字游戲，你能用多種算法來(lái)解決嗎?

你覺(jué)得怎樣的算法才是“好”的算法?第8課算法的多樣性學(xué)習(xí)內(nèi)容同一問(wèn)題的多種算法驗(yàn)證同一問(wèn)題存在多種算法討

論

下圖中，童童從學(xué)校到家有哪幾條路線可走?建

構(gòu)

日常生活中，算法具有多樣性，即可用多種不同的算法來(lái)解決同一個(gè)問(wèn)題。

例如，解決猜數(shù)字游戲問(wèn)題，除了前面學(xué)過(guò)的算法外，還可以采用順序查找和二分查找算法。一、問(wèn)題分析

猜數(shù)字游戲中，同學(xué)A輸入數(shù)字的過(guò)程其實(shí)是一個(gè)“查找”問(wèn)題，即在1-100范圍內(nèi)查找目標(biāo)數(shù)da，可采用多種不同的策略來(lái)解決。

例如:

方法一:按順序依次查找

依次將1，2，3，???，98,，99，100(或100，99，???，3，2，1)與da比較直到找到為止。

方法二:取中間數(shù)查找

1-100范圍內(nèi)的數(shù)是依次增加的，依據(jù)該有序性可依次取中間數(shù)來(lái)杏找。先取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的過(guò)程如下所示:一、問(wèn)題分析

目標(biāo)數(shù)為37，初始范圍為1-100

第一次比較:37<50，范圍調(diào)整為1-49

第二次比較:37>25，范圍調(diào)整為26-49

第三次比較:37=37，查找成功。小知識(shí)

計(jì)算機(jī)中的“查找”指根據(jù)既定條件找出滿(mǎn)足條件的對(duì)象，也就是說(shuō)在存儲(chǔ)的大量數(shù)據(jù)內(nèi)找出一個(gè)特定的數(shù)據(jù)，或者判定在一批數(shù)據(jù)內(nèi)是否存在特定的數(shù)據(jù)。試一試

采用“按順序依次查找”的方法，在1-100范圍內(nèi)查找數(shù)37，則需比較的次數(shù)是多少?二、解決問(wèn)題的多種算法設(shè)計(jì)

根據(jù)解決問(wèn)題采用的策略，將其設(shè)計(jì)成算法。例如，上述猜數(shù)字游戲就可將“按順序依次查找”設(shè)計(jì)成順序查找算法，“取中間數(shù)查找”設(shè)計(jì)成二分查找算法。

算法一:順序查找。假設(shè)目標(biāo)數(shù)為37，并用變量da表示，取到的數(shù)用變量cai表示。對(duì)應(yīng)的算法流程圖如下:二、解決問(wèn)題的多種算法設(shè)計(jì)二、解決問(wèn)題的多種算法設(shè)計(jì)

算法二:二分查找。

假設(shè)目標(biāo)數(shù)為37，并用變量da表示，計(jì)算得到的中間值用變量cai表示，用變量cz和zz表示可取數(shù)的范圍，初始查找范圍為1-100，則cz的初值為1，zz的終值為100。對(duì)應(yīng)的算法流程圖如下:二、解決問(wèn)題的多種算法設(shè)計(jì)三、解決問(wèn)題的多種算法驗(yàn)證

上述順序查找算法和二分查找算法可以通過(guò)編寫(xiě)并運(yùn)行程序或流程圖來(lái)進(jìn)行驗(yàn)證。

程序驗(yàn)證算法一:想一想

算法一的程序，若變量da的值為137，那么運(yùn)行結(jié)果會(huì)是什么?如果想要顯示相應(yīng)的提示，那么應(yīng)該如何修改程序?三、解決問(wèn)題的多種算法驗(yàn)證

用流程圖驗(yàn)證算法二:

根據(jù)剛才講到的算法二的流程圖，通過(guò)下方表格的形式列出變量cz、變量zz和變量cai的值來(lái)進(jìn)行驗(yàn)證。

找到數(shù)37，共進(jìn)行了3次循環(huán)。試一試

請(qǐng)同學(xué)們?cè)囈辉嚕?dāng)變量da的值為137時(shí)，怎樣用表格列出變量cz、變量zz和變量cai的值。練