C語言程序設(shè)計教學(xué)課件：算法與程序設(shè)計基礎(chǔ)

1、C語言程序設(shè)計1 本章要點 什么是程序設(shè)計 什么是算法，如何設(shè)計和表示算法 結(jié)構(gòu)化程序設(shè)計的思想和方法2計算機語言：是規(guī)則和符號的集合，是與計算機交流的工具。必須具有數(shù)據(jù)表達(dá)和數(shù)據(jù)處理（流程控制）的能力。程序：求解問題的指令序列軟件：程序的集合學(xué)習(xí)語言 設(shè)計程序 制作軟件概念：學(xué)軟件：學(xué)思想、學(xué)功能、學(xué)操作。熟練工種學(xué)語言：學(xué)規(guī)則、學(xué)方法、學(xué)設(shè)計、學(xué)應(yīng)用。 規(guī)范學(xué)習(xí)，靈活應(yīng)用3計算機語言分類面向過程語言面向?qū)ο笳Z言FORTRANBASICCPASCALCOBOLLISPC+C#Visual CVisual BASICVisual J+系統(tǒng)軟件設(shè)計具有圖形功能科學(xué)計算商用人工智能41.1 程序設(shè)

2、計的基本概念數(shù)據(jù)元素：數(shù)據(jù)的最小單位數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素的組織形式程序設(shè)計數(shù)據(jù)結(jié)構(gòu)算法方法工具數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣決定了 軟件或程序的復(fù)雜程度和面貌一個程序應(yīng)包括兩個方面的內(nèi)容:對數(shù)據(jù)的描述：數(shù)據(jù)結(jié)構(gòu)對操作的描述：算法完整的程序設(shè)計應(yīng)該包括四部分:5程序設(shè)計的步驟分析問題，建立數(shù)學(xué)模型確定數(shù)據(jù)結(jié)構(gòu)確定算法，描述算法編制程序，調(diào)試程序運行結(jié)果6程序的三種基本結(jié)構(gòu)1.順序結(jié)構(gòu) 程序按照語句的書寫次序順序執(zhí)行。 BA 先執(zhí)行A操作，再執(zhí)行B操作，兩者是順序執(zhí)行關(guān)系。7 2.選擇結(jié)構(gòu) 通過判斷特定條件，選擇一個分支執(zhí)行。當(dāng)P條件成立時，執(zhí)行A操作，否則執(zhí)行B操作APB 成立不成立 語句不成立 P成立當(dāng)P條件成

3、立時，執(zhí)行語句操作，否則跳過語句操作8 3. 循環(huán)結(jié)構(gòu) 在給定條件下，反復(fù)執(zhí)行循環(huán)體，直到條件不滿足為止.(1)形式a （當(dāng)型循環(huán)結(jié)構(gòu)）不成立 PA成立 當(dāng)P條件成立時，反復(fù)執(zhí)行A,直到P為零為止。9(2)形式b （直到型循環(huán)結(jié)構(gòu)）先執(zhí)行A操作，再判斷P是否成立，若P成立，再執(zhí)行A，直到P不成立為止。AP成立不成立 10算法：完成一項任務(wù)的具體步驟計算機語言的別名：算法語言1. 算法的概念1.2 算法概述 “一個算法，就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個解決某一特定類型的問題的運算序列?！?任何解決問題的過程都是由一定的步驟組成的，把解決問題確定的方法和有限的步驟稱作為算法。11例1：

4、計算函數(shù)M(x)的值。函數(shù)M(x)為：算法分析：這是一個數(shù)值運算問題。其中M代表要計算的函數(shù)值，有兩個不同的表達(dá)式，根據(jù)x的取值決定采用哪一個算式。根據(jù)計算機具有邏輯判斷的基本功能，用計算機解題的算法如下：12 將a、b、c和x的值輸入到計算機； 判斷xa?如果條件成立，執(zhí)行第步，否則執(zhí)行第步； 按表達(dá)式bx+a2計算出結(jié)果存放到M中，然后執(zhí)行第步； 按表達(dá)式a(c-x)+c2計算出結(jié)果存放到M中，然后執(zhí)行第步； 輸出M的值； 算法結(jié)束。這是用自然語言描述的算法13例2：有黑和藍(lán)兩個墨水瓶，但卻錯把黑墨水裝在了藍(lán)墨水瓶子里，而藍(lán)墨水錯裝在了黑墨水瓶子里，要求將其互換。算法分析：這是一個非數(shù)值運

5、算問題。因為兩個瓶子的墨水不能直接交換，所以，解決這一問題的關(guān)鍵是需要引入第三個墨水瓶。設(shè)第三個墨水瓶為白色，其交換步驟如下：14將藍(lán)瓶中的黑墨水裝入白瓶中將黑瓶中的藍(lán)墨水裝入藍(lán)瓶中將白瓶中的黑墨水裝入黑瓶中交換結(jié)束152.算法的基本特征 算法是一個有窮規(guī)則的集合，這些規(guī)則確定了解決某類問題的一個運算序列。 算法的基本特征：有窮性：算法必須在執(zhí)行有限個操作后終止； 確定性：算法中每一步的含義必須是確切的，不能出現(xiàn)任何二義性；有效性：算法中的每一步操作都應(yīng)該能有效執(zhí)行，一個不可執(zhí)行的操作是無效的；有零個或多個輸入：執(zhí)行算法時，從外界獲得必要的信息 ；有一個或多個輸出：算法的解就是輸出。163.算

6、法的常用表示方法可以用不同的方法表示算法，常用方法有：自然語言傳統(tǒng)流程圖結(jié)構(gòu)化流程圖 17（1）自然語言自然語言即是使用漢語、英語或其他語言去描述算法。例有50名學(xué)生的成績，要求將他們之中80分以上的成績打印出來。設(shè)用g代表學(xué)生成績，gi 代表第i個學(xué)生成績。算法可表示如下：1）使i=1 ；2）如果gi 80 ，則打印 gi ，否則不打??；3）使i的值加1 ；4）如果 i 50, 返回S2， 繼續(xù)執(zhí)行； 否則，算法結(jié)束。特點：描述算法通俗易懂，容易產(chǎn)生歧義。對復(fù)雜問題，語句繁瑣、冗長，并且很難清楚地表達(dá)算法的邏輯流程，往往需要根據(jù)上下文判別其含義，尤其對描述含有選擇、循環(huán)結(jié)構(gòu)的算法，不太方便和

7、直觀，一般不常使用。18(2)傳統(tǒng)流程圖 美國國家標(biāo)準(zhǔn)化協(xié)會ANSI(American National Standard Institute)規(guī)定了一些常用的流程圖符號：起止框判斷框處理框輸入/輸出框注釋框流向線連接點19程序流程圖表示開始1 igi=80輸出gii+1 ii50結(jié)束成立不成立不成立成立傳統(tǒng)流程圖用流程線指出各框的執(zhí)行順序，對流程線的使用沒有嚴(yán)格限制。20傳統(tǒng)流程圖的流程可以是：缺點：使用者可以毫不受限制地使流程隨意地轉(zhuǎn)向，使流程圖變得毫無規(guī)律，難以閱讀、修改，使算法的可靠性和可維護(hù)性難以保證。解決辦法：必須限制箭頭的濫用，即不允許無規(guī)律地使流程隨意轉(zhuǎn)向，只能順序的進(jìn)行下去。

8、 21（3）NS流程圖NS流程圖 由美國學(xué)者I.Nassi和B.Shneiderman提出表示算法的圖形工具?；締卧蔷匦慰?用不同的形狀線分割,表示三種結(jié)構(gòu)。只有一個入口,一個出口,沒有流程線。N-S圖的優(yōu)點 比文字描述直觀、形象、 易于理解；比傳統(tǒng)流程圖緊湊易畫。尤其是它廢除了流程線，整個算法結(jié)構(gòu)是由各個基本結(jié)構(gòu)按順序組成的，N-S流程圖中的上下順序就是執(zhí)行時的順序。22 三種基本程序結(jié)構(gòu)的NS流程圖條件TF語句1 語句22.選擇結(jié)構(gòu)語句1語句21.順序結(jié)構(gòu)3.循環(huán)結(jié)構(gòu) 循環(huán)體循環(huán)體當(dāng)滿足條件時 直到條件成立循環(huán)結(jié)構(gòu)一循環(huán)結(jié)構(gòu)二230t,0ii+1i t+it直到 i100輸出 t 的值

9、傳統(tǒng)流程圖與N-S流程圖的比較i100 NY開始 0t,0ii+1i t+it輸出 t 的值結(jié)束例1：1+2+3+ 加到100為止24例：打印50名學(xué)生中成績高于80分的學(xué)號和成績用N-S圖表示。 251. 枚舉法（窮舉法）特點:算法簡單，容易理解，運算量大?；舅枷耄?根據(jù)題目的部分條件確定答案的大致范圍，然后在此范圍內(nèi)對所有可能的情況逐一驗證，直到所有情況均通過驗證。若某個情況符合題目條件，則為本題的一個答案；若全部情況驗證完后均不符合題目的條件，則問題無解。 如：百元買百雞問題。假定小雞每只0.5元，公雞每只2元，母雞每只3元?，F(xiàn)在有100元錢要求買100只雞，問共有幾種購雞方案？ 根據(jù)

10、題目，設(shè)母雞、公雞、小雞各為x,y,z只，列出方程為：x+y+z=100，3x+2y+0.5z=100 利用窮舉法，將各種可能的組合一一測試，輸出符合條件的組合。即在各個變量的取值范圍內(nèi)不斷變化x,y,z的值，窮舉x,y,z全部可能的組合，若滿足方程組則是一組解。 1.3 幾種常用算法介紹26#include stdio.hmain() int x,y,z; printf(母雞 公雞 小雞); for(x=0;x=33;x+) for(y=0;y=1;i-) x=(x+1)*2; printf(第 %d 天的桃子數(shù)為：%d只, i,x); printf(n); 小猴吃桃子源程序：303.求最大值、最小值問題 采用如同打擂臺的方法。 在n個數(shù)中，先假設(shè)第一個數(shù)為最大值，成為擂主，依次同第2，3，n個數(shù)據(jù)逐一比較，一旦某個數(shù)大，馬上替換擂主；所有值比較完，最大值也就獲得。