數(shù)學(xué)名師導(dǎo)航算法的含義

學(xué)必求其心得，業(yè)必貴于專精學(xué)必求其心得，業(yè)必貴于專精學(xué)必求其心得，業(yè)必貴于專精5。1算法的含義名師導(dǎo)航三點(diǎn)剖析一、算法的含義在日常生活中做任何一件事情，都是按照一定規(guī)則,一步一步進(jìn)行,比如在工廠中生產(chǎn)一部機(jī)器，先把零件按一道道工序進(jìn)行加工，然后,再把各種零件按一定法則組裝成一部完整的機(jī)器，它們的工藝流程就是算法;在農(nóng)村中種莊稼有耕地、播種、育苗、施肥、中耕、收割等各個(gè)環(huán)節(jié)，這些栽培技術(shù)也是算法?？傊?，在任何這些數(shù)值計(jì)算或非數(shù)值計(jì)算的過(guò)程中所采取的方法和步驟，都稱之為算法。一般而言，對(duì)一類問(wèn)題的機(jī)械的、統(tǒng)一的求解方法稱為算法.注意：1。這種描述不是算法的嚴(yán)格定義，但是反映了算法的基本思想.算法的基本思想就是程序化思想。2.簡(jiǎn)單地說(shuō)，算法是完成某項(xiàng)工作的一系列步驟?，F(xiàn)代意義上的“算法”通常是指可以用計(jì)算機(jī)來(lái)解決的某一類問(wèn)題的程序或步驟，這些程序或步驟必須是明確和有效的,而且能夠在有限步之內(nèi)完成.3.算法的概念源于數(shù)學(xué)。比如數(shù)學(xué)中常用的配方法、換元法、待定系數(shù)法等都是解決某一類特定問(wèn)題的方法，它們的特點(diǎn)是對(duì)于某一類特定的問(wèn)題都有效，都有固定的、機(jī)械的步驟，每一步都能得到惟一的結(jié)果，只要嚴(yán)格按照步驟進(jìn)行，就一定可以解決問(wèn)題.但不要認(rèn)為只有“計(jì)算”的問(wèn)題才有算法。廣義地說(shuō)，為解決一個(gè)問(wèn)題而采取的方法,就稱為算法.例如，我們要發(fā)一封電子郵件，一般需要經(jīng)歷以下幾個(gè)步驟：第一步，打開電子郵箱；第二步，點(diǎn)擊“寫郵件"；第三步,輸入發(fā)送地址;第四步，輸入主題；第五步，輸入信件內(nèi)容；第六步，點(diǎn)擊“發(fā)送郵件”.這些步驟從廣義上來(lái)講也可以稱作是發(fā)一封電子郵件的算法.4。計(jì)算機(jī)解決任何問(wèn)題都要依賴于算法。只有將解決問(wèn)題的過(guò)程分解為若干個(gè)明確的步驟，即算法,并用計(jì)算機(jī)能夠接受的“語(yǔ)言”準(zhǔn)確地描述出來(lái)，計(jì)算機(jī)才能夠解決問(wèn)題.我們知道，計(jì)算機(jī)本質(zhì)上就是一個(gè)機(jī)械,只不過(guò)是一個(gè)非常復(fù)雜的機(jī)械罷了。和所有的機(jī)械一樣，它能根據(jù)特定的指令執(zhí)行特定的任務(wù).我們不妨拿我們所熟悉的一種機(jī)械——鋼琴來(lái)說(shuō)明這個(gè)道理.鋼琴對(duì)于人的特定的命令（按鍵或按鍵組合）會(huì)發(fā)出特定的、固定的聲音，并且這種基本的對(duì)應(yīng)關(guān)系是有限的。正是由于掌握了這種固定的對(duì)應(yīng)關(guān)系，鋼琴家才能夠以此為基礎(chǔ)進(jìn)行創(chuàng)作，如果沒(méi)有這種固定的對(duì)應(yīng)關(guān)系，鋼琴家也就無(wú)法駕馭鋼琴，更談不上彈奏出優(yōu)美的旋律了。計(jì)算機(jī)也是一樣，它對(duì)于特定的命令（基本命令或由基本命令組合而成的復(fù)雜命令），能作出固定的反應(yīng)(例如對(duì)于命令2+3，計(jì)算機(jī)的反應(yīng)就是計(jì)算出這個(gè)算式的值為5），像這種計(jì)算機(jī)能接受并執(zhí)行的基本命令或由基本命令所組合而成的復(fù)雜命令就是計(jì)算機(jī)能夠接受的“語(yǔ)言",也正是依靠這種“語(yǔ)言”，我們才能與計(jì)算機(jī)進(jìn)行“交流”并且讓計(jì)算機(jī)為我們所用，按照我們的意圖去解決問(wèn)題.二、算法的特性一般來(lái)講，一個(gè)算法應(yīng)具有以下五個(gè)重要特性:1．有窮性：一個(gè)算法必須總是（對(duì)任何合法的輸入值）在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成。算法具有有窮性是為了讓算法不能無(wú)休止地執(zhí)行下去，以致達(dá)不到解決問(wèn)題的目的。數(shù)學(xué)中的無(wú)窮級(jí)數(shù)，在實(shí)際計(jì)算時(shí)只能取有限項(xiàng),即計(jì)算無(wú)窮級(jí)數(shù)的過(guò)程只能是有窮的.因此，一個(gè)無(wú)窮級(jí)數(shù)的表示只能是一個(gè)計(jì)算公式,而根據(jù)精度要求確定的計(jì)算過(guò)程才是有窮的算法.2．確定性:算法中每一條指令必須有確切的含義，讀者理解時(shí)不會(huì)產(chǎn)生歧義。也就是說(shuō),算法的步驟中不能含有模糊不清、容易讓人誤解的敘述.確定性是要保證算法在執(zhí)行過(guò)程中,不能因不同的人的喜好、理解不同及其他人為因素而“走樣”.事實(shí)上，在程序設(shè)計(jì)中，一個(gè)算法必須確定到這樣一個(gè)程度，即使一臺(tái)計(jì)算機(jī)也能遵循這個(gè)指示正確執(zhí)行。從這個(gè)角度我們可以看到算法的步驟的一個(gè)特點(diǎn)就是：清晰、準(zhǔn)確而又機(jī)械、刻板、缺乏創(chuàng)造性(但從算法步驟的執(zhí)行上講也不需要有創(chuàng)造性，能嚴(yán)格執(zhí)行就可以了）。3．可行性:算法的可行性包括兩個(gè)方面:一是算法中的每一個(gè)步驟必須是能實(shí)現(xiàn)的.例如，在算法中，不允許出現(xiàn)分母為零的情況；在實(shí)數(shù)范圍內(nèi)不能求一個(gè)負(fù)數(shù)的平方根等.二是算法執(zhí)行的結(jié)果能達(dá)到預(yù)期的目的.通常，針對(duì)實(shí)際問(wèn)題設(shè)計(jì)的算法，人們總是希望能得到滿意的結(jié)果。當(dāng)然可行性對(duì)于不同的人及不同的時(shí)代具有不同的含義。僅就計(jì)算工具上來(lái)講，古代最好的計(jì)算工具大概就是算盤了，而現(xiàn)代的超級(jí)計(jì)算機(jī)無(wú)論是在計(jì)算的速度還是在可計(jì)算問(wèn)題的范圍上都遠(yuǎn)在其上。古代很多不能完成的計(jì)算在現(xiàn)代都變成了可能。4．輸入：算法一定要根據(jù)輸入的初始數(shù)據(jù)或給定的初值才能正確執(zhí)行它的每一步驟.需要注意的是,算法的輸入數(shù)據(jù)和輸出數(shù)據(jù)都應(yīng)該是離散（分散的、不連續(xù)的、可逐個(gè)計(jì)算的數(shù)據(jù)）的符號(hào)(或稱字母，其中也包括數(shù)字)，例如不能輸入一條連續(xù)的曲線。（連續(xù)曲線上的點(diǎn)是連續(xù)的，無(wú)法對(duì)所有點(diǎn)所對(duì)應(yīng)數(shù)據(jù)逐個(gè)進(jìn)行計(jì)算)這是因?yàn)樗惴ㄒ话愣际强坑?jì)算機(jī)來(lái)執(zhí)行的，而數(shù)字電子計(jì)算機(jī)是一個(gè)離散結(jié)構(gòu)，它只能處理離散的或離散化了的數(shù)量關(guān)系.因此，無(wú)論計(jì)算機(jī)科學(xué)本身,還是與計(jì)算機(jī)科學(xué)及其應(yīng)用密切相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域,都面臨著如何對(duì)離散結(jié)構(gòu)建立相應(yīng)的數(shù)學(xué)模型,又如何將已用連續(xù)數(shù)量關(guān)系建立起來(lái)的數(shù)學(xué)模型離散化，從而可由計(jì)算機(jī)加以處理.5．輸出：算法一定能得到問(wèn)題的解，有一個(gè)或多個(gè)的輸出，達(dá)到求解問(wèn)題的目的.這些輸出是同輸入有著某些特定關(guān)系的量.沒(méi)有輸出結(jié)果的算法是沒(méi)有意義的。此外,還要求算法應(yīng)具有通用性：即算法應(yīng)適用于某一類問(wèn)題中的所有個(gè)體，而不是只能用來(lái)解決一個(gè)具體問(wèn)題.例如一個(gè)能解所有二元一次方程組的算法就比一個(gè)只能解某一個(gè)特定的二元一次方程組的算法更具有通用性.三、算法的描述描述算法可以有不同的方式，常用的有自然語(yǔ)言、框圖(流程圖)、程序設(shè)計(jì)語(yǔ)言、偽代碼等。1．自然語(yǔ)言：就是人們?nèi)粘Ｊ褂玫恼Z(yǔ)言。用自然語(yǔ)言描述算法的優(yōu)點(diǎn)是通俗易懂，當(dāng)算法中的操作步驟都是順序執(zhí)行時(shí)比較容易理解.缺點(diǎn)是如果算法中包含判斷和轉(zhuǎn)向等較復(fù)雜的過(guò)程時(shí)，就會(huì)顯得不夠清晰、直觀了，并且敘述會(huì)較煩瑣和冗長(zhǎng),并且容易出現(xiàn)歧義.2．流程圖：是用一組幾何圖形表示各種類型的操作,在圖形上用簡(jiǎn)明扼要的文字和符號(hào)表示具體的操作，并用帶有箭頭的流線表示操作的先后次序.用框圖描述算法，具有直觀、結(jié)構(gòu)清晰、條理分明、通俗易懂、便于檢查修改及交流等優(yōu)點(diǎn).3．程序設(shè)計(jì)語(yǔ)言：“算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)”，計(jì)算機(jī)完成任何一項(xiàng)任務(wù)都需要算法.但是，用自然語(yǔ)言或程序框圖描述的算法計(jì)算機(jī)是無(wú)法“理解”的，我們還需要將算法用計(jì)算機(jī)能夠理解的語(yǔ)言表達(dá)出來(lái),通常這稱為程序設(shè)計(jì)，所用的語(yǔ)言稱為程序設(shè)計(jì)語(yǔ)言（programminglanguage）.程序設(shè)計(jì)語(yǔ)言由一些有特定含義的程序語(yǔ)句構(gòu)成，與算法程序框圖的三種基本結(jié)構(gòu)相對(duì)應(yīng)，任何程序設(shè)計(jì)語(yǔ)言都包含輸入輸出語(yǔ)句、賦值語(yǔ)句、條件語(yǔ)句和循環(huán)語(yǔ)句.不同的程序設(shè)計(jì)語(yǔ)言有不同的語(yǔ)句形式和語(yǔ)法規(guī)則，但基本結(jié)構(gòu)是相同的。正是由于這樣的原因，在研究算法的時(shí)候，有時(shí)并不很關(guān)心算法語(yǔ)句是否用的是某種精確的程序語(yǔ)言，而采用基本結(jié)構(gòu)相同的更為簡(jiǎn)便易懂的語(yǔ)言形式，有人稱之為偽代碼.問(wèn)題探究問(wèn)題1：算法的概念和我們生活中所遇到的許多概念有類似的地方.如菜譜，就是指導(dǎo)人們?nèi)绾巫霾说?那么,菜譜的概念和算法的概念究竟有哪些相同點(diǎn)和不同點(diǎn)呢？探究：我們知道，算法有五個(gè)重要的特征,即有窮性、確定性、可行性、有輸入、有輸出。于是我們想到可以根據(jù)算法的特性對(duì)菜譜逐一進(jìn)行對(duì)比來(lái)探究這個(gè)問(wèn)題.首先，容易想到，菜譜總是符合有窮性的要求的（廚師肯定不會(huì)花無(wú)限多的時(shí)間來(lái)做一盤菜吧?）.其次，可行性也是菜譜所具有的（做菜的步驟必須是廚師力所能及的）。輸入就是作菜的原料(如雞蛋、西紅柿、糖、鹽等)，輸出就是做好的菜了（如雞蛋炒西紅柿等).但是對(duì)于確定性，菜譜就不是那么令人滿意了.例如，步驟“加少許鹽”,“鹽”也許已經(jīng)是明確的定義了；那么“少許”該是多少呢，算法要求每一步都是精確的，按照這個(gè)標(biāo)準(zhǔn)，“少許"這樣模糊的詞句是不被允許的，當(dāng)然我們可以將這個(gè)步驟改為如“加2.2g鹽"這樣的敘述，但鹽應(yīng)該加到哪(頂上、邊上等等）也不是很明確的.也許像“輕輕地顛簸直到混合物發(fā)脆為止”、“在小長(zhǎng)柄鍋里加熱的料酒”等等指示，對(duì)于訓(xùn)練有素的廚師來(lái)說(shuō),說(shuō)明已經(jīng)是足夠了，但是一個(gè)算法必須確定到這樣一個(gè)程度:即使一臺(tái)計(jì)算機(jī)也能遵循這個(gè)指示。因此從嚴(yán)格的意義上來(lái)講,菜譜并不能稱為算法。問(wèn)題2：在實(shí)際問(wèn)題和算法理論中,找出好的算法是一項(xiàng)重要的工作。但是對(duì)于“好”沒(méi)有嚴(yán)格的定義。一個(gè)好的算法都應(yīng)該滿足哪些標(biāo)準(zhǔn)？探究：算法就其本質(zhì)來(lái)講，就是一種解決問(wèn)題的方法，只不過(guò)更具有程序化罷了.我們可以根據(jù)自己的經(jīng)驗(yàn)，思考一個(gè)好的解決問(wèn)題的方法應(yīng)該具有哪些特點(diǎn)，然后看這些特點(diǎn)在算法上都應(yīng)該有什么樣的體現(xiàn),就可以回答這個(gè)問(wèn)題了.正如所有的好的解決問(wèn)題的方法必須是正確的一樣，一個(gè)好的算法首先必須是正確的.正確性對(duì)不同的事情有著不同的含義.對(duì)于算法來(lái)講，正確性包含如下幾個(gè)層次：(1）算法不能含有語(yǔ)法錯(cuò)誤，否則算法不能正常執(zhí)行；(2）算法對(duì)于幾組輸入數(shù)據(jù),能夠得出滿足規(guī)格說(shuō)明要求的結(jié)果；（3）算法對(duì)于精心選擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù),能夠得出滿足規(guī)格說(shuō)明要求的結(jié)果；(4）算法對(duì)于一切合法的輸入數(shù)據(jù)，都能產(chǎn)生滿足規(guī)格說(shuō)明要求的結(jié)果.其次，我們?nèi)菀紫氲揭粋€(gè)好的解決問(wèn)題的方法,應(yīng)該是思路清晰、讓人容易理解的，這樣就可以讓更多的人掌握我們的方法。同理，我們寫出的算法要具有可讀性，格式要工整、規(guī)范，思想要清晰、準(zhǔn)確,以便和其他人更好地交流、合作.世事無(wú)常，在我們解決問(wèn)題的過(guò)程中，往往不可避免地會(huì)有意外情況發(fā)生，這要求我們解決問(wèn)題的方法要對(duì)這些意外情況制定相應(yīng)的對(duì)策，避免不必要的損失。同理,我們的算法要具有健壯性，它的含義就是要求算法能夠在出現(xiàn)異?；蛲话l(fā)事件時(shí)能正常運(yùn)行，不至于因?yàn)椴僮鳝h(huán)節(jié)中的錯(cuò)誤而造成災(zāi)難性的后果.此外，我們做事還要考慮這件事需要花費(fèi)的時(shí)間和占用的空間.一般來(lái)講，花費(fèi)時(shí)間和占用空間少的方法會(huì)更好。同樣的，算法也有高效率與低存儲(chǔ)量需求。效率指的是算法執(zhí)行時(shí)間.對(duì)于解決同一問(wèn)題的多個(gè)算法,執(zhí)行時(shí)間短的算法效率高。存儲(chǔ)量需求是指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間.如果所占空間量依賴于特定的輸入，則除特別指明外，均按最壞情況來(lái)分析.精題精講例1．給出求1+3+5+7+9+11+13的一個(gè)算法.思路解析分析一:本題主要是考查理解概念的程度。由于本題是一個(gè)連續(xù)相加的問(wèn)題，則寫算法時(shí)，只需按照逐一相加的程序進(jìn)行.分析二：由于1+3+5+…+(2n-1)＝n2，所以可以運(yùn)用公式1+3+5+…+（2n-1)＝n2直接計(jì)算,只需將n＝7代入公式即可。答案：解法一：按照逐一相加的程序進(jìn)行:第一步計(jì)算1+3，得到4；第二步將第一步中的運(yùn)算結(jié)果4與5相加，得到9；第三步將第二步中的運(yùn)算結(jié)果9與7相加，得到16；第四步將第三步中的運(yùn)算結(jié)果16與9相加，得到25；第五步將第四步中的運(yùn)算結(jié)果25與11相加，得到36；第六步將第五步中的運(yùn)算結(jié)果36與13相加，得到49.解法二：運(yùn)用公式1+3+5+…+（2n-1)＝n2計(jì)算：第一步取n＝7；第二步計(jì)算n2；第三步輸出運(yùn)算結(jié)果.綠色通道對(duì)算法的靈活、準(zhǔn)確應(yīng)用和自然語(yǔ)言表達(dá)問(wèn)題，要注意：算法的方法不同,解決問(wèn)題的繁簡(jiǎn)程度也不同.我們研究算法，就是要找出解決問(wèn)題的最好的算法。例2．給出求解方程ax2+bx+c=0（a≠0，b2—4ac思路解析解一元二次方程一般利用求根公式來(lái)求解,即，當(dāng)方程左邊的二次多項(xiàng)式可分解因式時(shí)，我們也可用分解因式的方法來(lái)解一元二次方程。答案：算法如下：第一步寫出方程中的a、b、c的值；第二步計(jì)算b2-4ac的值；第三步計(jì)算的值；第四步輸出方程的根為。綠色通道一個(gè)算法,就是一個(gè)有窮規(guī)則的集合，它為某個(gè)特定類型問(wèn)題提供了解決問(wèn)題的運(yùn)算序列.其中的每條規(guī)則必須是明確定義的、可行的.序列的終止表示問(wèn)題得到解答或指出問(wèn)題沒(méi)有解答。例3．一個(gè)人帶三只狼和三只羚羊過(guò)河，只有一條船，同船可以容一個(gè)人和兩只動(dòng)物.沒(méi)有人在的時(shí)候，如果狼的數(shù)量不少于羚羊的數(shù)量，狼就會(huì)吃掉羚羊.（1）設(shè)計(jì)一個(gè)安全渡河的算法；(2)思考每一步算法所遵循的相同原則是什么?思路解析在人運(yùn)送動(dòng)物過(guò)河