1、,第1章 計(jì)算機(jī)程序設(shè)計(jì)與算法,C/C+程序設(shè)計(jì)教程,主要內(nèi)容有,l 程序設(shè)計(jì)語(yǔ)言 l 程序設(shè)計(jì)過(guò)程 l 程序設(shè)計(jì)算法 l 自然語(yǔ)言描述計(jì)算機(jī)算法 l 程序流程圖描述計(jì)算機(jī)算法 l N-S圖描述計(jì)算機(jī)算法 l 用程序設(shè)計(jì)語(yǔ)言描述計(jì)算機(jī)算法,1.1程序設(shè)計(jì),學(xué)習(xí)程序設(shè)計(jì)并不是簡(jiǎn)單地學(xué)習(xí)計(jì)算機(jī)語(yǔ)法規(guī)范或程序設(shè)計(jì)語(yǔ)言的本身，而是要學(xué)會(huì)怎么用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言解決實(shí)際問(wèn)題、提高工作效率和工作質(zhì)量。計(jì)算機(jī)技術(shù)應(yīng)用領(lǐng)域博大而廣泛，誰(shuí)也不可能完全學(xué)會(huì)計(jì)算機(jī)技術(shù)的方方面面，這是因?yàn)橛?jì)算機(jī)涉及到的領(lǐng)域太廣了，計(jì)算機(jī)技術(shù)的發(fā)展日新月異，即使學(xué)上很久我們也不可能完全學(xué)到頭，可以說(shuō)學(xué)無(wú)止境。,1.1.1程序設(shè)計(jì)語(yǔ)言,

2、（1）科學(xué)計(jì)算語(yǔ)言。用于科學(xué)計(jì)算，基礎(chǔ)是數(shù)學(xué)模型，過(guò)程描述的是數(shù)值計(jì)算，如FORTRAN語(yǔ)言； （2）系統(tǒng)開(kāi)發(fā)語(yǔ)言。用于編寫(xiě)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)管理系統(tǒng)DBMS等，如C語(yǔ)言； （3）實(shí)時(shí)處理語(yǔ)言。及時(shí)響應(yīng)環(huán)境信息，可以根據(jù)外部信號(hào)對(duì)不同的程序段進(jìn)行并發(fā)控制執(zhí)行；如匯編語(yǔ)言 （4）商用語(yǔ)言。主要用于商業(yè)處理、經(jīng)濟(jì)管理, 基礎(chǔ)為自然語(yǔ)言模型；如COBOL語(yǔ)言 （5）人工智能描述語(yǔ)言。模擬人的思維推理過(guò)程，實(shí)現(xiàn)智能化控制等； （6）模擬建模語(yǔ)言。用于模擬實(shí)現(xiàn)客觀事物的發(fā)展與變化過(guò)程，以提前預(yù)測(cè)未來(lái)發(fā)展的結(jié)果； （7）網(wǎng)絡(luò)編程語(yǔ)言，在網(wǎng)絡(luò)技術(shù)基礎(chǔ)上進(jìn)入深層次的應(yīng)用研究與開(kāi)發(fā)的語(yǔ)言, 如Dephi

3、適于網(wǎng)絡(luò)化環(huán)境的編程，而JAVA是一種新型跨平臺(tái)分布式程序設(shè)計(jì)語(yǔ)言，語(yǔ)義規(guī)范與C語(yǔ)言相同等等，不再列舉。,1.1.2 程序設(shè)計(jì)過(guò)程,1.程序?qū)崿F(xiàn)過(guò)程 程序設(shè)計(jì)是指我們使用一種計(jì)算機(jī)語(yǔ)言為實(shí)現(xiàn)解決實(shí)際問(wèn)題的算法去設(shè)計(jì)編寫(xiě)計(jì)算機(jī)程序的過(guò)程。 計(jì)算機(jī)語(yǔ)言是人與計(jì)算機(jī)進(jìn)行交流的媒介，通過(guò)語(yǔ)言編寫(xiě)的程序，計(jì)算機(jī)就會(huì)準(zhǔn)確地按程序步驟執(zhí)行操作，計(jì)算機(jī)解決實(shí)際問(wèn)題的一般過(guò)程如圖1.1所示：,2. 程序設(shè)計(jì)的過(guò)程,程序設(shè)計(jì)大致包含以下幾個(gè)步驟 (1) 分析問(wèn)題 程序設(shè)計(jì)首先要進(jìn)行對(duì)問(wèn)題的分析，明白我們要作什么，確定要使用的數(shù)學(xué)模型。 (2) 確定算法 確定算法即確定解決問(wèn)題時(shí)要執(zhí)行的一系列步驟。 (3) 算法描

4、述 算法描述就是使用計(jì)算機(jī)語(yǔ)言對(duì)算法予以描述。 (4) 確定程序設(shè)計(jì)語(yǔ)言 由于不同的計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言有不同的特點(diǎn)，根據(jù)實(shí)際情況與需要選定好程序設(shè)計(jì)語(yǔ)言后，就可以用該語(yǔ)言編程實(shí)現(xiàn)以算法。 (5) 調(diào)試和運(yùn)行程序,1.2 程序設(shè)計(jì)算法,計(jì)算機(jī)程序可以這樣表示 程序=算法+數(shù)據(jù)結(jié)構(gòu) 其中 數(shù)據(jù)結(jié)構(gòu): 對(duì)數(shù)據(jù)的描述,包括對(duì)數(shù)據(jù)類(lèi)型的描述核對(duì)數(shù)據(jù)組織形式描述定義.算法: 對(duì)操作過(guò)程的描述, 即操作步驟的描述。 如果考慮現(xiàn)代編程的工程化與多樣性，可以這樣表示： 程序=數(shù)據(jù)結(jié)構(gòu)+算法+（程序設(shè)計(jì)方法+編程工具+語(yǔ)言環(huán)境） 其中算法是關(guān)鍵，是實(shí)現(xiàn)程序設(shè)計(jì)的依據(jù)和基礎(chǔ)，算法分析作的完整，作的精細(xì)，才能有完整的

5、程序設(shè)計(jì)，才可能對(duì)程序進(jìn)行優(yōu)化，所以掌握算法至關(guān)重要。,1.3計(jì)算機(jī)算法的表示,1.3.1 自然語(yǔ)言描述 期末數(shù)學(xué)成績(jī)高于90分，英語(yǔ)成績(jī)高于95分，有很好的團(tuán)隊(duì)協(xié)作精神的同學(xué)，可以報(bào)名參加國(guó)際數(shù)學(xué)建模比賽。 （有很多種理解）,1.3計(jì)算機(jī)算法的表示,1.3.2 程序流程圖描述,順序結(jié)構(gòu) 條件判斷分支結(jié)構(gòu) 循環(huán)控制結(jié)構(gòu),圖1.4 表示復(fù)雜的算法看似亂麻,1.3計(jì)算機(jī)算法的表示,1.3.3 N-S圖描述,圖1.6 N-S圖表示三種基本結(jié)構(gòu),1.4 用程序設(shè)計(jì)語(yǔ)言描述,1.機(jī)器語(yǔ)言(Machine language) 例如，計(jì)算表達(dá)式 mn-z的值，并把結(jié)果值存到10010000號(hào)內(nèi)存單元。假設(shè)已

6、知某計(jì)算機(jī)的取數(shù)操作碼為1000，除法操作碼為1010，減法操作碼為1001，傳送操作碼為0100，另外也知m、n、z中的三個(gè)數(shù)已分別存放在11110110、10101101、01010110號(hào)內(nèi)存單元。用機(jī)器語(yǔ)言可描述編寫(xiě)如下程序： 1000 11110110 取出放在11110110內(nèi)存單元的值 1010 10101101 除法操作放在10101101內(nèi)存單元的值 1001 01010110 把結(jié)果值減去放在10101101內(nèi)存單元的值 0100 10010000 把最后結(jié)果值存到10010000號(hào)內(nèi)存單元,2.匯編語(yǔ)言(Assembler language),例如計(jì)算表達(dá)式mn-z值的程

7、序可以寫(xiě)成： LDA M DIV N SUB Z MOV Y 使用這種語(yǔ)言計(jì)算機(jī)CPU不能直接識(shí)別，必須用事先存放在存儲(chǔ)器中的“翻譯程序”，把匯編語(yǔ)言翻譯成機(jī)器語(yǔ)言,計(jì)算機(jī)指令系統(tǒng)才能識(shí)別和執(zhí)行，這個(gè)翻譯程序稱(chēng)為編譯匯編程序, 翻譯成機(jī)器語(yǔ)言描述的程序叫目標(biāo)程序。,3.高級(jí)語(yǔ)言(High-level language),不管使用機(jī)器語(yǔ)言還是使用匯編語(yǔ)言描述算法和編寫(xiě)程序，都沒(méi)有擺脫計(jì)算機(jī)指令系統(tǒng)的束縛。到了1954年，出現(xiàn)了一種與具體計(jì)算機(jī)指令系統(tǒng)無(wú)關(guān)的語(yǔ)言，即高級(jí)語(yǔ)言。它與人們習(xí)慣使用的自然語(yǔ)言與數(shù)學(xué)語(yǔ)言非常接近，例如： y=2x2-x+1 這樣一個(gè)數(shù)學(xué)式子用高級(jí)語(yǔ)言來(lái)寫(xiě)，就寫(xiě)成 y=2*x

8、*x-x+1 基本上是原樣表達(dá)，這樣描述程序算法顯然就得心應(yīng)手的多。,高級(jí)語(yǔ)言的解釋過(guò)程如圖1.10所示。,高級(jí)語(yǔ)言的編譯過(guò)程如圖1.11所示。,1.5 算法舉例,算法步驟分析： S1: 累加器變量sum 賦初值0 ，即sum=0 S2: 計(jì)數(shù)器變量i 賦初值1 ，即i=1 S3: 使累加器變量值sum加計(jì)數(shù)器變量值i, 結(jié)果仍放在sum中, 即sum=sum+i, 此時(shí)sum值為 sum=sum+i=0+1=1 S4: 使計(jì)數(shù)器變量i加1,結(jié)果仍放在i中, 即 i=i+1, 此時(shí)i值為 i=i+1=1+1=2 S5: 使累加器變量值sum加計(jì)數(shù)器變量值i,結(jié)果仍放在sum中, 即sum=su

9、m+i, 此時(shí)sum值為 sum=sum+i=1+2=3 S6: 使i加1,結(jié)果仍放在i中, 即i=i+1, 此時(shí)i值為 i=i+1=2+1=3 S7: 使sum加i,結(jié)果仍放在sum中, 可表示為sum=sum+i, 此時(shí)sum值為 sum=sum+i=3+3=6 S8: 使i加1,結(jié)果仍放在i中, 可表示為i=i+1, 此時(shí)i值為 i=i+1=3+1=4 S9: 使sum加i,結(jié)果仍放在sum中., 可表示為sum=sum+i, 此時(shí)sum值為 sum=sum+i=6+4=10 ,程序流程圖如圖1.12所示，N-S圖如圖1.13所示。,圖1.12 累加運(yùn)算程序流程圖 圖1.13 累加運(yùn)算N

10、-S圖,C語(yǔ)言程序算法如下：,main() int i=1,sum=0; /*定義變量及其數(shù)據(jù)類(lèi)型*/ while(i=100) /*循環(huán)控制結(jié)構(gòu)*/ sum+=i; i=i+1; /*循環(huán)體結(jié)束*/ printf(sum=%dn,sum); /*輸出累加結(jié)果*/ 程序算法不是唯一的，這個(gè)問(wèn)題還有其它的算法,算法1：,main() float sum=0; int i=1; loop: if (i=100) sum=sum+i ; i=i+1; goto loop; printf(n%f,sum); ,算法2：,main() float sum=0; int i=1; while (i=100

11、) sum=sum+i ; i+; printf(n%f,sum); ,算法3：,main() int i=1,sum=0; do sum=sum+i; i=i+1; while(i=100); printf(the sum is %d,sum); ,以此類(lèi)推,可以很容易表示出計(jì)算 之和的算法，當(dāng)分母大于100時(shí)程序結(jié)束，輸出計(jì)算結(jié)果。程序算法如下。,算法3的N-S圖如圖1.14所示。,圖1.14累加運(yùn)算N-S圖,本章是計(jì)算機(jī)程序設(shè)計(jì)的基礎(chǔ)，介紹了計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的應(yīng)用特點(diǎn)和發(fā)展演變，特別介紹了程序設(shè)計(jì)過(guò)程以及程序設(shè)計(jì)算法，學(xué)要重點(diǎn)理解和掌握的是計(jì)算機(jī)算法的表示方法，列舉了用自然語(yǔ)言描述結(jié)局問(wèn)題過(guò)程的特點(diǎn)與不足。作為一個(gè)程序設(shè)計(jì)人員，應(yīng)該熟悉并掌握比較常用的程序流程圖描述方法，以及N-S圖描述算法的基本技能，最終需要使用計(jì)算機(jī)語(yǔ)言，即程序設(shè)計(jì)語(yǔ)言描述并實(shí)現(xiàn)。本章通過(guò)算法舉例以訓(xùn)練引導(dǎo)讀者用計(jì)算機(jī)的思維表達(dá)解決問(wèn)題的過(guò)程，以最終實(shí)現(xiàn)算法，這就是程序設(shè)計(jì)算法的根本。,本章小結(jié),1.6 練習(xí)思