資源描述：
《算法設(shè)計與分析(王曉東).ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、中國計算機學(xué)會 “21世紀大學(xué)本科計算機專業(yè)系列教材”算法設(shè)計與分析王曉東編著1主要內(nèi)容介紹第1章算法引論第2章遞歸與分治策略第3章動態(tài)規(guī)劃第4章貪心算法第5章回溯法第6章分支限界法2主要內(nèi)容介紹（續(xù)）第7章概率算法第8章NP完全性理論第9章近似算法第10章算法優(yōu)化策略3第1章算法引論1.1算法與程序1.2表達算法的抽象機制1.3描述算法1.4算法復(fù)雜性分析本章主要知識點：41.1算法與程序輸入：有零個或多個外部量作為算法的輸入。輸出：算法產(chǎn)生至少一個量作為輸出。確定性：組成算法的每條指令清晰、無歧義。有
2、限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限。是算法用某種程序設(shè)計語言的具體實現(xiàn)。程序可以不滿足算法的性質(zhì)(4)即有限性。是滿足下述性質(zhì)的指令序列。算法：程序：51.從機器語言到高級語言的抽象1.2表達算法的抽象機制高級程序設(shè)計語言的主要好處是：（4）把繁雜瑣碎的事務(wù)交給編譯程序，所以自動化程度高，開發(fā)周期短，程序員可以集中時間和精力從事更重要的創(chuàng)造性勞動，提高程序質(zhì)量。（1）高級語言更接近算法語言，易學(xué)、易掌握，一般工程技術(shù)人員只需要幾周時間的培訓(xùn)就可以勝任程序員的工作；（2）高級語言為
3、程序員提供了結(jié)構(gòu)化程序設(shè)計的環(huán)境和工具，使得設(shè)計出來的程序可讀性好，可維護性強，可靠性高；（3）高級語言不依賴于機器語言，與具體的計算機硬件關(guān)系不大，因而所寫出來的程序可植性好、重用率高；62.抽象數(shù)據(jù)類型1.2表達算法的抽象機制抽象數(shù)據(jù)類型是算法的一個數(shù)據(jù)模型連同定義在該模型上并作為算法構(gòu)件的一組運算。抽象數(shù)據(jù)類型帶給算法設(shè)計的好處有：（1）算法頂層設(shè)計與底層實現(xiàn)分離；（2）算法設(shè)計與數(shù)據(jù)結(jié)構(gòu)設(shè)計隔開，允許數(shù)據(jù)結(jié)構(gòu)自由選擇；（3）數(shù)據(jù)模型和該模型上的運算統(tǒng)一在ADT中，便于空間和時間耗費的折衷；（4）用
4、抽象數(shù)據(jù)類型表述的算法具有很好的可維護性；（5）算法自然呈現(xiàn)模塊化；（6）為自頂向下逐步求精和模塊化提供有效途徑和工具；（7）算法結(jié)構(gòu)清晰，層次分明，便于算法正確性的證明和復(fù)雜性的分析。7在本書中，采用Java語言描述算法。1.Java程序結(jié)構(gòu)1.3描述算法以下，對Java語言的若干重要特性作簡要概述。（1）Java程序的兩種類型：應(yīng)用程序和applet區(qū)別：應(yīng)用程序的主方法為main，其可在命令行中用命令語句java應(yīng)用程序名來執(zhí)行；applet的主方法為init，其必須嵌入HTML文件，由Web瀏覽器
5、或applet閱讀器來執(zhí)行。（2）包：java程序和類可以包(packages)的形式組織管理。（3）import語句：在java程序中可用import語句加載所需的包。例如，importjava.io.*;語句加載java.io包。81.3描述算法2.Java數(shù)據(jù)類型數(shù)據(jù)類型基本數(shù)據(jù)類型：詳見下頁表1-1非基本數(shù)據(jù)類型：如Byte,Integer,Boolean,String等。Java對兩種數(shù)據(jù)類型的不同處理方式：對基本數(shù)據(jù)類型：在聲明一個具有基本數(shù)據(jù)類型的變量時，自動建立該數(shù)據(jù)類型的對象（或稱實例）
6、。如:intk;對非基本數(shù)據(jù)類型：語句Strings;并不建立具有數(shù)據(jù)類型String的對象，而是建立一個類型String的引用對象，數(shù)據(jù)類型為String的對象可用下面的new語句建立。s=newString(“Welcome”);Strings=newString(“Welcome”);91.3描述算法表格1-1Java基本數(shù)據(jù)類型類型缺省值分配空間（bits）取值范圍booleanfalse1[true,false]byte08[-128,127]charu000016[u0000,uFFFF
7、]double0.064±4.9*10-324~±1.8*10308float0.032±1.4*10-45~±3.4*1038int032[-2147483648,2147483647]long064±9.2*1017short016[-32768,32767]101.3描述算法3.方法在Java中，執(zhí)行特定任務(wù)的函數(shù)或過程統(tǒng)稱為方法(methods)。例如，java的Math類給出的常見數(shù)學(xué)計算的方法如下表所示：方法功能方法功能abs(x)x的絕對值max(x,y)x和y中較大者ceil(x)不小于x
8、的最小整數(shù)min(x,y)x和y中較小者cos(x)x的余弦pow(x,y)xyexp(x)exsin(x)x的正弦floor(x)不大于x的最大整數(shù)sqrt(x)x的平方根log(x)x的自然對數(shù)tan(x)x的正切111.3描述算法3.方法計算表達式值的自定義方法ab描述如下：publicstaticintab(inta,intb){return(a+b+Math.abs(a-b))/2;}（1）方法參數(shù)：Java中所有方
