算法的概念課件

算法的概念算法是指解決給定問題的有窮操作步驟的描述。算法是計算機科學中的重要概念之一，它指明了問題的求解過程，是對給定問題解題方案的準確而完整地描述。2020年10月2日1【例4.1】給定任意兩個整數(shù)，按從小到大順序排列。解決這一問題的算法可描述如下：⑴輸入兩個整數(shù)A和B；⑵比較A和B的大小，若A<B，則分別輸出A和B，且計算到此結(jié)束，否則(A≥B)，分別輸出B和A，且計算到此結(jié)束。2020年10月2日2算法的基本特征⑴有窮性。一個算法應包括有限的操作步驟，能在執(zhí)行有窮的操作步驟之后結(jié)束。⑵確定性。算法的計算規(guī)則及相應的計算步驟必須是唯一確定的，既不能含糊其詞，也不能有二義性。⑶可行性。算法中的每一個步驟都是可以在有限的時間內(nèi)完成的基本操作，并能得到確定的結(jié)果。2020年10月2日3⑷數(shù)據(jù)輸入。每個算法都要求有原始數(shù)據(jù)輸入，即給定計算初值。算法不同，輸入的原始數(shù)據(jù)可能不同，但缺少原始數(shù)據(jù)的算法則是一個不完善的算法。⑸信息輸出。一個算法至少要有一個有效的信息輸出，這就是問題求解的結(jié)果。2020年10月2日4衡量一個算法好壞的標準是：算法應當正確，易于閱讀和理解，實現(xiàn)算法所占存儲空間要少，運算時間短，實現(xiàn)方法簡單可行等。2020年10月2日5算法的表示方法⒈用文字敘述形式表示可以用中文或英文敘述的形式來描述算法采用文字敘述形式表示算法通俗易懂，但文字冗長，而且容易產(chǎn)生“歧義”（即對同一段文字，不同的人可能會有不同的理解）。因此，除了一些非常簡單的問題外，一般不采用文字敘述形式來表示算法。2020年10月2日6⒉用流程圖表示流程圖一般可分為傳統(tǒng)流程圖和結(jié)構(gòu)化流程圖（Ｎ－Ｓ圖)。所謂傳統(tǒng)的流程圖是指用幾何框、箭頭、連線以及文字說明相結(jié)合的一種圖形。用流程圖表示算法不僅直觀、靈活，而且易于理解。2020年10月2日7起始或終止框計算處理框（過程）條件判斷框（決策）輸入輸出框（數(shù)據(jù)）流向或路徑連接點2020年10月2日8開始輸入兩個整數(shù)A和BA<B輸出A和B值輸出B和A值成立不成立2020年10月2日9結(jié)束2020年10月2日103.用偽代碼表示所謂偽代碼表示是指用介于自然語言和計算機語言之間的一種代碼來描述算法。用偽代碼表示例4.1的算法。

INPUTA,BIFA<BPRINTA,BELSEPRINTB,AENDIF2020年10月2日11利用計算機處理問題的過程用計算機所能接受的形式把解題的算法用程序設計語言描述出來的工作叫程序設計，它包括了大量的工作和許多具體的步驟。其中這些步驟包括以下內(nèi)容：⑴分析問題。即明確實際問題的要求，給定的數(shù)據(jù)有哪些，需要輸出什么樣的數(shù)據(jù)，需要進行哪種處理。⑵確定求解方案。2020年10月2日12⑶算法分析。根據(jù)處理方案，具體列出讓計算機如何進行操作的步驟（算法），并進行算法的準確性和有效性分析，找出合理的算法。⑷編寫程序。擬定算法的步驟和說明后，使用某種程序設計語言，以書面形式將算法描述出來，所得到的編程結(jié)果就是源程序。⑸上機調(diào)試運行程序。將編寫好的源程序輸入計算機并調(diào)試、運行，如果程序是正確的，應能得到預期的結(jié)果，如果得2020年10月2日13不到正確結(jié)果，應該檢查前幾步是否有誤，改正后再上機運行。⑹編寫文檔。編寫文檔是程序設計的必要組成部分。從問題的提出開始一直到程序運行結(jié)束，都應該全面、完整地編寫文檔資料，內(nèi)容包括技術文檔資料和使用文檔資料，這是后期使用和維護程序所必需的資料。⑺維護。程序所處理的各種數(shù)據(jù)是非常寶貴的信息資源，其寶貴價值就在于信息的真實性、準確性和有效性。要保證信息的真實性和準確性，就需要及時地進行增、刪和更新等維護工作。2020年10月2日144.3結(jié)構(gòu)化程序設計概述4.3.1結(jié)構(gòu)化程序的三種基本結(jié)構(gòu)結(jié)構(gòu)化程序規(guī)定了三種基本的結(jié)構(gòu)，即順序結(jié)構(gòu)、分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。⒈順序結(jié)構(gòu)順序結(jié)構(gòu)是一種最簡單、最基本的結(jié)構(gòu)，其特點是各部分按照出現(xiàn)的先后順序執(zhí)行。它由A和B兩個語句塊組成，且僅有一個入口（ａ）和一個出口（ｂ）。最簡單的情況是每一語句塊中只含有一條不產(chǎn)生控制轉(zhuǎn)移的執(zhí)行語句。2020年10月2日15每個語句塊本身也可以是一個順序結(jié)構(gòu)，因此一個順序結(jié)構(gòu)可以由許多順序執(zhí)行的語句組成。ABab2020年10月2日16⒉分支結(jié)構(gòu)它根據(jù)給定的條件在兩條可供選擇的分支中選擇其中的一條執(zhí)行。當條件成立時，執(zhí)行語句塊A，否則執(zhí)行語句塊B。執(zhí)行完語句塊A或語句塊B后，都從ｂ點出口。因此就整個分支結(jié)構(gòu)來講，它仍然只有一個入口（ａ）和一個出口（ｂ）。2020年10月2日17條件ABab成立不成立2020年10月2日18⒊循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)也叫重復結(jié)構(gòu)，即重復執(zhí)行某些操作。根據(jù)其執(zhí)行情況和循環(huán)結(jié)束條件的不同可分為當型循環(huán)（也稱WHILE型結(jié)構(gòu)）和直到型循環(huán)（也稱UNTIL型結(jié)構(gòu)）。當型循環(huán)結(jié)構(gòu)，它是當滿足某個指定的條件時，反復執(zhí)行語句塊A，否則不執(zhí)行。直到型循環(huán)結(jié)構(gòu)，它是反復執(zhí)行語句塊A，直到條件滿足為止。它們也只有一個入口（ａ）和一個出口（ｂ）。2020年10月2日19條件A條件Aab成立不成立成立b不成立a當型直到型2020年10月2日20兩種循環(huán)結(jié)構(gòu)的區(qū)別：⑴執(zhí)行情況不一樣。當型結(jié)構(gòu)是先判斷循環(huán)條件，當條件成立時，才執(zhí)行語句塊A，若循環(huán)條件一開始就不成立，則語句塊A一次也不執(zhí)行。而直到型結(jié)構(gòu)是先執(zhí)行語句塊A，后判斷循環(huán)條件，且語句塊A至少要執(zhí)行一次。⑵循環(huán)結(jié)束條件不一樣。當型結(jié)構(gòu)是條件不成立時結(jié)束循環(huán)，而直到型結(jié)構(gòu)是條件成立時結(jié)束循環(huán)。2020年10月2日21由三種基本結(jié)構(gòu)（可以是其中的一種、二種或三種）構(gòu)成的程序，稱為結(jié)構(gòu)化程序。一個結(jié)構(gòu)化程序以及三種基本結(jié)構(gòu)中的每一種都應當具有以下特點：⑴程序執(zhí)行的路徑只有一個入口和一個出口，在入口和出口之間是一種基本方盒或邏輯結(jié)構(gòu)。⑵該結(jié)構(gòu)中的任一個部分都存在著從入口到出口的路徑，換句話說，結(jié)構(gòu)中每一部分都可以被執(zhí)行，不存在執(zhí)行不到的死塊（程序段）。⑶沒有死循環(huán)（永無休止的循環(huán)）。2020年10月2日224.3.2結(jié)構(gòu)化流程圖在結(jié)構(gòu)化程序設計中，經(jīng)常采用結(jié)構(gòu)化流程圖來表示算法。結(jié)構(gòu)化流程圖是在去掉傳統(tǒng)流程圖中的流程線的基礎上形成的，由美國計算機科學家I.Nasi和B.Schneiderman1973年提出，因此又稱為Ｎ－Ｓ圖?？矗危訄D就好比是看一頁書，從上到下看下來就全明白了。2020年10月2日23⒈三種基本結(jié)構(gòu)的Ｎ－Ｓ圖符號⑴順序結(jié)構(gòu)順序結(jié)構(gòu)用矩形框表示，有時為了簡便，也可以將一個順序結(jié)構(gòu)寫在一個矩形框內(nèi)。AB2020年10月2日24⑵分支結(jié)構(gòu)分支結(jié)構(gòu)用帶三角形的框來表示，若三角形中的條件成立，則執(zhí)行語句塊A，否則執(zhí)行語句塊B。條件成立不成立AB2020年10月2日25⑶循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)用一個包含Ｌ形的矩形表示，分當型循環(huán)結(jié)構(gòu)和直到型循環(huán)。循環(huán)條件放在Ｌ形框（或倒立Ｌ形框）中，重復執(zhí)行部分放在矩形框中。當條件成立時執(zhí)行AA直到條件成立2020年10月2日26所謂結(jié)構(gòu)化程序設計方法是指采用順序、分支和循環(huán)三種基本結(jié)構(gòu)來實現(xiàn)算法。按照結(jié)構(gòu)化程序設計方法設計出的程序結(jié)構(gòu)良好，具有易讀、易維護等優(yōu)點。自頂向下、逐步求精和模塊化是結(jié)構(gòu)化程序設計方法中最典型、最具有代表性的方法。⒈自頂向下的設計方法自頂向下設計方法是一種從頂層開始，向下逐層分解、逐步細化，直到最底一層達到最簡單的功能模塊為止的方法。這種方法能夠使編程者思路清楚、2020年10月2日27有條不紊地一步一步深入地工作，用較短的時間設計出結(jié)構(gòu)良好、可讀性強、可靠性較高的程序，并容易驗證程序的正確性，便于維護。⒉逐步求精設計方法逐步求精設計方法是將一個抽象的問題分解成若干個相對獨立的小問題，并逐級進行由抽象到具體，由粗到細，由表及里不斷進行精細化的程序設計方法。每一步求精過程都將問題的算法進一步細化，直到算法精細化到可以用三種基本結(jié)構(gòu)實現(xiàn)為止。2020年10月2日28⒊模塊化設計方法模塊化設計方法是指將一個復雜的問題，分解成許多功能單一、相對獨立的模塊，各模塊之間按照層次結(jié)構(gòu)聯(lián)系起來構(gòu)成模塊結(jié)構(gòu)圖。在模塊結(jié)構(gòu)圖中，每個模塊用一個矩形框表示，框內(nèi)寫上每個模塊的名稱，模塊之間的調(diào)用關系用帶箭頭的方向線表示。模塊化設計方法的核心是如何劃分模塊，產(chǎn)生模塊結(jié)構(gòu)圖。2020年10月2日29上述三種結(jié)構(gòu)化程序設計方法各有其特點。逐步求精設計方法主要指一個程序的設計過程，它符合人們邏輯推理和思維的習慣。模塊化設計方法和自頂向下設計方法主要指一個比較大的系統(tǒng)的設計過程，采取的是化整為零，各個擊破的方法。將問題分割成若干個子問題，對子問題再進行分割，這樣可將問題分割成一個模塊層次結(jié)構(gòu)。2020年10月2日304.4Foxpro程序的建立、運行和調(diào)試4.4.1Foxpro程序的一般結(jié)構(gòu)*PROG4_6.PRG的功能是已知三角形三邊,求

三角形面積

SETTALKOFF&&執(zhí)行結(jié)果不在屏幕上顯示

A=3B=4C=5P=(A+B+C)/2S=SQRT(P*(P-A)*(P-B)*(P-C))?"三角形面積為:",SSETTALKON2020年10月2日31

PARAMETERSA,B,C&&形式參數(shù)

SETTALKOFFP=(A+B+C)/2S=SQRT(P*(P-A)*(P-B)*(P-C))?"三角形面積為:",SSETTALKON*帶參數(shù)程序2020年10月2日32*PROG4_8.PRGPARAMETERSA,B,CSETTALKOFFIFA+B<=CORA+C<=BORB+C<=A*判斷能否構(gòu)成三角形

DODISPERR&&調(diào)用過程DISPERRELSE?"三角形面積為:",SOLVEAREA(A,B,C)*調(diào)用函數(shù)SOLVEAREA計算三角形面積

ENDIF

2020年10月2日33SETTALKONRETURN

PROCEDUREDISPERR&&顯示錯誤信息

WAIT"不能構(gòu)成三角形!"WINDOW；NOWAITRETURN

FUNCTIONSOLVEAREA

*計算三角形面積自定義函數(shù)

PARAMETERSX,Y,ZP=(X+Y+Z)/2

2020年10月2日34

AREA=SQRT(P*(P-X)*(P-Y)*(P-Z))RETURNAREA2020年10月2日35通過以上幾個程序例子可以看到：⒈一個Foxpro程序是由一個主程序或者一個主程序和若干個過程或自定義函數(shù)構(gòu)成⒉主程序、過程或用戶自定義函數(shù)通常包括三個基本部分，即參數(shù)說明部分、執(zhí)行部分和結(jié)束部分。⑴參數(shù)說明部分

Foxpro規(guī)定其程序可以有兩種，即不帶參數(shù)程序和帶參數(shù)程序，兩者的主要區(qū)別在于有無參數(shù)說明部分。2020年10月2日36對于不帶參數(shù)的程序，其第一條可執(zhí)行的命令應為程序的執(zhí)行部分。對于帶參數(shù)程序，其第一條可執(zhí)行的命令必須是參數(shù)說明命令PARAMETERS。參數(shù)說明命令的格式如下：

PARAMETERS<形式參數(shù)表>該命令說明程序、過程或用戶自定義函數(shù)中所使用的全部形式參數(shù)，以便接收程序、過程或用戶自定義函數(shù)傳來的數(shù)據(jù)，它必須是“被調(diào)用程序”中的第一條可執(zhí)行命令。2020年10月2日37<形式參數(shù)表>中的參數(shù)可以是任何內(nèi)存變量名或數(shù)組名，當使用多個形參時，參數(shù)之間以逗號“，”分隔。在Foxpro中，一次最多能傳送24個參數(shù)。⑵執(zhí)行部分一個程序、過程或用戶自定義函數(shù)的執(zhí)行部分是由若干條有序的可執(zhí)行命令組成的，它完成該程序、過程或自定義函數(shù)的所有功能。通常把過程的執(zhí)行部分稱為過程體，用戶自定義函數(shù)的執(zhí)行部分稱為函數(shù)體。

2020年10月2日38⑶結(jié)束部分在Foxpro中，一個程序、過程或用戶自定義函數(shù)可以有結(jié)束部分，也可以沒有結(jié)束部分。如果有結(jié)束部分，一般都是通過執(zhí)行一條“結(jié)束程序執(zhí)行的命令”來結(jié)束該程序、過程或用戶自定義函數(shù)的執(zhí)行。Foxpro提供了以下四條結(jié)束程序執(zhí)行的命令：①返回命令──RETURN【格式】RETURN[<表達式>｜TOMASTER｜TO<程序名>]

2020年10月2日39【功能】該命令終止程序、過程或用戶自定義函數(shù)的執(zhí)行。若RETURN后不帶任何選項，則返回到調(diào)用程序中調(diào)用處的下一條命令繼續(xù)執(zhí)行，當在命令窗口下執(zhí)行程序時將返回到命令窗口。如果RETURN后帶TOMASTER，則返回到最高層調(diào)用程序。如果RETURN后加入TO<程序名>，則返回到由<程序名>所指定的程序。在用戶自定義函數(shù)的最后通常用RETURN命令將一個<表達式>的值返回給調(diào)用程序。2020年10月2日40②重試命令──RETRY【格式】RETRY【功能】返回調(diào)用程序，并再次執(zhí)行調(diào)用程序中上一次被執(zhí)行的那一行。該命令常用在錯誤處理程序中。③結(jié)束命令──CANCEL【格式】CANCEL【功能】中止程序的執(zhí)行，直接返回到Foxpro命令窗口。④退出命令──QUIT【格式】QUIT2020年10月2日41【功能】結(jié)束程序的執(zhí)行，關閉所有已打開的文件，退出Foxpro環(huán)境，返回到操作系統(tǒng)。以上四條結(jié)束命令可以放在一個程序、過程或用戶自定義函數(shù)中的任何地方，并且允許出現(xiàn)多次。Foxpro規(guī)定，如果在一個程序、過程或用戶自定義函數(shù)中沒有結(jié)束部分，則默認為RETURN，在這種情況下，當執(zhí)行完最后一條命令后，將返回到調(diào)用處的下一條命令繼續(xù)執(zhí)行。2020年10月2日42綜上所述，給出Foxpro程序的一般結(jié)構(gòu)如下：[PARAMETERS<形式參數(shù)表>]<執(zhí)行部分>[結(jié)束部分]

[PROCEDURE<過程名>[PARAMETERS<形式參數(shù)表>]<過程體>[結(jié)束部分].

2020年10月2日43][FUNCTION<函數(shù)名>[PARAMETERS<形式參數(shù)表>]<函數(shù)體>[RETURN<表達式>]...]2020年10月2日444.4.2Foxpro程序的建立與修改⒈程序文件的建立

MODIFYCOMMAND[<文件>]｜?]｜

MODIFYFILE[<文件>｜?]

modicomm主要用來編輯程序文件，

modifile主要用來編輯文本文件。2020年10月2日454.4.3Foxpro程序的運行與調(diào)試⒈程序的運行在Foxpro環(huán)境下，運行一個程序有兩種方法：一種是在Foxpro系統(tǒng)菜單下執(zhí)行Program菜單中的Do選項，另外一種方法是在命令窗口中執(zhí)行Do命令。Foxpro的Do命令的格式如下：

DO<文件1>[WITH<實際參數(shù)表>][IN<文件2>]該命令用來執(zhí)行一個Foxpro程序文件。如果沒有指定程序文件的擴展名，則按可執(zhí)行文件（.EXE）→應用程序（.APP2020年10月2日46）→編譯后的文件（.FXP）→源程序（.PRG）順序來執(zhí)行。對于帶參數(shù)程序，必須帶WITH<實際參數(shù)表>，此時WITH后的實際參數(shù)表將被傳送給該程序文件使用。帶IN<文件2>選項表示要執(zhí)行指定程序<文件2>中的一個過程。通常我們把在Foxpro命令窗口中執(zhí)行DO命令稱為“運行程序”，而在一個程序中執(zhí)行該命令稱為“調(diào)用程序”。Foxpro中的每個程序都可以被調(diào)用，所以在任何程序中都可以通過DO命令來調(diào)用其它程序。2020年10月2日47⒉程序的調(diào)試初次建立的程序由于種種原因可能會出現(xiàn)各種各樣的錯誤，需要通過試運行來檢查和修改程序中的錯誤，這就是常說的“程序的調(diào)試”。調(diào)試程序的常用方法是用一些典型數(shù)據(jù)來試驗運行程序，通過分析運行結(jié)果來判斷程序是否正確。若運行結(jié)果不正確，需要找出錯誤的地方并加以修改。也可以使用Foxpro提供的調(diào)試工具來幫助我們跟蹤在程序調(diào)試中出現(xiàn)的錯誤。例如，如果使用SETSTEPON命令可以設置單步執(zhí)行方式，F(xiàn)oxpro在執(zhí)行每條命令后暫停，并在2020年10月2日48

Trace窗口顯示該程序，以便查看程序的執(zhí)行情況。如果使用SETALTERNATETO<文件名>命令和SETALTERNATEON命令，可將程序運行過程中輸出到屏幕上的數(shù)據(jù)存入指定的磁盤文件（可以利用CLOSEALTERNATE命令關閉建立的文件），以便分析結(jié)果時使用。2020年10月2日49一般來說，程序中的錯誤可分為語法錯誤和邏輯錯誤兩種類型。⑴語法錯誤所謂“語法錯誤”是指程序中某條（些）命令不符合Foxpro的語法規(guī)則而引起的錯誤。例如，命令動詞拼寫錯誤，引用的變量不存在，數(shù)據(jù)類型不匹配等。有時標點符號使用錯誤也會導致語法錯誤。一旦出現(xiàn)語法錯誤，F(xiàn)oxp