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

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

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

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

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

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

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

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

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

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

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

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

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

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

計算機(jī)高級語言已有上百種之多，得到廣泛應(yīng)用的也有十幾種，并且?guī)缀趺恳环N高級語言都有其適用的領(lǐng)域。C語言是其中之一?？夏崴肌丈?/p>

丹尼斯·里奇

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

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

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

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

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

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

可靠性

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

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

有效性

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

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

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

設(shè)計步驟

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

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

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

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

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

0；②i

1；③a

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

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

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

用偽代碼表示

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

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

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

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

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

x=x/10；

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

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

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

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

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

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

1.三種基本結(jié)構(gòu)(1)只有一個入口。(2)只有一個出口。(3)結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會被執(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)向語句，將全部算法都寫在一個矩形框內(nèi)，因此，N-S流程圖也叫盒圖。

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

從鍵盤輸入一個整數(shù)，判別該數(shù)是否為素數(shù)

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