,第二章,程序的靈魂-算法,主要內(nèi)容,2.1 算法的概念 2.2 簡單算法舉例 2.3 算法的特性 2.4 怎樣表示一個算法 2.5 程序化設(shè)計方法,一個程序應包括兩個方面的內(nèi)容:,對數(shù)據(jù)的描述：數(shù)據(jù)結(jié)構(gòu)(data structure) 對操作的描述：算法(algorithm),著名計算機科學家沃思提出一個公式: 數(shù)據(jù)結(jié)構(gòu) + 算法 = 程序,數(shù)據(jù)結(jié)構(gòu)算法程序設(shè)計方法語言工具,完整的程序設(shè)計應該是:,上述四個方面中： 算法是靈魂； 數(shù)據(jù)結(jié)構(gòu)是加工對象； 語言是工具； 編程需要采取合適的方法。 算法解決“做什么“和“怎么做“的問題。 程序中的按一定順序列出的操作語句，就是算法的體現(xiàn)。 通過本門課，大家學會使用c語言的語法編寫不太復雜的c程序。,算法的概念,用計算機解決問題的步驟，即計算機算法。,例2.1 求12345,改進算法： S1: 使t=1 S2: 使i=2 S3: 使ti,乘積仍然放在變量 t中，可表示為tit S4: 使i的值+1，即i+1i S5: 如果i5, 返回重新執(zhí)行 步驟S3以及其后的S4和S5； 否則，算法結(jié)束。,原始方法： 步驟1：先求12， 得到結(jié)果2。 步驟2：將步驟1得到的乘 積2乘以3，得到 結(jié)果6。 步驟3：將6再乘以4，得24。 步驟4：將24再乘以5，得 120。,i：第個學生學號 i：第個學生成績,S1: 1i S2: 如果gi80，則打印ni和gi，否則不打印 S3: i+1i S4: 若i50, 返回S2，否則，結(jié)束。,例2.2 有50個學生，要求將他們之中成績在80分以上者打印出來。,閏年的條件： 能被4整除，但不能被100整除的年份； 能被100整除，又能被400整除的年份；,例2. 判定2000 2500年中的每一年是否閏年，將結(jié)果輸出。,S1: 2000y S2: 若y不能被4整除，則輸出y“不是閏年”， 然 后轉(zhuǎn)到S6 S3: 若y能被4整除，不能被100整除，則輸 出y“是閏年”，然后轉(zhuǎn)到S6 S4: 若y能被100整除，又能被400整除，輸 出y“是閏年” 否則輸出y“不是閏年”， 然后轉(zhuǎn)到S6 S5: 輸出y“不是閏年”。 S6: y+1y S7: 當y2500時, 返回S2繼續(xù)執(zhí)行，否則， 結(jié)束。,C程序設(shè)計 第二章 程序的靈魂算法,例2. 求,S1: sigh=1 S2: sum=1 S3: deno=2 S4: sigh=(-1)sigh S5: term= sigh(1/deno ) S6: sum=sum+term S7: deno= deno +1 S8:若deno100，返回S4；否則，結(jié)束。,算法的特性,有窮性：一個算法應包含有限的操作步驟而不能是無限的 確定性：算法中每一個步驟應當是確定的，而不能應當是含糊的、模棱兩可的 輸入:有零個或多個輸入 輸出:有一個或多個輸出 有效性：算法中每一個步驟應當能有效地執(zhí)行，并得到確定的結(jié)果,小結(jié)：,流程圖是表示算法的較好的工具。一個流程圖包括以下幾部分 ： (1)表示相應操作的框； (2)帶箭頭的流程線； (3)框內(nèi)外必要的文字說明。,算法的表示,用自然語言表示 用流程圖表示（傳統(tǒng)流程圖和N-S圖） 用偽代碼表示 用計算機語言表示 結(jié)構(gòu)化程序的三種基本結(jié)構(gòu)： 順序、選擇、循環(huán)結(jié)構(gòu),（一）用自然語言表示算法,上節(jié)中討論的例1和例2的算法是用自然語言寫的。 自然語言指人們?nèi)粘Ｊ褂玫恼Z言，如漢語、英語等。 用自然語言表示算法的特點：通俗易懂，但不嚴謹，容易產(chǎn)生歧義。 除非問題很簡單，一般不用自然語言描述算法。,（二） 用流程圖表示算法,流程圖采用一些圖形框表示算法要表述的各種操作。 美國國家標準化協(xié)會ANSI規(guī)定了一些常用的流程圖符號： 起止框 處理框 輸入輸出框 流程線 或 判斷框 連接點 注釋,開始,結(jié)束,例1的算法用流程圖來表示,計算1 x 3x5x.x11的值 步驟1：令p=1 步驟2：令i=1 步驟3：使p x i,并將乘積放入p中。通常表示為 p x i = p 步驟4：使 i 的值加2，表示為 i+ 2 = i 步驟5：如果i 不大于11，返回到步驟3繼續(xù)向下執(zhí)行；否則算法結(jié)束。p中的值即最后結(jié)果。,例2的算法用流程圖來表示,有兩個數(shù)a,b，按大小順序打印它們。 步驟1： 輸入a,b的值； 步驟2： 如果ab,則先打印a，再打印b；否則，先打印b，再 打印a； 算法結(jié)束。,（三）三種基本結(jié)構(gòu),順序結(jié)構(gòu)：,虛線框內(nèi)是一個順序結(jié)構(gòu)。 AB兩個框是順序執(zhí)行的： 按圖中所畫的框的順序，先執(zhí)行A操作，再執(zhí)行B操作。,選擇結(jié)構(gòu),也稱為分支結(jié)構(gòu)。 虛線框內(nèi)是一個選擇結(jié)構(gòu)。 此結(jié)構(gòu)包括一個選擇框，框中寫有一個條件，根據(jù)給定的條件是否成立，從而選擇執(zhí)行A框還是B框。 例如：條件可以是i101,B操作為空時，畫成直線,（三）三種基本結(jié)構(gòu),循環(huán)結(jié)構(gòu)（當型-while型）,虛線框內(nèi)是一個當型循環(huán)結(jié)構(gòu)。 當給定的條件成立時，執(zhí)行A框中的操作； 執(zhí)行完A操作后，判條件P是否成立； 如果仍成立，繼續(xù)執(zhí)行A操作； 如此反復執(zhí)行A框中的操作，直到條件P不成立為止。,條件P,A,成立,不成立,（三）三種基本結(jié)構(gòu),循環(huán)結(jié)構(gòu)（直到型-until型）,條件P,A,成立,不成立,虛線框內(nèi)是一個直到型循環(huán)結(jié)構(gòu)。 先執(zhí)行A框中的操作； 執(zhí)行完A操作后，判條件P是否成立； 如果不成立，繼續(xù)執(zhí)行A操作； 如此反復執(zhí)行A框中的操作，直到條件P成立為止。,（三）三種基本結(jié)構(gòu),（四）結(jié)構(gòu)化程序設(shè)計方法,三種基本結(jié)構(gòu)的共同點： 只有一個入口； 一個出口； 結(jié)構(gòu)內(nèi)每一部分都有機會被執(zhí)行。 結(jié)構(gòu)內(nèi)不存在“死循環(huán)“。 如條件永遠成立時，就成了“死循環(huán)“ 已經(jīng)證明，用上述三種基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)，可以解決任何復雜的問題。 由基本結(jié)構(gòu)構(gòu)成的算法屬于“結(jié)構(gòu)化“的算法 只要符合上述的四個特點的結(jié)構(gòu)，都稱為基本結(jié)構(gòu)。,對例1算法的流程圖的結(jié)構(gòu)化分析,計算1 x 3x5x.x101的值 步驟1：令p=1 步驟2：令i=3 步驟3：使p x i,并將乘積放入p中。通常表示為 p x i = p 步驟4：使 i 的值加2，表示為 i+ 2 = i 步驟5：如果i 不大于101，返回到步驟3繼續(xù)向下執(zhí)行；否則算法結(jié)束。p中的值即最后結(jié)果。,這兩個操作之間是順序關(guān)系,這是一個循環(huán)結(jié)構(gòu),這是一個順序結(jié)構(gòu),上述算法由基本結(jié)構(gòu)組成,對例2算法的流程圖的結(jié)構(gòu)化分析,有兩個數(shù)a,b，按大小順序打印它們。 步驟1： 輸入a,b的值； 步驟2： 如果ab,則先打印a，再打印b；否則，先打印b，再 打印a； 算法結(jié)束。,這是一個選擇結(jié)構(gòu),上述算法由基本結(jié)構(gòu)組成,用基本結(jié)構(gòu)的組合表示算法，從而去掉了流程線。避免了隨意的跳轉(zhuǎn)。 1973年兩名美國學者提出了一種新的流程圖形式，并用二人名字的第一個字母組合命名了該流程圖。即N-S流程圖，也稱盒圖。 三種基本結(jié)構(gòu)的表示：,（五）用N-S流程圖表示算法,不成立,當條件P成立時,直到條件P1成立,前面的算法用N-S流程圖來表示,計算1 x 3x5x.x11的值 步驟1：令p=1 步驟2：令i=1 步驟3：使p x i,并將乘積放入p中。通常表示為 p x i = p 步驟4：使 i 的值加2，表示為 i+ 2 = i 步驟5：如果i 不大于11，返回到步驟3繼續(xù)向下執(zhí)行；否則算法結(jié)束。p中的值即最后結(jié)果。,這兩個操作之間是順序關(guān)系,這是一個順序結(jié)構(gòu),這是一個循環(huán)結(jié)構(gòu),上述算法由基本結(jié)構(gòu)組成,N-S圖表示算法的優(yōu)點,比文字描述直觀、形象、 易于理解；比傳統(tǒng)流程圖緊湊易畫。尤其是它廢除了流程線，整個算法結(jié)構(gòu)是由各個基本結(jié)構(gòu)按順序組成的，N-S流程圖中的上下順序就是執(zhí)行時的順序。用N-S圖表示的算法都是結(jié)構(gòu)化的算法，因為它不可能出現(xiàn)流程無規(guī)律的跳轉(zhuǎn)，而只能自上而下地順序執(zhí)行。,小結(jié)：,一個結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順序組成的。在基本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個基本結(jié)構(gòu)范圍之內(nèi)(如循環(huán)中流程的跳轉(zhuǎn))；一 個非結(jié)構(gòu)化的算法可以用一個等價的結(jié)構(gòu)化算法代替，其功能不變 。如果一個算法不能分解為若干個基本結(jié)構(gòu)，則它必然不是一個結(jié)構(gòu)化的算法。,（六）用偽碼表示算法,偽碼 是用一種介于自然語言和計算機語言之間的文字和符號來描述算法。 好處： 書寫方便，格式緊湊，易懂，便于向計算機語言過渡。 前面的算法可用偽碼表示為：,開始 置p的初值為1 置i的初值為1 當i 小于11時，執(zhí)行下面的操作： 使 p=p x i 使 i=i+2 打印 p 的值 結(jié)束,（七）用計算機語言表示算法,只有用計算機語言描述的算法才能被計算機的編譯環(huán)境識別，并被處理、執(zhí)行。 用計算機語言表示算法必須嚴格遵守所用語言的語法規(guī)則。 前面幾種描述算法的方法對文字等格式要求不嚴，一般來說，只要能示意就行。,前面的算法用c語言表示,#include void main() int p,i; p=1; i=1; while(i=11) p=p*i; i=i+2; ,五、程序設(shè)計步驟,分析問題 確定解決方案 建立數(shù)學模型 設(shè)計算法 用計算機語言描述算法（即寫出源程序） 上機調(diào)試源程序：經(jīng)過編輯、編譯、連接、運行，得到可執(zhí)行的程序。（參看教科書第7頁上的圖1.1 上機步驟） 運行程序，得到需要的結(jié)果。,應當強調(diào)說明：寫出了C程序，仍然只是描述了算法，并未實現(xiàn)算法。只有運行程序才是實現(xiàn)算法。應該說，用計算機語言表示的算法是計算機能夠執(zhí)行的算法。,2.5 結(jié)構(gòu)化程序設(shè)計方法,一個結(jié)構(gòu)化程序 就是用高級語言表示的結(jié)構(gòu)化算法。用三種基本結(jié)構(gòu)組成的程序必然是結(jié)構(gòu)化的程序，這種程序便于編寫、便于閱讀、便于修改和維護。 結(jié)構(gòu)化程序設(shè)計強調(diào)程序設(shè)計風格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu)。 結(jié)構(gòu)化程序設(shè)計方法的基本思路是：把一個復雜問題的求解過程 分階段進行，每個階段處理的問題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。,用這種方法逐步分解，直到作者認為可以直接將各小段表達為文字語句為止。這種方法就叫 做“自頂向下，逐步細化”。,自頂向下，逐步細化方法的優(yōu)點： 考慮周全，結(jié)構(gòu)清晰，層次分明，作者容易寫，讀者容易看。如果發(fā)現(xiàn)某一部分中有一段內(nèi)容不妥，需要修改，只需找出該部分修改有關(guān)段落即可，與其它部分無關(guān)。我們提倡用這種方法設(shè)計程序。這就是用工程的方法設(shè)計程序。,模塊設(shè)計的方法： 模塊化設(shè)計的思想實際上是一種“分而治之”的思想，把一個大任務分為若干個子任務，每一個子任務就相對簡單了。 在拿到一個程序模塊以后，根據(jù)程序模塊的功能將它劃分為若干個子模塊，如果這些子模塊的規(guī)模還嫌大，還再可以劃分為更小的模塊。這個過程采用自頂向下方法來實現(xiàn)。 子模塊一般不超過50行。 劃分子模塊時應注意模塊的獨立性，即：使一個模塊完成一項功能，耦合性愈少愈好。,實驗一 C程序設(shè)計入門 目的要求： l 了解Turbo C2.0的集成開發(fā)環(huán)境，學習如何在Turbo C2.0中編輯、編譯、連接、運行與調(diào)試C程序； 2 通過運行簡單C程序，初步了解C源程序的特點。 實驗內(nèi)容： 1. 首先在e盤建立以自已學號命名（注意文件夾名或文件名都不要超過8個字符，也不要用漢字）的目錄，以后自已編輯和調(diào)試的有關(guān)C的源文件可保存在這個目錄下。 2. 啟動Turbo C 2.0，輸入教材第一章例1.1程序，并進行編譯和運行。 注意觀察：在此過程中，系統(tǒng)是用何命令進行編譯和運行的？編譯和連接后所得到的目標程序的后綴是什么？同時請注意相應的目標程序存放在何處？ 3. 輸入并運行教材第一章例1.2，了解如何在運行時向程序中的變量輸入數(shù)據(jù)。 4. 輸入并運行教材第一章例1.3。 5. 輸入并運行自已編寫的程序(教材第一章P14 三 編程題)。*,實驗二 C基本數(shù)據(jù)類型及運算 目的要求： l 掌握C語言中整型、字符型、實型變量的定義及賦值； 2 學會使用C的有關(guān)運算符及相關(guān)表達式； 3 進一步熟悉Turbo C 2.0的集成開發(fā)環(huán)境。 實驗內(nèi)容： 1. 編寫一個程序，從鍵盤接收3個實數(shù)（分別為10.0、20.0、5.0），輸出這3個數(shù)的和s、乘積t和平均值a。 2. 編程。要求用戶輸入兩個整數(shù)a、b（分別為20、10）， 讀取用戶從鍵盤輸入的值，然后： 1) 用整數(shù)輸出這兩個數(shù)的和、差； 2) 用長整型輸出這兩個數(shù)的積，用float輸出商； 3) 用整數(shù)輸出這兩個數(shù)的余數(shù)，用float輸出平均值。 3. 將第2題中的程序修改