【優(yōu)教通-備課參考】2020年高中數(shù)學同步學案:第2章-算法初步-算法的概念文字(北師大版必修3)_第1頁
【優(yōu)教通-備課參考】2020年高中數(shù)學同步學案:第2章-算法初步-算法的概念文字(北師大版必修3)_第2頁
【優(yōu)教通-備課參考】2020年高中數(shù)學同步學案:第2章-算法初步-算法的概念文字(北師大版必修3)_第3頁
全文預覽已結束

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

算法的概念算法是指完成一個任務所需要的具體步驟和方法。也就是說給定初始狀態(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í)行有限步之后結束;精確?????性:算法的每一步驟必需有精確?????的定義;輸入:一個算法有0個或多個輸入,以刻畫運算對象的初始狀況,所謂0個輸入是指算法本身定除了初始條件;輸出:一個算法有一個或多個輸出,以反映對輸入數(shù)據(jù)加工后的結果。沒有輸出的算法是毫無意義的;可行性:算法原則上能夠精確地運行,而且人們用筆和紙做有限次運算后即可完成?!夹问交惴ā剿惴ㄊ怯嬎銠C處理信息的本質(zhì),由于計算機程序本質(zhì)上是一個算法來告知計算機精確?????的步驟來執(zhí)行一個指定的任務,如計算職工的薪水或打印同學的成果單。一般地,當算法在處理信息時,會從輸入設備或數(shù)據(jù)的存儲地址讀取數(shù)據(jù),把結果寫入輸出設備或某個存儲地址供以后再調(diào)用?!妓惴ǖ膶崿F(xiàn)〗算法不單單可以用計算機程序來實現(xiàn),也可以在神經(jīng)網(wǎng)絡、電路或者機械設備上實現(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ù)設兩個變量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〖算法設計和分析的基本方法〗分治法:字面上的解釋是“分而治之”,就是把一個簡潔的問題分成兩個或更多的相同或相像的子問題,再把子問題分成更小的子問題……直到最終子問題可以簡潔的直接求解,原問題的解即子問題的解的合并。這個技巧是很多高效算法的基礎,如排序算法(快速排序,歸并排序),傅立葉變換(快速傅立葉變換)……動態(tài)規(guī)劃:動態(tài)規(guī)劃在查找有很多重疊子問題的狀況的最優(yōu)解時有效。它將問題重新組合成子問題。為了避開多次解決這些子問題,它們的結果都漸漸被計算并被保存,從簡潔的問題直到整個問題都被解決。因此,動態(tài)規(guī)劃保存遞歸時的結果,因而不會在解決同樣的問題時花費時間。貪心法(亦作饕餮法):就是一種在每一步選擇中都實行在當前狀態(tài)下最好/優(yōu)的選擇,從而期望導致結果是最好/優(yōu)的算法。貪心法可以解決一些最優(yōu)性問題,如:求圖中的最小生成樹、求哈夫曼編碼……對于其他問題,貪心法一般不能得到我們所要求的答案。一旦一個問題可以通過貪心法來解決,那么貪心法一般是解決這個問題的最好方法。由于貪心法的高效性以及其所求得的答案比較接近最優(yōu)結果,貪心法也可以用作掛念算法或者直接解決一些要求結果不特殊精確的問題?!妓惴ǖ姆诸悺?基本算法〔枚舉搜尋(深度優(yōu)先搜尋廣度優(yōu)先搜尋啟發(fā)式搜尋遺傳算法)〕?數(shù)據(jù)結構的算法?數(shù)論與代數(shù)算法?計算幾何的算法(凸包算法)?圖論的算法(哈夫曼編碼樹的遍歷最短路徑算法最小生成樹算法最小樹形圖網(wǎng)絡流算法匹配算法)?動態(tài)規(guī)劃?其他(數(shù)值分析加密算法排序算法檢索算法隨機化算法)還可以分成串行算法、并行算法?!妓惴ǖ暮啙嵭浴剿惴ǖ暮啙嵭允撬惴ㄐ实亩攘?,在評價算法性能時,簡潔性是一個重要的依據(jù)。算法的簡潔性的程度與運行該算法所需要的計算機資源的多少有關,所需要的資源越多,表明該算法的簡潔性越高;所需要的資源越少,表明該算法的簡潔性越低。計算機的資源,最重要的是運算所需的時間和存儲程序和數(shù)據(jù)所需的空間資源,算法的簡潔性有時間簡潔性和空間簡潔性之分。算法在計算機上執(zhí)行運算,需要確定的存儲空間存放描述算法的程序和算法所需的數(shù)據(jù),計算機完成運算任務需要確定的時間。依據(jù)不同的算法寫出的程序放在計算機上運算時,所需要的時間和空間是不同的,算法的簡潔性是對算法運算所需時間和空間的一種度量。不同的計算機其運算速度相差很大,在衡量一個算法的簡潔性要留意到這一點。對于任意給定的問題,設計出簡潔性盡可能低的算法是在設計算法時考慮的一個重要目標。另外,當給定的問題已有多種算法時,選擇其中簡潔性最低者,是在選用算法時應遵循的一個重要準則。因此,算法的簡潔性分析對算法的設計或選用有著重要的指導意義和有用價值。在爭辯算法的簡潔性時,有兩個問題要弄清楚:(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:結論: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:結論:17是質(zhì)數(shù)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論