【同步備課】高中數(shù)學(北師大版)必修三教案：2.1-算法的概念文字資料

算法的概念算法是指完成一個任務所需要的具體步驟和方法。也就是說給定初始狀態(tài)或輸入數(shù)據(jù)，經(jīng)過計算機程序的有限次運算，能夠得出所要求或期望的終止狀態(tài)或輸出數(shù)據(jù)。算法經(jīng)常含有重復的步驟和一些比較或規(guī)律推斷。假如一個算法有缺陷，或不適合于某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優(yōu)劣可以用空間簡單度與時間簡單度來衡量?！妓惴ǖ臍v史〗“算法”(algorithm)來自于9世紀波斯數(shù)學家比阿勒?霍瓦里松的名字al-Khwarizmi，比阿勒?霍瓦里松在數(shù)學上提出了算法這個概念。“算法”原為"algorism"，意思是阿拉伯數(shù)字的運算法則，在18世紀演化為"algorithm"。第一次編寫算法是AdaByron于1842年為巴貝奇分析機編寫求解解伯努利方程的程序，因此AdaByron被大多數(shù)人認為是世界上第一位程序員。由于巴貝奇(CharlesBabbage)未能完成他的巴貝奇分析機，這個算法未能在巴貝奇分析機上執(zhí)行。由于"well-definedprocedure"缺少數(shù)學上精確的定義，19世紀和20世紀早期的數(shù)學家、規(guī)律學家在定義算法上消滅了困難。20世紀的英國數(shù)學家圖靈提出了有名的圖靈論題，并提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。圖靈機的消滅解決了算法定義的難題，圖靈的思想對算法的進展起到了重要的作用?！妓惴ǖ奶卣鳌揭粋€算法應當具有以下五個重要的特征：有窮性：一個算法必需保證執(zhí)行有限步之后結(jié)束；精確?????性：算法的每一步驟必需有精確?????的定義；輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始狀況，所謂0個輸入是指算法本身定除了初始條件；輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；可行性：算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成?！夹问交惴ā剿惴ㄊ怯嬎銠C處理信息的本質(zhì)，由于計算機程序本質(zhì)上是一個算法來告知計算機精確?????的步驟來執(zhí)行一個指定的任務，如計算職工的薪水或打印同學的成果單。一般地，當算法在處理信息時，會從輸入設(shè)備或數(shù)據(jù)的存儲地址讀取數(shù)據(jù)，把結(jié)果寫入輸出設(shè)備或某個存儲地址供以后再調(diào)用?！妓惴ǖ膶崿F(xiàn)〗算法不單單可以用計算機程序來實現(xiàn)，也可以在神經(jīng)網(wǎng)絡、電路或者機械設(shè)備上實現(xiàn)。?例子這是算法的一個簡潔的例子。我們有一串隨機數(shù)列。我們的目的是找到這個數(shù)列中最大的數(shù)。假如將數(shù)列中的每一個數(shù)字看成是一顆豆子的大小,可以將下面的算法形象地稱為“撿豆子”：首先將第一顆豆子放入口袋中。從其次顆豆子開頭檢查，直到最終一顆豆子。假如正在檢查的豆子比口袋中的還大，則將它撿起放入口袋中，同時丟掉原先口袋中的豆子。最終口袋中的豆子就是全部的豆子中最大的一顆。下面是一個形式算法，用近似于編程語言的偽代碼表示給定：一個數(shù)列“l(fā)ist"，以及數(shù)列的長度"length(list)"largest=list[1]forcounter=2tolength(list):iflist[counter]>largest:largest=list[counter]printlargest符號說明:=用于表示賦值。即：右邊的值被賜予給左邊的變量。List[counter]用于表示數(shù)列中的第counter項。例如：假如counter的值是5，那么List[counter]表示數(shù)列中的第5項。<=用于表示“小于或等于”。＝＝例子＝＝求兩個自然數(shù)的最大公約數(shù)設(shè)兩個變量M和N1.假如M<N，則交換M和N2.以N除以M，得到余數(shù)R3.推斷R＝0，正確則N即為“最大公約數(shù)”，否則下一步4.將N賦值給M，將R賦值給N，重做第一步。用“Basic代碼”表示－－IfM<NThenSwapM,NDoWhileR<>0R=MModNM=NN=RLoopPrintR〖算法設(shè)計和分析的基本方法〗分治法：字面上的解釋是“分而治之”，就是把一個簡單的問題分成兩個或更多的相同或相像的子問題，再把子問題分成更小的子問題……直到最終子問題可以簡潔的直接求解，原問題的解即子問題的解的合并。這個技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)……動態(tài)規(guī)劃：動態(tài)規(guī)劃在查找有很多重疊子問題的狀況的最優(yōu)解時有效。它將問題重新組合成子問題。為了避開多次解決這些子問題，它們的結(jié)果都漸漸被計算并被保存，從簡潔的問題直到整個問題都被解決。因此，動態(tài)規(guī)劃保存遞歸時的結(jié)果，因而不會在解決同樣的問題時花費時間。貪心法（亦作饕餮法）：就是一種在每一步選擇中都實行在當前狀態(tài)下最好/優(yōu)的選擇，從而期望導致結(jié)果是最好/優(yōu)的算法。貪心法可以解決一些最優(yōu)性問題，如：求圖中的最小生成樹、求哈夫曼編碼……對于其他問題，貪心法一般不能得到我們所要求的答案。一旦一個問題可以通過貪心法來解決，那么貪心法一般是解決這個問題的最好方法。由于貪心法的高效性以及其所求得的答案比較接近最優(yōu)結(jié)果，貪心法也可以用作幫助算法或者直接解決一些要求結(jié)果不特殊精確的問題?！妓惴ǖ姆诸悺?基本算法〔枚舉搜尋（深度優(yōu)先搜尋廣度優(yōu)先搜尋啟發(fā)式搜尋遺傳算法）〕?數(shù)據(jù)結(jié)構(gòu)的算法?數(shù)論與代數(shù)算法?計算幾何的算法（凸包算法）?圖論的算法（哈夫曼編碼樹的遍歷最短路徑算法最小生成樹算法最小樹形圖網(wǎng)絡流算法匹配算法）?動態(tài)規(guī)劃?其他（數(shù)值分析加密算法排序算法檢索算法隨機化算法）還可以分成串行算法、并行算法?！妓惴ǖ暮唵涡浴剿惴ǖ暮唵涡允撬惴ㄐ实亩攘?，在評價算法性能時，簡單性是一個重要的依據(jù)。算法的簡單性的程度與運行該算法所需要的計算機資源的多少有關(guān)，所需要的資源越多，表明該算法的簡單性越高；所需要的資源越少，表明該算法的簡單性越低。計算機的資源，最重要的是運算所需的時間和存儲程序和數(shù)據(jù)所需的空間資源，算法的簡單性有時間簡單性和空間簡單性之分。算法在計算機上執(zhí)行運算，需要肯定的存儲空間存放描述算法的程序和算法所需的數(shù)據(jù)，計算機完成運算任務需要肯定的時間。依據(jù)不同的算法寫出的程序放在計算機上運算時，所需要的時間和空間是不同的，算法的簡單性是對算法運算所需時間和空間的一種度量。不同的計算機其運算速度相差很大，在衡量一個算法的簡單性要留意到這一點。對于任意給定的問題，設(shè)計出簡單性盡可能低的算法是在設(shè)計算法時考慮的一個重要目標。另外，當給定的問題已有多種算法時，選擇其中簡單性最低者，是在選用算法時應遵循的一個重要準則。因此，算法的簡單性分析對算法的設(shè)計或選用有著重要的指導意義和有用價值。在爭辯算法的簡單性時，有兩個問題要弄清楚：(1)一個算法的簡單性用怎樣的一個量來表達；(2)怎樣計算一個給定算法的簡單性。找到求解一個問題的算法后，接著就是該算法的實現(xiàn)，至于是否可以找到實現(xiàn)的方法，取決于算法的可計算性和計算的簡單性，該問題是否存在求解算法，能否供應算法所需要的時間資源和空間資源。篩選法求質(zhì)數(shù)質(zhì)數(shù)亦叫作素數(shù)，是大于1的自然數(shù)，并且除了該數(shù)本身和1以外沒有其它的數(shù)能整除它，如2，3，5，7，11，13，…，質(zhì)數(shù)有無窮多個。（1）推斷143是否為質(zhì)數(shù)。解：Step1：143÷2不為整數(shù)；Step2：143÷3不為整數(shù)；Step3：143÷4不為整數(shù)；Step4：143÷5不為整數(shù)；Step5：143÷6不為整數(shù)；Step6：143÷7不為整數(shù)；Step7：143÷8不為整數(shù)；Step8：143÷9不為整數(shù)；Step9：143÷10不為整數(shù)；Step10：143÷11=13，143能被11整除；Step11：結(jié)論：143不是質(zhì)數(shù)。（2）推斷17是否為質(zhì)數(shù)。解：Step1：17÷2不為整數(shù)；Step2：17÷3不為整數(shù)；Step3：17÷4不為整數(shù)；Step4：17÷5不為整數(shù)；Step5：17÷6不為整數(shù)；Step6：17÷7不為整數(shù)；Step7：17÷8不為整數(shù)；Step8：17÷9不為整數(shù)；Step9：17÷10不為整數(shù)；Step10：17÷11不為整數(shù)；Step11：17÷12不為整數(shù)；Step12：17÷13不為整數(shù)；Step13：17÷14不為整數(shù)；Step14：17÷15不為整數(shù)；Step15：17÷16不為整數(shù)；Step16：結(jié)論：17是質(zhì)數(shù)