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