《算法及其設(shè)計(jì)基礎(chǔ)》PPT課件.ppt

第1章 算法及其設(shè)計(jì)基礎(chǔ),教學(xué)目的和要求 了解算法描述的基本要求和目的，掌握用自然語(yǔ)言方式、流程圖方式、盒圖(N-S圖)、 偽代碼方式、PAD圖方式和計(jì)算機(jī)語(yǔ)言方式來(lái)描述一個(gè)算法。 重點(diǎn)： 流程圖方式、盒圖(N-S圖)、PAD圖方式。 難點(diǎn)： 完整地用盒圖(N-S圖)來(lái)描述一個(gè)算法。,1.1 引言,程序設(shè)計(jì)方法首先強(qiáng)調(diào)的是設(shè)計(jì)，其次才是實(shí)現(xiàn)（寫(xiě)出程序代碼）。其核心是將程序設(shè)計(jì)過(guò)程分為兩部分。 第一部分集中于問(wèn)題及其解法或算法，與任何特定的計(jì)算機(jī)或計(jì)算機(jī)語(yǔ)言無(wú)關(guān)。 第二部分集中于選擇某一種程序設(shè)計(jì)語(yǔ)言，把算法表達(dá)給特定的計(jì)算機(jī)。,1.2 算法的概念,廣義地說(shuō)，為解決一個(gè)問(wèn)題而采取的方法和步驟，就稱(chēng)為“算法”。 你想查看計(jì)算機(jī)CPU，首先必須將計(jì)算機(jī)斷電，拆除連線(xiàn)，打開(kāi)機(jī)箱，然后按下夾子解除夾口，最后取出CPU進(jìn)行查看。 復(fù)制文件，首先要尋找所要復(fù)制的文件，然后選中，再進(jìn)行復(fù)制，最后移動(dòng)到需要的地方進(jìn)行粘貼。,計(jì)算機(jī)算法的分類(lèi)： 本書(shū)所講述的算法只限于計(jì)算機(jī)算法，即計(jì)算機(jī)能執(zhí)行的算法。在設(shè)計(jì)一個(gè)計(jì)算機(jī)算法時(shí)，應(yīng)當(dāng)考慮到計(jì)算機(jī)能否執(zhí)行。 計(jì)算機(jī)算法可分為兩大類(lèi)別：數(shù)值運(yùn)算算法和非數(shù)值運(yùn)算算法。 數(shù)值運(yùn)算的目的是求數(shù)值解，例如求方程的根，求一個(gè)函數(shù)的定積分等，都屬于數(shù)值運(yùn)算范圍。 非數(shù)值運(yùn)算包括的面十分廣泛，最常見(jiàn)的是用于事務(wù)管理領(lǐng)域，例如圖書(shū)檢索、人事管理等。目前，計(jì)算機(jī)在非數(shù)值運(yùn)算方面的應(yīng)用遠(yuǎn)遠(yuǎn)超過(guò)了在數(shù)值運(yùn)算方面的應(yīng)用。,1.3 算法的特性,一個(gè)算法應(yīng)該具有以下幾個(gè)特性： 有窮性 確定性 輸入 輸出 有效性,1.3 算法的特性,1）有窮性 一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無(wú)限的。 但是要注意，“有窮性”往往指“在合理的范圍之內(nèi)”。如果讓計(jì)算機(jī)執(zhí)行一個(gè)歷時(shí)幾百年才結(jié)束的算法，這雖然是有窮的，但超過(guò)了合理的限度，人們也不把它視做有效算法。究竟什么算“合理限度”，并無(wú)嚴(yán)格標(biāo)準(zhǔn)，由人們的常識(shí)和需要而定。,確定性 算法中的每一個(gè)步驟，必須是確切定義的，而不應(yīng)當(dāng)含糊不清或模棱兩可的。即算法的含義應(yīng)當(dāng)是唯一的，而不應(yīng)當(dāng)產(chǎn)生“歧義性”。 例如，某人只說(shuō)請(qǐng)您“復(fù)制文件”或查看計(jì)算機(jī)的CPU，是不確定的，因?yàn)榇巳藳](méi)有說(shuō)明復(fù)制哪一個(gè)文件或查看哪一臺(tái)計(jì)算機(jī)的CPU。,1.3 算法的特性,輸入 所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息。 例如，讓計(jì)算機(jī)來(lái)完成“將N個(gè)正數(shù)按從小到大的次序排列”時(shí)，就需要輸入N個(gè)正整數(shù)。一個(gè)算法可以有多個(gè)輸入，也可以沒(méi)有輸入。,1.3 算法的特性,輸出 算法執(zhí)行過(guò)程中往往會(huì)產(chǎn)生一些數(shù)據(jù)，它們?cè)谒惴▓?zhí)行之后被保存下來(lái)或傳遞給算法的調(diào)用者，這些數(shù)據(jù)被稱(chēng)為算法的輸出。 一個(gè)算法可以有多個(gè)輸出，沒(méi)有輸出的算法是沒(méi)有意義的。 例如，計(jì)算機(jī)來(lái)完成“將N個(gè)整數(shù)按從小到大的次序排列”的算法時(shí)，輸出的整數(shù)將是一組“從小到大的次序排列的N個(gè)整數(shù)”。,1.3 算法的特性,有效性 一個(gè)算法應(yīng)該是具有現(xiàn)實(shí)意義的，如果算法中含有不能實(shí)現(xiàn)的某一個(gè)步驟，則這個(gè)所謂的“算法”無(wú)法解決問(wèn)題，因此，不能稱(chēng)為算法。 算法貫穿于程序設(shè)計(jì)的始終，希望讀者對(duì)算法給予很大的重視，在解決一個(gè)問(wèn)題之前應(yīng)當(dāng)首先構(gòu)造出一個(gè)好的算法。在本書(shū)各章中都貫穿這一原則。,1.3 算法的特性,1.4 算法的結(jié)構(gòu),1966年，計(jì)算機(jī)科學(xué)家Bohm和Jacopini的研究表明，任何簡(jiǎn)單或復(fù)雜的算法都可以由下述3種基本控制結(jié)構(gòu)組成。 1）順序結(jié)構(gòu) 2) 選擇結(jié)構(gòu) 3) 循環(huán)結(jié)構(gòu),1）順序結(jié)構(gòu),這是最簡(jiǎn)單的一種基本結(jié)構(gòu)。順序結(jié)構(gòu)中的各個(gè)部分是按書(shū)寫(xiě)順序依次執(zhí)行的。例如某個(gè)算法中可能出現(xiàn)下列形式的一組操作： 操作 1 操作 2 操作 3 如果這樣一組操作的執(zhí)行順序與操作出現(xiàn)的前后順序相同，即先進(jìn)行“操作1”，然后進(jìn)行“操作2”，再后進(jìn)行“操作3”，那么這段算法的結(jié)構(gòu)就是順序結(jié)構(gòu)。,2) 選擇結(jié)構(gòu),這種結(jié)構(gòu)也稱(chēng)為分支結(jié)構(gòu)，它表示操作的處理步驟出現(xiàn)了分支，它需要根據(jù)某一特定的條件選擇其中的一個(gè)分支執(zhí)行。例如下述算法描述片段： 如果 成立 則執(zhí)行 否則執(zhí)行 和 之間構(gòu)成了一種選擇關(guān)系，兩個(gè)操作中哪一個(gè)將被執(zhí)行是通過(guò)對(duì) 的判斷來(lái)控制的。,3) 循環(huán)結(jié)構(gòu),循環(huán)結(jié)構(gòu)是指被重復(fù)執(zhí)行的一個(gè)操作集合。例如下述算法描述片段： 重復(fù)執(zhí)行 直到 不成立 這段描述指出 將被反復(fù)運(yùn)行多次，直到 不成立為止。,注意： 通過(guò)上述三種基本控制結(jié)構(gòu)可以看到，它們有一個(gè)共同的特點(diǎn)，即：只有一個(gè)入口且只有一個(gè)出口，并且操作不會(huì)出現(xiàn)死循環(huán)。,1.5 算法的描述,算法的描述具有重要意義，描述一個(gè)算法的目的在于使其他人能夠利用算法解決具體問(wèn)題。 算法的描述方式?jīng)]有統(tǒng)一規(guī)定，本書(shū)將介紹常用的自然語(yǔ)言、流程圖、N-S圖、PAD圖、偽代碼以及計(jì)算機(jī)語(yǔ)言等六種描述算法的方式。 注意： 不論是哪類(lèi)方式，對(duì)它們的基本要求都是能提供對(duì)算法的無(wú)歧義的描述，以便使我們能夠?qū)⑦@種描述很容易轉(zhuǎn)換成計(jì)算機(jī)高級(jí)語(yǔ)言（程序）。,1.5.1 自然語(yǔ)言方式,自然語(yǔ)言就是人們?nèi)粘Ｊ褂玫恼Z(yǔ)言，可以是漢語(yǔ)、英語(yǔ)或其他任何形式的語(yǔ)言。,算法可以表示如下： 第1步 使sign=1（sign代表數(shù)值的符號(hào)） 第2步 使sum1（sum代表累加和變量） 第3步 使deno=2（deno代表分母變量） 第4步 sign(-1)*sign（求級(jí)數(shù)中各項(xiàng)的符號(hào)，它的值為l或-1） 第5步 termsign*(1/deno) （term代表級(jí)數(shù)中的某一項(xiàng)） 第6步 sum=sum+term 第7步 deno=deno+l 第8步 若deno20，轉(zhuǎn)去執(zhí)行第4步以及其后的各個(gè)步驟；否則 執(zhí)行第9步 第9步 打印sum的值（即所求之總和） 第10步 算法結(jié)束,例1.1 求,例1.2 用選擇排序法，將N個(gè)正整數(shù)數(shù)列按照從小到大 的順序排列。 選擇排序法基本思想：在選擇排序方法中，第一步在N個(gè)元素中選出最小元素，將其與第一個(gè)元素交換。第二步從剩下的N-1個(gè)元素中選出最小元素，將其與第二個(gè)元素交換，如此下去，直到剩下最后兩個(gè)元素。,輸入：將N個(gè)正整數(shù)放置在數(shù)組aN中。 第1步 使i=1 第2步 若iN-1，執(zhí)行第3步；否則轉(zhuǎn)第10步 第3步 使k=i，順次執(zhí)行第4步 第4步 使j=i+1，順次執(zhí)行第5步 第5步 若jN，執(zhí)行第6步；否則轉(zhuǎn)第8步 第6步 若ajak，則置k為j，然后順次執(zhí)行第7步；否則 直接執(zhí)行第7步 第7步 使j=j+1，轉(zhuǎn)第5步 第8步 若i!=k交換ai和ak的值(置t為 ai,ai為 ak， ak為 t )，順次執(zhí)行第9步；否則直接執(zhí)行第9步 第9步 使i=i+1，轉(zhuǎn)第2步 第10步 輸出a1aN 第11步 算法結(jié)束,算法可以表示如下：,自然語(yǔ)言方式的優(yōu)缺點(diǎn)： 用自然語(yǔ)言表示通俗易懂，但文字冗長(zhǎng)，容易出現(xiàn)歧義性。 用自然語(yǔ)言描述的算法通用性差。例如，用漢語(yǔ)描述的算法只適合于懂得漢語(yǔ)的人，而用英語(yǔ)描述的算法也只能適合于懂得英語(yǔ)的人。 基于上述原因，除了很簡(jiǎn)單的問(wèn)題以外，一般不用自然語(yǔ)言描述算法。,1.5.2 流程圖方式,流程圖是20世紀(jì)40年代末出現(xiàn)的一種描述算法或程序的工具，其特點(diǎn)是用一些圖框表示各種類(lèi)型的操作，用線(xiàn)表示這些操作的執(zhí)行順序。,圖例中各結(jié)點(diǎn)的意義：,端點(diǎn)符：表示算法由此開(kāi)始或結(jié)束。 處理框：表示一般的處理功能，應(yīng)在框中對(duì)該功能進(jìn)行簡(jiǎn)單標(biāo)記和說(shuō)明。 判斷框：表示判斷操作，應(yīng)該在框中標(biāo)明判斷條件。此框具有兩個(gè)或兩個(gè)以上出口，在每個(gè)出口處標(biāo)明出口的條件。 預(yù)定義功能框：代表未詳細(xì)說(shuō)明的一個(gè)或一組操作，通常用來(lái)表示調(diào)用一個(gè)已知的算法或函數(shù)，框中標(biāo)明這個(gè)算法或函數(shù)的名字或入口地址。 連接符：表示連結(jié)點(diǎn)，框中標(biāo)有數(shù)字。當(dāng)流程圖較復(fù)雜或分布在多張紙上時(shí)，用連接符表示各圖之間的聯(lián)系，相同符號(hào)的連接符是相互連接的（如圖1.2所示）。 注釋框：注釋框不反映流程和操作，只是為了對(duì)流程圖中某些框的操作做必要的補(bǔ)充說(shuō)明，以幫助閱讀流程圖的人更好地理解流程圖的作用。,端點(diǎn)符,處理框,輸入輸出框,預(yù)定義功能框,判斷框,流程線(xiàn),連接符,圖 1.1 流程圖常用圖形符號(hào),使用流程圖表示的順序型、選擇型、當(dāng)型循環(huán)和直到型循環(huán)等四種基本控制結(jié)構(gòu)如圖1.3所示。,條件,處理2,處理1,順序結(jié)構(gòu),處理2,處理,N,當(dāng)型循環(huán),直到型循環(huán),選擇結(jié)構(gòu),處理,條件,條件,Y,Y,N,處理,圖 1.3 四種基本控制結(jié)構(gòu),N,Y,使用流程圖表示的順序型、選擇型、當(dāng)型循環(huán)和直到型循環(huán)等四種基本控制結(jié)構(gòu)：,例1.3 求,的流程圖如圖1.4所示,例1.4 將N個(gè)正整數(shù)數(shù)列按照從小到大的順序排列的算法用流程圖表示。,流程圖描述算法的不足之處?,隨意地使用箭頭控制算法的執(zhí)行流程，從而造成算法的層次結(jié)構(gòu)混亂。 降低了程序的可讀性和可維護(hù)性。 不適于自頂向下、逐步求精的程序開(kāi)發(fā)方式。,使用程序流程圖描述算法，具有簡(jiǎn)捷、直觀、使用方便的特點(diǎn)。,流程圖特點(diǎn):,1.5.3 盒圖(N-S圖)方式,出于要有一種不允許違背結(jié)構(gòu)化程序設(shè)計(jì)思想的圖形工具的考慮，1973年美國(guó)學(xué)者Nassi和Shneiderman提出了一種新的流程圖形式,稱(chēng)為盒圖（box diagram）,又稱(chēng)為N-S圖。 在這種流程圖中，完全去掉了帶箭頭的流程線(xiàn)。全部算法寫(xiě)在一個(gè)矩形框內(nèi)，在該框內(nèi)還可以包含其他的從屬于它的框。 N-S圖十分適合描述結(jié)構(gòu)化程序或算法的結(jié)構(gòu)化實(shí)現(xiàn)，能夠較好地反映算法和程序的層次結(jié)構(gòu)，可讀性好，具有自頂向下逐步求精的特征。,N-S 圖基本符號(hào)以及控制結(jié)構(gòu)的描述方法,例1.5 求,圖 1.7 N-S圖描述,的N-S圖表示。,例1.6 將N個(gè)正整數(shù)數(shù)列按照從小到大的順序排列的N-S圖描述,1.5.4 PAD圖方式,PAD圖是問(wèn)題分析圖（problem analysis diagram）的英文縮寫(xiě)，1973年由日本日立公司的二才 良彥等提出，是另一種可以用于算法和程序描述的圖形工具。 PAD圖用二維樹(shù)型結(jié)構(gòu)的圖來(lái)表示程序的控制流，即可以用于表示程序中操作的邏輯順序，也可用于表示數(shù)據(jù)結(jié)構(gòu)，是一種結(jié)構(gòu)化程序設(shè)計(jì)描述工具，適用于自頂向下、逐步求精的程序開(kāi)發(fā)方法。,PAD圖的符號(hào)及控制結(jié)構(gòu)如圖1.9和表1.1所示。,表1.1 PAD圖的圖形符號(hào),例1.7求,的PAD圖描述算法,例1.8 將N個(gè)正整數(shù)數(shù)列按照從小到大的順序排列。,圖1.11 PAD圖描述,1.5.5 偽代碼方式,偽代碼(pseudo code)就是程序設(shè)計(jì)語(yǔ)言的控制結(jié)構(gòu)和其他一些元素的速記符號(hào)。一般來(lái)說(shuō)，偽代碼的語(yǔ)法規(guī)則分為“外層語(yǔ)法”和“內(nèi)層語(yǔ)法”。 外層語(yǔ)法類(lèi)似于一般編程語(yǔ)言控制結(jié)構(gòu)的關(guān)鍵字，比較嚴(yán)格。 內(nèi)層語(yǔ)法則是靈活自由的，可以用自然語(yǔ)言，也可用程序設(shè)計(jì)語(yǔ)言，或使用自然語(yǔ)言與程序設(shè)計(jì)語(yǔ)言的混合體，以便使用于不同工程項(xiàng)目的需要。 偽代碼不用圖形符號(hào)，因此書(shū)寫(xiě)方便、格式緊湊，也比較好懂，便于轉(zhuǎn)換成計(jì)算機(jī)高級(jí)語(yǔ)言(即程序)。,1) 層次,算法的書(shū)寫(xiě)應(yīng)該具有層次，下面的一層采用縮進(jìn)方式，同層次的縮進(jìn)相同，例如： X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X,本書(shū)偽代碼構(gòu)成元素和書(shū)寫(xiě)規(guī)則如下：,2) 注釋,其形式是由()括起來(lái)的中文或英文字符串。 3) 3種控制結(jié)構(gòu) (1) 順序結(jié)構(gòu) 書(shū)寫(xiě)格式如下： ,(2) 分支結(jié)構(gòu),有以下兩種書(shū)寫(xiě)格式： 格式1： if() then else 格式2： if() then 多重選擇的格式如下： ，執(zhí)行 ，執(zhí)行 ，執(zhí)行,（3）循環(huán)結(jié)構(gòu),有以下三種書(shū)寫(xiě)格式： 格式l：do while() 格式2：while() do 格式3：for to 步長(zhǎng) ,4) 調(diào)用算法,書(shū)寫(xiě)方式如下： 調(diào)用() 5) 需要標(biāo)明算法的“BEGIN(開(kāi)始)”和“END(結(jié)束)”點(diǎn)。,例1.9 求,BEGIN sign=1（sign代表數(shù)值的符號(hào)） sum=1（sum代表累加和變量） deno=2（deno代表分母變量） while deno20 sign=(-1)*sign（求級(jí)數(shù)中各項(xiàng)的符號(hào),它的值為l或-1） term=sign*1/deno（term代表級(jí)數(shù)中的某一項(xiàng)） sum=sum+term deno=deno+1 print sum（所求之總和） END,例1.10 將N個(gè)正整數(shù)數(shù)列按照從小到大的順序排列。,BEGIN for i=1 to N-1 (每循環(huán)一次在未排序元素中找出一個(gè)最小的元素進(jìn)行排序) k=i for j=i+1 to N（查找未排序元素中的最小的元素） if( ajak) then k=j if( ik ) then t=ai; ai=ak; ak=t; END,偽代碼書(shū)寫(xiě)格式比較自由，可以隨手寫(xiě)下去，容易表達(dá)出設(shè)計(jì)者的思想。 用偽代碼寫(xiě)的算法很容易修改，例如增加一行、刪除一行或?qū)⒑竺婺骋徊糠终{(diào)到前面某一位置，都是很容易做到的。 用偽代碼很容易寫(xiě)出結(jié)構(gòu)化的算法。 用偽代碼寫(xiě)算法不如流程圖和N-S圖直觀，可能會(huì)出現(xiàn)邏輯上的錯(cuò)誤。,1.5.6 計(jì)算機(jī)語(yǔ)言方式,前幾節(jié)我們用自然語(yǔ)言方式、偽代碼方式、流程圖方式、N-S圖方式、PAD圖等5 種不同的方式描述了算法，用計(jì)算機(jī)語(yǔ)言（包括低級(jí)語(yǔ)言和高級(jí)語(yǔ)言）編寫(xiě)的程序也是算法的表示形式。 用計(jì)算機(jī)語(yǔ)言表示算法必須嚴(yán)格遵循所用語(yǔ)言的語(yǔ)法規(guī)則，這是與其它描述方式不同的。本書(shū)中將用C程序設(shè)計(jì)語(yǔ)言表示算法。,例1.11 求,main() int sign=1; float deno=2.0,sum=1.0,term; clrscr(); while(deno=20) sign=-sign; /* 求級(jí)數(shù)中各項(xiàng)的符號(hào),值為l或-1 */ term=sign/deno; /* term代表級(jí)數(shù)中的某一項(xiàng) */ sum=sum+term; deno=deno+1; printf(“sum=%fn“,sum); 程序運(yùn)行結(jié)果： sum=0.668771,#define N 10 main() int i,j,k,t; int aN; printf(“input %d number:n“,N); for(i=0;iN;i+) printf(“a%d=“,i); scanf(“%d“, ,例1.12 將N個(gè)正整數(shù)數(shù)列按照從小到大的順序排列。,程序運(yùn)行結(jié)果： input 10 number: a0=13 a1=19 a2=22 a3=55 a4=66 a5=88 a6=11 a7=77 a8=55 a9=1 1 11 13 19 22 55 55 66 77 88,我們可以直接使用某種程序設(shè)計(jì)語(yǔ)言（如C程序設(shè)計(jì)語(yǔ)言或C+程序設(shè)計(jì)語(yǔ)言）來(lái)描述算法，不過(guò)直接使用程序設(shè)計(jì)語(yǔ)言不是很容易，而且不太直觀，并常常需要借助注釋才能使人看明白。,1.6 關(guān)于計(jì)算機(jī)算法的評(píng)價(jià),關(guān)于一個(gè)計(jì)算機(jī)算法的好壞可用下面幾個(gè)指標(biāo)來(lái)衡量： 1）程序的可讀性好 2）提高收斂速度 3）節(jié)省計(jì)算時(shí)間 4）節(jié)省存儲(chǔ)空間 5）增強(qiáng)數(shù)值穩(wěn)定性,1）程序的可讀性好 在早期使用程序設(shè)計(jì)語(yǔ)言編程的時(shí)候，尤其是在使用匯編語(yǔ)言編程的時(shí)候，人們有這樣一種認(rèn)識(shí)，那就是程序只是給機(jī)器執(zhí)行的，而不是供人閱讀的。基于這一想法，人們往往采用一些編程技巧，從而造成算法難以理解，編程更加困難，程序不易閱讀，也不便于程序的測(cè)試和維護(hù)。 20世紀(jì)70年代初，人們開(kāi)始注意在編寫(xiě)程序時(shí)注意應(yīng)該使程序具有良好的風(fēng)格。這樣使得今后有人閱讀這個(gè)程序時(shí)能比較方便地沿著你的思路去理解程序的功能，從而使程序的可讀性增強(qiáng)，方便了測(cè)試與維護(hù)。,2）提高收斂速度 對(duì)于一個(gè)迭代過(guò)程來(lái)說(shuō)，理論上講需要無(wú)限多步的計(jì)算才能得到某個(gè)量的真值，實(shí)際操作中采用的方法是根據(jù)精度要求決定是否停止進(jìn)一步的計(jì)算。所以計(jì)算時(shí)間既與選定的方法有關(guān)，還與要求達(dá)到精度有關(guān)，用計(jì)算量來(lái)評(píng)估并不適宜。,3）節(jié)省計(jì)算時(shí)間 盡管現(xiàn)在計(jì)算機(jī)的運(yùn)算速度極快，但是對(duì)于一些復(fù)雜的大規(guī)模問(wèn)題求高精度數(shù)值解來(lái)說(shuō)，最后折算成所需要進(jìn)行的四則運(yùn)算次數(shù)也是相當(dāng)多的，所需要的計(jì)算時(shí)間也很多。通常我們使用機(jī)器完成一次浮點(diǎn)數(shù)的乘法或除法運(yùn)算連同一次加法或減法運(yùn)算的計(jì)算量作為評(píng)估計(jì)算量的計(jì)量單位。 現(xiàn)在由于CPU的運(yùn)算速度以及數(shù)據(jù)總線(xiàn)的位數(shù)都得到了明顯的改善，因此，這個(gè)問(wèn)題的重要性現(xiàn)在已經(jīng)大大降低了。但是，對(duì)于一些問(wèn)題而言，設(shè)計(jì)算法時(shí)應(yīng)該考慮節(jié)省計(jì)算的時(shí)間。,4）節(jié)省存儲(chǔ)空間 節(jié)省存儲(chǔ)空間有兩層含義，第一層含義是指算法簡(jiǎn)單，因而程序就短，程序本身所占用的存儲(chǔ)空間便少；另一層含義是指所需要保留的中間結(jié)果比較少，這樣就可以省下為了保留中間結(jié)果所需要的額外的存儲(chǔ)空間。 自20世紀(jì)90年代以來(lái)，計(jì)算機(jī)的機(jī)器字長(zhǎng)，數(shù)據(jù)總線(xiàn)的位數(shù)，以及存儲(chǔ)器的容量等都得到了明顯的改善。因此，這個(gè)問(wèn)題的重要性現(xiàn)在已經(jīng)大大降低了。,5） 增強(qiáng)數(shù)值穩(wěn)定性 對(duì)于某個(gè)數(shù)值算法，如果輸入數(shù)據(jù)的誤差，在計(jì)算過(guò)程中不斷擴(kuò)大而難以得到控制，則稱(chēng)該算法是數(shù)值不穩(wěn)定的，否則是數(shù)值穩(wěn)定的。 如果某算法在一定的條件下才是穩(wěn)定的，則稱(chēng)該算法是條件穩(wěn)定（相對(duì)穩(wěn)定）的；若在任何條件下，某算法是穩(wěn)定的，則稱(chēng)該算法是無(wú)條件穩(wěn)定（絕對(duì)穩(wěn)定）的。 誤差的傳播能否得到控制，是誤差分析的重要內(nèi)容，也是衡量一個(gè)算法優(yōu)劣的一個(gè)重要標(biāo)志，可以用算法的數(shù)值穩(wěn)定性表示誤差傳播的控制。,1.7 常用算法設(shè)計(jì)及其實(shí)現(xiàn),下面我們將介紹幾種典型的方法，這些方法有一定的使用價(jià)值，但更重要的是為了使初學(xué)者容易理解算法，從而逐步掌握根據(jù)算法編寫(xiě)程序的方法。,1.7.1 排序算法及其實(shí)現(xiàn),排序是將一個(gè)無(wú)序的數(shù)據(jù)序列按照某種順序（升序或降序）重新排列的過(guò)程。例如，將一批雜亂無(wú)序的學(xué)生成績(jī)按高分到低分的順序排列。,1.7 常用算法設(shè)計(jì)及其實(shí)現(xiàn),例 1.13 用冒泡排序法將N個(gè)正整數(shù)，按照從小到大的順序排序。 冒泡排序法基本思想是將相鄰兩個(gè)數(shù)比較，把大數(shù)往后移，如圖1.12所示的過(guò)程就是冒泡處理的形象過(guò)程。,6 6 6 6 6 6 6 8 8 8 4 4 4 4 4 4 4 8 7 7 7 7 7 7 7 8 2 2 2 2 2 2 2 8 5 5 5 5 5 5 5 8 第1次 第2次 第3次 第4次 第5次 結(jié)果 6 6 4 4 4 4 4 4 6 6 6 6 7 7 7 7 2 2 2 2 2 2 7 5 5 5 5 5 5 7 第1次 第2次 第3次 第4次 結(jié)果 圖1.12 冒泡排序法第一趟比較和第二趟比較的示意,值得注意的是: 如果在一趟比較中沒(méi)有數(shù)據(jù)的交換，說(shuō)明所有的數(shù)據(jù)都已經(jīng)從小到大排好了序，因此可以提前退出循環(huán)。為此，程序中設(shè)置exchange為交換標(biāo)志，在一趟比較中數(shù)據(jù)進(jìn)行了交換exchange置為1，沒(méi)有進(jìn)行數(shù)據(jù)交換exchange置為0，即可退出循環(huán)。其N(xiāo)-S圖，如圖1.13所示。,圖 1.13 N-S圖描述,#include #define N 6 main() int i,j,t,exchange; int aN+1; /* aN用于存放 */ printf(“input %d number:“,N); for(i=0;iaj+1) /* 順序不符合要求時(shí)交換位置 */ t=aj; aj=aj+1; aj+1=t; exchange=1; if (!exchange) break; /* 若所有的元素都已排好序，則退出循環(huán) */ for(i=0;iN;i+) printf(“%4d“,ai); printf(“n“); ,程序運(yùn)行結(jié)果： input 6 number: 6 8 4 7 2 5 6 8 4 7 2 5 2 4 5 6 7 8,1.7.2 查找算法及其實(shí)現(xiàn),在處理大量數(shù)據(jù)時(shí)，經(jīng)常要按某種方法找出所需的數(shù)據(jù)，這個(gè)過(guò)程稱(chēng)為查找。 例如，在學(xué)生成績(jī)中查找某位學(xué)生的成績(jī)等。查找方法很多，下面將以例1.14為例介紹常用的順序查找法。,例 1.14 編寫(xiě)一個(gè)程序，在給定的數(shù)組a中查找用戶(hù)輸入的值，并提示相應(yīng)的查找結(jié)果。 順序查找法基本思想是：從數(shù)組第一個(gè)元素開(kāi)始，順序掃描數(shù)組，依次將掃描元素和給定值x相比較，若當(dāng)前掃描元素與x相等，則查找成功；若掃描結(jié)束后，仍未找到等于x的元素，則查找失敗。,例 1.14 編寫(xiě)一個(gè)程序，在給定的數(shù)組a中查找用戶(hù)輸入的值，并提示相應(yīng)的查找結(jié)果。,#define N 10 main() int a=6,3,9,8,1,5,4,10,2,7; int i=0,x; printf(“input x=“); scanf(“%d“, ,程序運(yùn)行結(jié)果： input x=8 find 8 it position is :a3=8 input x=99 99 not been found,1.7.3 窮舉算法及其實(shí)現(xiàn),在循環(huán)算法中，窮舉法是具有代表性的基本算法，窮舉的基本思想是，對(duì)問(wèn)題的所有可能狀態(tài)一一測(cè)試，直到找到解或?qū)⑷靠赡軤顟B(tài)都測(cè)試過(guò)為止。,例 1.15 編寫(xiě)一個(gè)程序，求這樣四位數(shù)：該四位數(shù)的千位上的數(shù)字和百位上的數(shù)字都被擦掉了，知道十位上的數(shù)字是1，個(gè)位上的數(shù)字是2，又知道這個(gè)數(shù)如果減去7就能被7整除，減去8就能被8整除，減去9就能被9整除。 設(shè)這個(gè)數(shù)為n=abl2，則n=lOOO*a+lOO*b+lO+2，且有0a9，0b9。,main() int n,a,b; for(a=1;a=9;a+) for(b=0;b=9;b+) n=1000*a+100*b+10+2; if(n-7)%7=0 程序運(yùn)行結(jié)果： n=1512