第2章算法-程序的靈魂

第2章算法—程序的靈魂

主要內(nèi)容一、

算法的概念二、算法的特性三、

算法的表示方法四、結(jié)構(gòu)化程序設(shè)計(jì)方法一、算法的概念一個(gè)程序應(yīng)包括兩個(gè)方面的內(nèi)容:對(duì)數(shù)據(jù)的描述：數(shù)據(jù)結(jié)構(gòu)(datastructure)對(duì)操作的描述：算法(algorithm)著名計(jì)算機(jī)科學(xué)家沃思提出一個(gè)公式:數(shù)據(jù)結(jié)構(gòu)+算法=程序一、算法的概念

廣義地說(shuō)，為解決一個(gè)問(wèn)題而采取的方法和步驟，就稱(chēng)為“算法”。例：求方法1：1+2，+3，+4，一直加到100加99次方法2：100+(1+99)+(2+98)+…+(49+51)+50=100+49×100+50加51次一、算法的概念計(jì)算機(jī)算法可分為兩大類(lèi)別：數(shù)值運(yùn)算算法：求數(shù)值解，例如求方程的根、求函數(shù)的定積分等。非數(shù)值運(yùn)算：包括的面十分廣泛，最常見(jiàn)的是用于事務(wù)管理領(lǐng)域，例如圖書(shū)檢索、人事管理、行車(chē)調(diào)度管理等。二、算法的特性有窮性：包含有限的操作步驟確定性：算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的

有零個(gè)或多個(gè)輸入：輸入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息有一個(gè)或多個(gè)輸出：算法的目的是為了求解，“解”就是輸出有效性：算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。三、算法的表示方法常用的表示算法的方法有：自然語(yǔ)言傳統(tǒng)流程圖結(jié)構(gòu)化流程圖N-S圖偽代碼計(jì)算機(jī)語(yǔ)言Part3算法的表示優(yōu)點(diǎn)：通俗易懂缺點(diǎn)：文字冗長(zhǎng)，容易出現(xiàn)“歧義性”，有時(shí)候需要通過(guò)上下文來(lái)判斷正確含義。1、自然語(yǔ)言Part3算法的表示2、傳統(tǒng)流程圖美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI(AmericanNationalStandardInstitute)規(guī)定了一些常用的流程圖符號(hào)：起止框判斷框處理框輸入/輸出框注釋框流向線(xiàn)連接點(diǎn)Part3算法的表示2、傳統(tǒng)流程圖例

將求5!的算法用流程圖表示Part3算法的表示2、傳統(tǒng)流程圖傳統(tǒng)流程圖的流程可以是：

這種如同亂麻一樣的算法稱(chēng)為BS型算法，意為一碗面條(ABowlofSpaghetti)，亂無(wú)頭緒。缺點(diǎn)：難以閱讀、修改，使算法的可靠性和可維護(hù)性難以保證。解決辦法：必須限制箭頭的濫用，即不允許無(wú)規(guī)律地使流程隨意轉(zhuǎn)向，只能順序地進(jìn)行下去。

Part3算法的表示Bohra和Jacopini提出了以下三種基本結(jié)構(gòu)：

順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)3、結(jié)構(gòu)化流程圖Part3算法的表示順序結(jié)構(gòu)3、結(jié)構(gòu)化流程圖Part3算法的表示選擇結(jié)構(gòu)3、結(jié)構(gòu)化流程圖Part3算法的表示3、結(jié)構(gòu)化流程圖當(dāng)型(While型)循環(huán)結(jié)構(gòu)直到型(Until型)循環(huán)Part3算法的表示3、結(jié)構(gòu)化流程圖三種基本結(jié)構(gòu)的共同特點(diǎn)：(1)只有一個(gè)入口；(2)只有一個(gè)出口；（請(qǐng)注意：一個(gè)菱形判斷框有兩個(gè)出口，而一個(gè)選擇結(jié)構(gòu)只有一個(gè)出口。不要將菱形框的出口和選擇結(jié)構(gòu)的出口混淆。）(3)結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到；(4)結(jié)構(gòu)內(nèi)不存在“死循環(huán)”(無(wú)終止的循環(huán))。Part3算法的表示3、結(jié)構(gòu)化流程圖

圖中沒(méi)有一條從入口到出口的路徑通過(guò)A框。不正確的流程表示：流程內(nèi)的死循環(huán)Part3算法的表示3、結(jié)構(gòu)化流程圖多分支選擇結(jié)構(gòu)：由三種基本結(jié)構(gòu)所派生出來(lái)的，根據(jù)表達(dá)式的值決定執(zhí)行路線(xiàn)。

虛線(xiàn)框內(nèi)的結(jié)構(gòu)是一個(gè)入口一個(gè)出口。Part3算法的表示4、N-S圖

N--S流程圖用以下的流程圖符號(hào)：

(1)順序結(jié)構(gòu)(2)選擇結(jié)構(gòu)(3)循環(huán)結(jié)構(gòu)Part3算法的表示4、N-S圖例求5!算法用N--S圖表示Part3算法的表示5、偽代碼偽代碼是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法。Part3算法的表示5、偽代碼開(kāi)始

置t的初值為1

置i的初值為2

當(dāng)i<=5，執(zhí)行下面操作：使t=t×i

使i=i+1

｛循環(huán)體到此結(jié)束｝輸出t的值結(jié)束也可以寫(xiě)成以下形式：

BEGIN｛算法開(kāi)始｝

1t2iwhilei≤5{t×iti+1i}printtEND｛算法結(jié)束｝例用偽代碼表示算法：求5!。Part3算法的表示6、計(jì)算機(jī)語(yǔ)言#include<stdio.h>voidmain(){inti,t;t=1;i=2;while(i<=5){t=t*i;i=i+1;}printf(“%d\n”,t);}例求5!，用C語(yǔ)言編寫(xiě)。四、結(jié)構(gòu)化程序設(shè)計(jì)方法一個(gè)結(jié)構(gòu)化程序

就是用高級(jí)語(yǔ)言表示的結(jié)構(gòu)化算法。(用三種基本結(jié)構(gòu)組成的程序)結(jié)構(gòu)化程序設(shè)計(jì)方法的基本思路是：把一個(gè)復(fù)雜問(wèn)題的求解過(guò)程分階段進(jìn)行，每個(gè)階段處理的問(wèn)題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。四、結(jié)構(gòu)化程序設(shè)計(jì)方法采取以下方法來(lái)保證得到結(jié)構(gòu)化的程序：自頂向下；逐步細(xì)化；模塊化設(shè)計(jì)；結(jié)構(gòu)化編碼。四、結(jié)構(gòu)化程序設(shè)計(jì)方法

用這種方法逐步分解，直到可以直接將各小段表達(dá)為文字語(yǔ)句為止。這種方法就叫做“自頂