【優(yōu)教通-備課參考】2020年高中數(shù)學(xué)同步學(xué)案：第2章-算法初步-算法的概念文字(北師大版必修3)

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