第1章概述1.1計算機(jī)發(fā)展

計算機(jī)語言1.2算法及其描述方法1.31.4程序和程序設(shè)計方法本章內(nèi)容導(dǎo)讀本章主要介紹計算機(jī)發(fā)展、計算機(jī)語言、程序、算法及其描述，以及程序設(shè)計方法等。通過學(xué)習(xí)本章，讀者應(yīng)掌握以下內(nèi)容：了解計算機(jī)語言的發(fā)展；了解高級語言的概念和特點；了解程序的概念；掌握幾種常用的算法表示方法以及程序設(shè)計方法。計算機(jī)的誕生1946年世界上第一臺電子計算機(jī)（電子數(shù)字積分計算機(jī)，ENIAC）誕生。1.1計算機(jī)發(fā)展計算機(jī)的發(fā)展第一代（20世紀(jì)50年代）：主要采用真空電子管，主要用于科學(xué)計算，用機(jī)器語言編寫程序；第二代（20世紀(jì)50年代末期）：以晶體管為主要元器件，采用匯編和高級語言編寫程序；第三代（1964至1974）：采用集成電路技術(shù)，計算機(jī)軟件逐漸系統(tǒng)化，形成了操作系統(tǒng)、編譯程序和網(wǎng)絡(luò)軟件等；第四代（1974至今）：采用大規(guī)模集成電路和微處理器；未來計算機(jī)：神經(jīng)網(wǎng)絡(luò)計算機(jī)、生物計算機(jī)、量子計算機(jī)等。馮?諾依曼體系結(jié)構(gòu)

ENIAC誕生的同時，馮?諾依曼提出存儲程序的概念，預(yù)先將計算機(jī)指令序列輸入到計算機(jī)存儲，以自動執(zhí)行一個計算任務(wù)。馮?諾依曼體系結(jié)構(gòu)確定了現(xiàn)代計算機(jī)的體系結(jié)構(gòu)，至今沒有改變。特點指令和數(shù)據(jù)采用二進(jìn)制表示，簡化機(jī)器的邏輯線路；指令和數(shù)據(jù)存儲在存儲器中；計算機(jī)由運算部件、控制部件、存儲器、輸入設(shè)備和輸出設(shè)備五大部分組成。1.1計算機(jī)發(fā)展第一代

機(jī)器語言（低級語言）：面向機(jī)器、可移植性差、效率高但不方便編程。第二代

匯編語言：利用助記符代替二進(jìn)制代碼。第三代

高級語言：面向程序員、可移植性好、執(zhí)行效率高、便于編程。第四代

面向?qū)ο笳Z言第五代

智能語言1.2計算機(jī)語言1、機(jī)器語言計算機(jī)發(fā)展早期使用的語言由“0”和“1”的字符串組成；計算機(jī)中唯一不經(jīng)過翻譯而能直接識別的語言，與具體機(jī)器有關(guān)，不同的機(jī)器識別的機(jī)器語言也不同。1.2計算機(jī)語言2、匯編語言20世紀(jì)50年代早期，數(shù)學(xué)家GraceHopper發(fā)明了符號語言（又稱為匯編語言），即用符號或助記符表示不同的機(jī)器語言指令。機(jī)器語言和具體的機(jī)器有關(guān)，要求程序員不僅要非常熟悉硬件的組成及其指令系統(tǒng)，而且必須熟記計算機(jī)的指令代碼。程序代碼量龐大，且易出錯，不易修改。1.2計算機(jī)語言3、高級語言程序員不必了解機(jī)器的指令系統(tǒng)，編程效率大大提高。高級語言與具體機(jī)器無關(guān)，所以在一種機(jī)器上運行的高級語言程序可以不經(jīng)改動地移植到另一種機(jī)器上運行，提高程序的通用性。與自然語言（尤其是英語）相似，但比自然語言嚴(yán)謹(jǐn)且富有邏輯性，因此高級語言易學(xué)、易懂。

1.2計算機(jī)語言C語言：系統(tǒng)軟件和應(yīng)用軟件BASIC：初學(xué)者入門FORTRAN或PL/I：科學(xué)計算COBOL：商業(yè)和管理等數(shù)據(jù)處理領(lǐng)域PASCAL：教學(xué)，第一個結(jié)構(gòu)化語言4、C語言與其他高級語言1.2計算機(jī)語言算法

解決問題的步驟序列即為算法。算法必須具備的五個基本特性可執(zhí)行性

算法的每一步都是可執(zhí)行的。確定性算法的每一步驟必須明確定義，不能有任何歧義性（非確定性）。有窮性一個算法必須在執(zhí)行有窮步驟之后結(jié)束。有輸入信息的說明有的算法可以沒有輸入信息，然而絕大多數(shù)算法都具有輸入信息。有輸出信息的步驟一個算法應(yīng)至少有一個輸出問題答案的步驟。1.3算法及其描述方法【例1-1】計算1×2×…×9×10的積。第一種算法（最簡單的方法）步驟1：先求1×2，得到結(jié)果2；步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6；步驟3：將6再乘以4，得到結(jié)果24；步驟4：將24再乘以5，得到結(jié)果120?！襟E9：將362880乘以10，得到結(jié)果3628800，即最后結(jié)果。1.3算法及其描述方法【例1-1】計算1×2×…×9×10的積。第二種算法分析：可以設(shè)置被乘數(shù)和乘數(shù)兩個變量，不另設(shè)變量存放乘積，直接將每一步驟的乘積放在被乘數(shù)的變量中。若設(shè)p為被乘數(shù)，i為乘數(shù)。采用循環(huán)算法計算結(jié)果，即：

S1：使p=1；S2：使i=2；S3：使p×i，乘積仍放在變量p中，可表示為p×i=>p；S4：使i的值加1，即i+1=>i；S5：如果i不大于10，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否則算法結(jié)束。最后得到p的值就是10！的值。1.3算法及其描述方法算法描述方法自然語言

通俗易懂，但文字冗長、易產(chǎn)生歧義。傳統(tǒng)流程圖

直觀形象，但占用篇幅較大，畫流程圖既費時又不方便。N-S流程圖比自然語言描述直觀、形象、易于理解；比傳統(tǒng)流程圖緊湊易畫，尤其是廢除了流程線，整個算法由各個基本結(jié)構(gòu)按順序組成。偽代碼用介于自然語言和計算機(jī)語言之間的文字和符號描述算法。書寫方便，格式緊湊，容易理解，便于向計算機(jī)語言（即程序）過渡。計算機(jī)語言只有用計算機(jī)語言編寫的程序才能被計算機(jī)執(zhí)行。必須嚴(yán)格遵循所用編程語言的語法規(guī)則，不同于偽代碼。1.3算法及其描述方法【例1-1】算法的偽代碼

1=>t

2=>i

t×i=>t

i+1=>i

直到i>10

打印t開始

置t的初值為1

置i的初值為2

當(dāng)i<=10時，執(zhí)行如下操作：

使t=t×i

使i=i+1打印t的值結(jié)束開始1=>t2=>ii+1=>it×i=>ti>10結(jié)束YN【例1-1】算法的N-S流程圖【例1-1】算法的傳統(tǒng)流程圖一個程序包括對數(shù)據(jù)的描述和對處理問題的方法和步驟的完整而準(zhǔn)確的描述。對數(shù)據(jù)的描述，即數(shù)據(jù)結(jié)構(gòu)。C語言中，系統(tǒng)提供的數(shù)據(jù)結(jié)構(gòu)，以數(shù)據(jù)類型的形式出現(xiàn)。對處理問題的方法和步驟的描述，即計算機(jī)算法，是程序的靈魂。著名計算機(jī)科學(xué)家NikiklausWirth提出：

數(shù)據(jù)結(jié)構(gòu)+算法=程序?qū)嶋H上，一個程序除了數(shù)據(jù)結(jié)構(gòu)和算法外，還必須采用結(jié)構(gòu)化程序設(shè)計方法進(jìn)行設(shè)計，并采用一種計算機(jī)語言表示。1.4程序和程序設(shè)計方法1、程序程序設(shè)計者使用各種高級語言如C、C++和Java等編寫程序，生成的程序稱為源程序。預(yù)處理階段，對源程序中以字符#開頭的預(yù)處理命令進(jìn)行處理，例如，將#include命令后面的.h文件內(nèi)容嵌入到源程序文件中。編譯階段，對預(yù)處理后的源程序進(jìn)行編譯，對源程序進(jìn)行語法檢查，如果有錯誤則給出錯誤提示，直到源程序沒有任何語法錯誤，將源程序轉(zhuǎn)換生成一個匯編語言源程序文件。匯編階段，對匯編語言源程序進(jìn)行匯編，生成一個可重定位目標(biāo)文件，在VisualStudio中以“obj”為擴(kuò)展名。鏈接階段，將多個可重定位目標(biāo)文件和標(biāo)準(zhǔn)庫函數(shù)目標(biāo)模塊合并成為一個可執(zhí)行目標(biāo)文件（ExecutableObjectFile），簡稱為可執(zhí)行文件，在VisualStudio中以“exe”為擴(kuò)展名。1.4程序和程序設(shè)計方法1、程序結(jié)構(gòu)化程序設(shè)計方法（面向過程的程序設(shè)計方法）荷蘭計算機(jī)科學(xué)家E.W.Dijkstra

于1965年提出。核心思想——模塊化將待開發(fā)的程序劃分為若干個相互獨立的模塊，每個模塊完成特定功能，適合于設(shè)計大規(guī)模的復(fù)雜程序，其基本要點包括：采用“自頂向下，逐步求精”的設(shè)計方法。程序由三種基本結(jié)構(gòu)（順序、選擇和循環(huán)）構(gòu)成。優(yōu)點：程序員易于編碼實現(xiàn)，讀者易于閱讀理解；復(fù)雜的問題化簡為一系列簡單模塊，便于系統(tǒng)擴(kuò)充。缺點：用戶的要求難以在需求分析階段被確定；開發(fā)周期較長。

2、程序設(shè)計方法1.4程序和程序設(shè)計方法面向?qū)ο蟪绦蛟O(shè)計方法1967年，挪威計算中心的KristenNygaard

和OleJohanDahl開發(fā)了Simula67語言，提供比子程序更高一級的抽象和封裝，引入數(shù)據(jù)抽象和類的概念，被認(rèn)為是第一個面向?qū)ο蟮恼Z言。核心思想將程序或者軟件看成是一個由對象組成的集合。與傳統(tǒng)