




已閱讀5頁(yè),還剩73頁(yè)未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第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)粘J褂玫恼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
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2023 年醫(yī)院招聘護(hù)士考試題庫(kù)及參考答案
- 江蘇省宿遷市沭陽(yáng)中學(xué)等三校2024-2025學(xué)年高三下學(xué)期4月聯(lián)考政治試題(含解析)
- 幼兒園小班數(shù)學(xué)教案《找圓形》
- 2025年中小學(xué)心理健康教育教師考試試題及答案
- 保密協(xié)議、競(jìng)業(yè)禁止協(xié)議與培訓(xùn)
- 針灸科胃痛病例分享
- 小學(xué)教育教學(xué)知識(shí)
- 2025年工程管理與咨詢(xún)能力測(cè)試卷及答案
- 2025年教育技術(shù)學(xué)期末考試試題及答案
- 2025年社會(huì)調(diào)查與統(tǒng)計(jì)分析考試試卷及解答
- 70歲以上的換領(lǐng)駕駛證三力測(cè)試題答案
- 藥品售后服務(wù)承諾書(shū)
- 露天礦防火安全知識(shí)講座
- 2024年山東煙臺(tái)財(cái)金集團(tuán)招聘筆試參考題庫(kù)含答案解析
- GB/T 43234-2023成型模斜導(dǎo)柱
- 馬工程版《中國(guó)經(jīng)濟(jì)史》各章思考題答題要點(diǎn)及詳解
- 中建公路工程10T龍門(mén)吊安拆方案
- 2023年石獅市國(guó)企招聘考試基礎(chǔ)題庫(kù)
- OBE理念下的一流專(zhuān)業(yè)和課程建設(shè)
- 游戲俱樂(lè)部群公告范本
- 國(guó)家玩具安全技術(shù)規(guī)范
評(píng)論
0/150
提交評(píng)論