第二章算法初步§1算法的基本思想知識(shí)點(diǎn)一算法的概念及思想[填一填]1．算法的概念及描述方式算法是解決某類問題的一系列步驟或程序，只要按照這些步驟執(zhí)行，都能使問題得到解決．一般來說，“用算法解決問題”都是可以利用計(jì)算機(jī)幫助完成的．算法的描述方式有：自然語言、數(shù)學(xué)語言、形式語言(算法語言)、框圖．2．算法的基本思想在解決某些問題時(shí)，需要設(shè)計(jì)出一系列可操作或可計(jì)算的步驟，通過實(shí)施這些步驟來解決問題，通常把這些步驟稱為解決這些問題的算法．這種解決問題的思想方法稱為算法的基本思想．[答一答]1．一個(gè)好的算法應(yīng)有哪些要求？提示：算法的基本思想是程序化思想，應(yīng)滿足以下兩個(gè)基本要求．(1)寫出的算法，必須能解決一類問題，并且能夠重復(fù)使用．如在解二元一次方程組時(shí)，高斯消去法就是一個(gè)典型的算法實(shí)例，這種算法可用來求解任意一個(gè)二元一次方程組，只要我們將高斯消去法中的參數(shù)值換為二元一次方程組的相應(yīng)系數(shù)值即可．(2)算法過程要能一步一步執(zhí)行，每一步執(zhí)行的操作必須確切，不能含糊不清，而且經(jīng)過有限步后能得出結(jié)果．知識(shí)點(diǎn)二算法的性質(zhì)[填一填]3．算法的性質(zhì)(1)確定性：算法中的每一步都應(yīng)該是確定的，并且能有效地執(zhí)行并得到確定的結(jié)果，而不能含糊其辭，含有歧義．(2)有限性：對(duì)于一個(gè)算法來說，它的操作步驟必須是有限的，必須在有限的步驟之內(nèi)完成．(3)普遍性：一個(gè)算法通常能解決一類問題，不是僅僅解決一個(gè)單獨(dú)的問題．4．(1)作用：使計(jì)算機(jī)代替人完成某些工作．(2)注意：解決一個(gè)問題可能有多個(gè)算法，但有優(yōu)劣之分，其中操作簡(jiǎn)單、步驟少且能解決一類問題的算法稱為最優(yōu)算法．[答一答]2．算法與解法的區(qū)別與聯(lián)系是什么？提示：學(xué)習(xí)算法的概念應(yīng)注意以下兩點(diǎn)：1．在數(shù)學(xué)中，現(xiàn)代意義上的“算法”通常是指解決某一類問題的程序或步驟，這些程序或步驟必須是明確和有效的，而且能夠在有限步之內(nèi)完成．2．通俗點(diǎn)說，算法就是計(jì)算機(jī)解題的過程，在這個(gè)過程中，無論是形成解題思路還是編寫程序，都是在實(shí)施某種算法，前者是推理實(shí)現(xiàn)的算法，后者是操作實(shí)現(xiàn)的算法．類型一算法的概念【例1】小明早上從起床到出門需要洗臉?biāo)⒀?5min)、刷水壺(2min)、燒水(8min)、泡面(3min)、吃飯(10min)、聽廣播(8min)幾個(gè)步驟，下列選項(xiàng)中最好的一種算法是()A．①洗臉?biāo)⒀溃虎谒⑺畨兀虎蹮虎芘菝妫虎莩燥垼虎蘼爮V播B．①刷水壺；②燒水同時(shí)洗臉?biāo)⒀溃虎叟菝妫虎艹燥垼虎萋爮V播C．①刷水壺；②燒水同時(shí)洗臉?biāo)⒀溃虎叟菝妫虎艹燥埻瑫r(shí)聽廣播D．①吃飯同時(shí)聽廣播；②泡面；③燒水同時(shí)洗臉?biāo)⒀溃虎芩⑺畨亍舅悸诽骄俊款}中給出了各步驟及所需的時(shí)間，保證了算法步驟的確定性和可執(zhí)行性，現(xiàn)在只需根據(jù)時(shí)間最短來確定出最好的算法步驟即可．【解析】因?yàn)锳選項(xiàng)共用時(shí)間36min，B選項(xiàng)共用時(shí)間31min，C選項(xiàng)共用時(shí)間23min，D選項(xiàng)的算法步驟不符合常理，所以最好的算法是C.【答案】C規(guī)律方法解決有關(guān)算法概念的判斷題時(shí)，應(yīng)根據(jù)算法的特征進(jìn)行判斷，特別注意必須能在有限步內(nèi)求解某類問題，其中每個(gè)步驟都必須明確可行，不能模棱兩可．(1)下列關(guān)于算法的幾種說法：①算法對(duì)一類問題都有效；②算法對(duì)個(gè)別問題有效；③算法就是某個(gè)問題的解題過程；④算法是一種通法，只要按部就班地做，總能得到結(jié)果．其中正確的個(gè)數(shù)為(B)A．1B．2C．3D．4(2)下列描述中不能看作算法的是(D)A．做米飯需要刷鍋，淘米，添水，加熱這些步驟B．洗衣機(jī)的使用說明書C．從濟(jì)南到臺(tái)灣旅游，先坐火車，再坐飛機(jī)D．解方程2x2＋x－1＝0時(shí)需先判斷判別式的符號(hào)解析：(1)算法通常是指可以用計(jì)算機(jī)來解決的某一類問題的程序或步驟，所以①正確，②不正確；算法不等同于解法，所以③不正確；算法的程序或步驟必須是明確的、有效的，而且必須在有限步內(nèi)完成，所以④正確．(2)因?yàn)锳，B，C都描述了解決問題的過程，可以看作算法，而D只描述了一個(gè)事實(shí)，沒說明如何解決問題，不是算法．類型二借助算法解方程或方程組【例2】寫出解方程組eq\b\lc\{\rc\(\a\vs4\al\co1(2x＋y＝7①，,4x＋5y＝11②))的算法．【思路探究】解線性方程組的常用方法是加減消元法和代入消元法，這兩種方法沒有本質(zhì)的差別，但是代入消元法更適用于解一般的線性方程組，且便于在計(jì)算機(jī)上實(shí)現(xiàn)．【解】算法1(代入消元法)算法步驟如下：1．由①得y＝7－2x③；2．將③代入②得4x＋5(7－2x)＝11④；3．解④得x＝4；4．將x＝4代入③得y＝－1；5．得到方程組的解為eq\b\lc\{\rc\(\a\vs4\al\co1(x＝4，,y＝－1.))算法2(加減消元法)算法步驟如下：1．①×5－②得(2×5－4)x＝7×5－11③；2．解③得x＝4；3．①×2－②得(1×2－5)y＝7×2－11④；4．解④得y＝－1；5．得到方程組的解為eq\b\lc\{\rc\(\a\vs4\al\co1(x＝4，,y＝－1.))規(guī)律方法設(shè)計(jì)算法時(shí)，經(jīng)常遇到解方程或方程組的算法問題，一般是按照數(shù)學(xué)上解方程或方程組的方法進(jìn)行設(shè)計(jì)，但應(yīng)注意全面考慮解的情況，即先確定方程或方程組是否有解，有解時(shí)有幾個(gè)或幾組解，然后按照求解步驟設(shè)計(jì)算法步驟．寫出解方程x2－2x－3＝0的一個(gè)算法．解：解法1：1.移項(xiàng)，得x2－2x＝3；①2．①兩邊同時(shí)加1并配方，得(x－1)2＝4；②3．②式兩邊開方，得x－1＝±2；③4．解③得x＝3，或x＝－1.解法2：1.計(jì)算方程的判別式并判斷其符號(hào)，Δ＝(－2)2－4×1×(－3)＝16>0；2．將a＝1，b＝－2，c＝－3代入求根公式x＝eq\f(－b±\r(b2－4ac),2a)，得x1＝3，x2＝－1.類型三求兩個(gè)數(shù)的最大公因數(shù)或最小公倍數(shù)【例3】設(shè)計(jì)一個(gè)算法，求1896與2008的最大公因數(shù)．【思路探究】分別對(duì)1896與2008進(jìn)行素因數(shù)分解，最后找出最大公因數(shù)．【解】首先，對(duì)兩個(gè)數(shù)分別進(jìn)行素因數(shù)分解：1896＝23×3×79,2008＝23×251.其次，確定兩個(gè)數(shù)的公共素因數(shù)為2.接著，確定公共素因數(shù)的指數(shù)：對(duì)于公共素因數(shù)2,23是1896的因數(shù)，也是2008的因數(shù)，因此23是這兩個(gè)數(shù)的公因數(shù)．這樣，就確定了1896與2008的最大公因數(shù)為：23＝8.算法步驟如下：第一步，將1896行素因數(shù)分解：1896＝23×3×79；第二步，將2008進(jìn)行素因數(shù)分解：2008＝23×251；第三步，確定它們的公共素因數(shù)：2；第四步，確定公共素因數(shù)2的指數(shù)為3；第五步，最大公因數(shù)為23＝8.規(guī)律方法把1896與2008分別進(jìn)行素因數(shù)分解，一般是從2開始，用“是則留下，不是則去掉”的方法，然后是3,5,7，…直到分別將兩個(gè)數(shù)分解為素因數(shù)的積為止．設(shè)計(jì)一個(gè)算法，求1356和2400的最小公倍數(shù)．解：算法步驟如下：(1)先將1356進(jìn)行素因數(shù)分解：1356＝22×3×113；(2)然后將2400進(jìn)行素因數(shù)分解：2400＝25×3×52；(3)確定兩個(gè)數(shù)的所有素因數(shù)：2,3,5,113；(4)確定素因數(shù)的指數(shù)：2的指數(shù)為5,3的指數(shù)為1,5的指數(shù)為2,113的指數(shù)為1；(5)最小公倍數(shù)為：25×3×52×113＝271200.類型四篩選問題的算法設(shè)計(jì)【例4】設(shè)計(jì)一個(gè)算法，對(duì)任意3個(gè)整數(shù)a，b，c，求出其中的最小值．【思路探究】eq\x(比較a，b)eq\o(→,\s\up15(較小的數(shù)記為m))eq\x(比較m與c)→eq\x(最小數(shù))【解】算法步驟如下：1．比較a與b的大小，若a<b，則m＝a；若b<a，則m＝b.2．比較m與c的大小，若m<c，則m為最小數(shù)；若c<m，則c為最小數(shù)．規(guī)律方法求最小(大)數(shù)就是從中篩選出最小(大)的一個(gè)，篩選過程中的每一步都是比較兩個(gè)數(shù)的大小，保證了篩選的可行性，這種方法可以推廣到從多個(gè)不同數(shù)中篩選出滿足要求的一個(gè)．在下列數(shù)字序列中，寫出搜索89的算法：21,3,0,9,15,72,89,91,93.解：1.先找到序列中的第一個(gè)數(shù)m，m＝21；2．將m與89比較，是否相等，如果相等，則搜索到89；3．如果m與89不相等，則往下執(zhí)行；4．繼續(xù)將序列中的其他數(shù)賦給m，重復(fù)第2步，直到搜索到89.類型五算法的應(yīng)用【例5】一次青青草原園長(zhǎng)包包大人帶著灰太狼、懶羊羊和一捆青草過河．河邊只有一條船，由于船太小，只能裝下兩樣?xùn)|西．若包包大人不在跟前，灰太狼要吃懶羊羊，懶羊羊要吃青草，請(qǐng)問包包大人如何才能帶著他們平安過河？試設(shè)計(jì)一種算法．【思路探究】包包大人先帶誰過去是解決本題的關(guān)鍵所在．【解】包包大人采取的過河的算法可以是：第一步，包包大人帶懶羊羊過河；第二步，包包大人自己返回；第三步，包包大人帶青草過河；第四步，包包大人帶懶羊羊返回；第五步，包包大人帶灰太狼過河；第六步，包包大人自己返回；第七步，包包大人帶懶羊羊過河．規(guī)律方法對(duì)于實(shí)際生活中的問題，首先應(yīng)建立過程模型，根據(jù)過程設(shè)計(jì)步驟，完成算法．在設(shè)計(jì)算法時(shí)應(yīng)簡(jiǎn)練、清晰，要善于分析任何可能出現(xiàn)的情況，以體現(xiàn)思維的嚴(yán)謹(jǐn)性．一位商人有9枚銀元，其中有1枚略輕的是假銀元，你能用天平(無砝碼)將假銀元找出來嗎？解：法1算法如下：第一步，任取2枚銀元分別放在天平的兩邊，若天平左、右不平衡，則輕的一枚就是假銀元，若天平平衡，則進(jìn)行第二步．第二步，取下右邊的銀元放在一邊，然后把剩下的7枚銀元依次放在右邊進(jìn)行稱量，直到天平不平衡，偏輕的那一枚就是假銀元．法2算法如下：第一步，把9枚銀元平均分成3組，每組3枚．第二步，先將其中兩組放在天平的兩邊，若天平不平衡，則假銀元就在輕的那一組；否則假銀元在未稱量的那一組．第三步，取出含假銀元的那一組，從中任取2枚銀元放在天平左、右兩邊稱量，若天平不平衡，則假銀元在輕的那一邊；若天平平衡，則未稱量的那一枚是假銀元．——易錯(cuò)警示——對(duì)算法的概念理解錯(cuò)誤【例6】用自然語言描述求y＝－x2－2x＋3的最大值的算法．【錯(cuò)解】第一步，配方得y＝－(x＋1)2＋4.第二步，函數(shù)的最大值為4.【錯(cuò)解分析】作為一個(gè)具體問題來說，上述解法沒有什么錯(cuò)誤，但是我們要描述的是求這一類問題的算法，它可以用來解決這個(gè)問題，也可以用來求這一類問題，則上述解法就欠妥了．應(yīng)就y＝ax2＋bx＋c作一般討論．【正解】第一步，給a，b，c賦值．第二步，判斷a≥0是否成立，若成立，則輸出“函數(shù)無最大值”，結(jié)束算法；否則執(zhí)行第三步．第三步，計(jì)算eq\f(4ac－b2,4a)，并將結(jié)果賦給max.第四步，輸出max，結(jié)束算法．(算法執(zhí)行過程中，依次給a、b、c取值－1、－2、3)設(shè)計(jì)算法，給定任一x的值，求y的值，其中y＝eq\b\lc\{\rc\(\a\vs4\al\co1(2x－1，x≤0，,x2＋1，x>0.))解：第一步，輸入x的值．第二步，判斷x是否大于零，若x>0，執(zhí)行第三步；否則，執(zhí)行第四步．第三步，計(jì)算y＝x2＋1的值，轉(zhuǎn)去執(zhí)行第五步．第四步，計(jì)算y＝2x－1的值．第五步，輸出y的值．一、選擇題1．下列語句表達(dá)中是算法的有(C)①?gòu)臐?jì)南到巴黎可以先乘火車到北京，再坐飛機(jī)抵達(dá)；②利用公式S＝eq\f(1,2)ah計(jì)算底為1，高為2的三角形的面積；③eq\f(1,2)x>2x＋4；④求M(1,2)與N(－3，－5)兩點(diǎn)所在直線的方程，可先求MN的斜率，再利用點(diǎn)斜式求方程．A．1個(gè)B．2個(gè)C．3個(gè)D．4個(gè)解析：算法是解決某類問題的步驟與過程，這個(gè)問題并不僅僅限于數(shù)學(xué)問題，①②④都表達(dá)了一種算法，故應(yīng)選C.2．588與378的最大公因數(shù)是(D)A．6 B．14C．21 D．42解析：588＝22×3×72,378＝2×33×7，所以588