程序和程序設(shè)計(jì)算法結(jié)構(gòu)化程序設(shè)計(jì)方法

第一章程序設(shè)計(jì)基本概念教學(xué)目標(biāo)掌握程序及程序設(shè)計(jì)的基本概念，程序的運(yùn)行過程、算法及其特點(diǎn)、算法的描述、C語言程序的基本結(jié)構(gòu)。熟悉設(shè)計(jì)程序時(shí)應(yīng)遵循的基本原則。了解利用計(jì)算機(jī)解決實(shí)際問題的過程、結(jié)構(gòu)化程序設(shè)計(jì)方法并在以后的程序設(shè)計(jì)中應(yīng)用并逐步熟練掌握。能將日常生活中解決一些簡單問題的步驟用算法描述。熟悉程序開發(fā)環(huán)境，學(xué)習(xí)上機(jī)基本操作。1.1程序與程序設(shè)計(jì)程序與程序設(shè)計(jì)程序是控制計(jì)算機(jī)運(yùn)行的指令序列。程序設(shè)計(jì)就是設(shè)計(jì)、書寫及檢查程序的過程。程序設(shè)計(jì)語言程序設(shè)計(jì)語言是軟件系統(tǒng)的重要組成部分

程序設(shè)計(jì)語言是描述計(jì)算機(jī)指令的工具。各種程序設(shè)計(jì)語言有自己的語法、詞匯。

可分為機(jī)器語言、匯編語言和高級(jí)語言三類。1.機(jī)器語言由“0”和“1”組成的二進(jìn)制表示的機(jī)器指令的集合。例如某種類型的計(jì)算機(jī)規(guī)定以“10000000”表示一個(gè)“加法”操作，以“10010000”表示一個(gè)“減法”操作。

機(jī)器指令一般由操作碼和操作數(shù)兩個(gè)部分組成。

計(jì)算機(jī)硬件可以直接識(shí)別，因此，它的執(zhí)行速度比較快。

針對(duì)一種計(jì)算機(jī)所編寫的機(jī)器語言程序，一般不能在另一種類型的計(jì)算機(jī)上運(yùn)行，而且程序的編寫難度較大，修改、調(diào)試也不方便，容易出錯(cuò)，程序的直觀性較差。

2.匯編語言用能夠幫助記憶的指令助記符來代替機(jī)器指令中的操作碼，用地址符號(hào)或十進(jìn)制數(shù)來代替操作數(shù)。如用“ADD”表示加法操作，用“SUB”表示減法操作。

比機(jī)器語言直觀，容易記憶和理解，編寫的程序比機(jī)器語言程序易讀、易檢查、易修改

不同類型的計(jì)算機(jī)，匯編語言源程序不能通用。

必須由一種專門的翻譯程序（匯編程序）將匯編語言源程序翻譯成機(jī)器語言程序，計(jì)算機(jī)才能執(zhí)行。

3.高級(jí)語言面向問題的程序設(shè)計(jì)語言

與具體的計(jì)算機(jī)硬件無關(guān)，其表達(dá)方式接近于被描述的問題，接近于自然語言和數(shù)學(xué)語言，易為人們接受和掌握。

其顯著特點(diǎn)是獨(dú)立于具體的計(jì)算機(jī)硬件，通用性和可移植性好。

計(jì)算機(jī)高級(jí)語言已有上百種之多，得到廣泛應(yīng)用的也有十幾種，并且?guī)缀趺恳环N高級(jí)語言都有其適用的領(lǐng)域。C語言是其中之一。肯尼思·湯普森和

丹尼斯·里奇

在計(jì)算機(jī)發(fā)展的歷史上，大概沒有哪個(gè)程序設(shè)計(jì)語言像C那樣得到如此廣泛地流行；也沒有哪個(gè)操作系統(tǒng)像UNIX那樣獲得計(jì)算機(jī)廠家和用戶的普遍青睞和厚愛。它們對(duì)整個(gè)軟件技術(shù)和軟件產(chǎn)業(yè)都產(chǎn)生了深遠(yuǎn)的影響。而C和UNIX兩者都是貝爾實(shí)驗(yàn)室的DennisRitchie和KennethThompson設(shè)計(jì)、開發(fā)的。他們兩人共同獲得1983年度的圖靈獎(jiǎng)。UNIX成功的一個(gè)重要因素是它的可移植性。正是里奇竭盡全力開發(fā)了C語言，并把UNIX用C重寫了一遍，這才使它具有了這一特性。里奇還和克尼漢(B．W．Kernighan)合著了一本介紹C的專著：《C程序設(shè)計(jì)語言》(TheCProgrammingLanguage，Prentice-Hall，1978，1988)。4.程序運(yùn)行過程編輯處理

通過編輯程序?qū)⒕帉懙脑闯绦蛩腿胗?jì)算機(jī)。語言處理

將用戶編寫的源程序轉(zhuǎn)換成機(jī)器語言的形式，以便計(jì)算機(jī)能夠識(shí)別和運(yùn)行。由翻譯程序自動(dòng)完成的，翻譯程序除了要完成語言間的轉(zhuǎn)換外，還要進(jìn)行語法、語義等方面的檢查。裝配鏈接處理

裝入內(nèi)存運(yùn)行5.語言處理語言處理程序一般可分為：匯編程序編譯程序解釋程序這三種類型5.語言處理匯編由匯編程序（一種由專業(yè)的軟件開發(fā)商提供的系統(tǒng)軟件）將用匯編語言編寫的源程序翻譯成目標(biāo)程序（某種類型計(jì)算機(jī)的機(jī)器語言程序），這一過程稱為匯編。編譯由編譯程序?qū)⒏呒?jí)語言源程序翻譯成目標(biāo)程序。語言處理(續(xù))解釋由解釋程序?qū)⒏呒?jí)語言源程序一句一句地讀入，每讀入一個(gè)語句都要對(duì)它進(jìn)行分析和解釋，若有錯(cuò)誤就即時(shí)中斷其解釋過程，并通知用戶進(jìn)行修改，若沒有錯(cuò)誤就按照解釋結(jié)果執(zhí)行所要求的操作。解釋方式不產(chǎn)生目標(biāo)程序。

6.程序設(shè)計(jì)基本原則正確性

程序本身必須具備且只能具備程序設(shè)計(jì)規(guī)格說明書中所列舉的全部功能。它是判斷程序質(zhì)量的首要標(biāo)準(zhǔn)。

可靠性

程序在多次反復(fù)使用過程中不失敗的概率。簡明性

簡明性的目標(biāo)是要求程序簡明易讀。

有效性

程序在計(jì)算機(jī)上運(yùn)行需要使用一定數(shù)量的計(jì)算機(jī)資源，如CPU的時(shí)間、存儲(chǔ)器的存儲(chǔ)空間。有效性就是要在一定的軟、硬件條件下，反映出程序的綜合效率?？删S護(hù)性

程序的可維護(hù)可分為校正性維護(hù)、適應(yīng)性維護(hù)和完善性維護(hù)。一個(gè)軟件的可維護(hù)性如何直接關(guān)系到程序的可用性，因此應(yīng)特別予以關(guān)注?？梢浦残?/p>

程序主要與其所完成的任務(wù)有關(guān)，但也與它的運(yùn)行環(huán)境有著一定的聯(lián)系。軟件的開發(fā)應(yīng)盡可能遠(yuǎn)離機(jī)器的特征，以提高它的可移植程度。7.用計(jì)算機(jī)解決問題的基本步驟一般由分析問題、建立數(shù)學(xué)模型、選擇合適算法、編寫程序、調(diào)試、運(yùn)行程序直至得到正確的結(jié)果等幾個(gè)階段所組成。

設(shè)計(jì)步驟

確定要解決的問題。主要目的是搞清楚“做什么”。算法設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。主要任務(wù)是解決“如何做”。涉及兩個(gè)方面的內(nèi)容，一是數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)（解決數(shù)據(jù)的表示與存儲(chǔ)），另一個(gè)是算法設(shè)計(jì)（描述操作步驟）。編寫程序和調(diào)試程序。整理資料，交付使用。1.2算法計(jì)算機(jī)算法是為計(jì)算機(jī)解題設(shè)計(jì)的有明確意義的運(yùn)算步驟的有限集合。算法可以用不同的方法表示。常用的有自然語言、傳統(tǒng)流程圖、結(jié)構(gòu)化流程圖、偽代碼等。算法的特點(diǎn)有窮性確定性有效性有零個(gè)或多個(gè)輸入有一個(gè)或多個(gè)輸出1．簡單算法舉例例1.1

給出求x1+x2+x3+x4+x5的值的算法。

算法分析：（1）手工計(jì)算步驟為：①求x1與x2的和，得到兩個(gè)數(shù)之和；②將上一步的和與x3相加，得到三個(gè)數(shù)之和；③將上一步的和與x4相加，得到四個(gè)數(shù)之和；④將上一步的和與x5相加，得到五個(gè)數(shù)之和。從手工計(jì)算過程中可知：其運(yùn)算方法類似于用算盤計(jì)算該題的過程，每次僅求出兩個(gè)數(shù)之和，其中一個(gè)加數(shù)為上一步所得的結(jié)果，另一加數(shù)為多項(xiàng)式中的一項(xiàng)，重復(fù)這個(gè)過程，直到加到最后一項(xiàng)為此。

該算法能更加簡潔地表達(dá)上述解題過程，并具有通用性。先定義幾個(gè)變量：設(shè)置變量s表示多項(xiàng)式之和，其初值為零；設(shè)置變量a表示多項(xiàng)式中的一項(xiàng)，它的值可以為x1，x2，

，x5；用i記錄被加了幾次，其初值為1。解題步驟為：①s

0；②i

1；③a

xi；（使a等于多項(xiàng)式中的第i項(xiàng)）④s

s+a；（求和，并將結(jié)果保留在s中）⑤i

i+1；（計(jì)數(shù)增值）⑥若i≤5，則重復(fù)③、④、⑤各步；否則，計(jì)算結(jié)束；⑦輸出s。（2）適合計(jì)算機(jī)處理的算法。2.算法描述用自然語言表示通俗易懂、直觀、容易掌握，但算法的表達(dá)與計(jì)算機(jī)的高級(jí)語言形式差距較大，通常用在較簡單的問題中。

用偽代碼表示

不在計(jì)算機(jī)上實(shí)際執(zhí)行，僅僅用于程序員使用C等程序設(shè)計(jì)語言編寫程序之前幫助其構(gòu)思，而且與自然語言相似，非常方便和友好。

用傳統(tǒng)流程圖表示

直觀，設(shè)計(jì)者的思路表達(dá)得清楚易懂，便于檢查修改。

傳統(tǒng)流程圖常用的符號(hào)例1.2輸入一個(gè)整數(shù)，將它倒過來輸出用自然語言描述：①輸入一個(gè)整數(shù)送給x；②求x除以10的余數(shù)，結(jié)果送給d，并輸出d；③求x除以10的整數(shù)商，結(jié)果送給x；④

重復(fù)②，③步，直到x變?yōu)榱銜r(shí)終止。用偽代碼描述：①輸入一個(gè)整數(shù)送x；②while（x≠0）do{d=x%10；輸出d；

x=x/10；

}定義變量X輸入一個(gè)數(shù)給Xx≠0?d=x%10;輸出d;x=x/10;程序結(jié)束否是例1.3求出這100個(gè)數(shù)的累加和、最大值和最小值

從鍵盤輸入100個(gè)數(shù)，求出這100個(gè)數(shù)的累加和，并找出它們的最大值和最小值。試用傳統(tǒng)流程圖描述解決這個(gè)問題的算法。ABCABC1.3結(jié)構(gòu)化程序設(shè)計(jì)方法設(shè)計(jì)程序時(shí)只能使用順序、選擇、循環(huán)三種基本結(jié)構(gòu)。

結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào)程序設(shè)計(jì)風(fēng)格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu)。

結(jié)構(gòu)化程序設(shè)計(jì)方法的基本思路是，把一個(gè)復(fù)雜問題的求解過程分階段進(jìn)行，每個(gè)階段處理的問題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。

(1)自頂向下；(2)逐步細(xì)化；

(3)模塊化設(shè)計(jì)；(4)結(jié)構(gòu)化編碼。

1.三種基本結(jié)構(gòu)(1)只有一個(gè)入口。(2)只有一個(gè)出口。(3)結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到。(4)結(jié)構(gòu)內(nèi)不存在“死循環(huán)”(無終止的循環(huán))。處理1處理2(a)順序結(jié)構(gòu)條件處理(c)循環(huán)結(jié)構(gòu)滿足不滿足條件處理1處理2(b)選擇結(jié)構(gòu)滿足不滿足2.NS流程圖N-S流程圖由美國學(xué)者I.Nassi和B.Shneiderman提出的一種新的流程圖形式。在這種流程圖中，完全去掉了帶箭頭的流程線，禁用程序的轉(zhuǎn)向語句，將全部算法都寫在一個(gè)矩形框內(nèi)，因此，N-S流程圖也叫盒圖。

處理1處理2(a)順序結(jié)構(gòu)條件處理1處理2成立不成立(b)選擇結(jié)構(gòu)當(dāng)條件成立時(shí)處理直到條件成立為止處理(c)循環(huán)結(jié)構(gòu)例1.4

從鍵盤輸入一個(gè)整數(shù)，判別該數(shù)是否為素?cái)?shù)

素?cái)?shù)，也稱為質(zhì)數(shù)，是指只能被1