1、第1章 程序設(shè)計(jì)基礎(chǔ)知識(shí),主要內(nèi)容： 1、程序設(shè)計(jì)概述（理解） 程序、程序設(shè)計(jì)語(yǔ)言等基本概念 程序設(shè)計(jì)的一般過(guò)程 如何學(xué)習(xí)程序設(shè)計(jì) 2、算法（熟悉） 3、結(jié)構(gòu)化程序設(shè)計(jì)方法（了解）,1.1 程序設(shè)計(jì)概述,一、概念： 1、程序（program）：程序是為解決某一問(wèn)題而編寫(xiě)的語(yǔ)句序列。通俗的說(shuō)，將解決一個(gè)實(shí)際問(wèn)題的具體操作步驟用某種計(jì)算機(jī)語(yǔ)言描述出來(lái)，就形成了程序。,2、程序設(shè)計(jì)(programming)：設(shè)計(jì)、書(shū)寫(xiě)及檢查程序的過(guò)程。包括分析問(wèn)題、確定解決方法、設(shè)計(jì)程序結(jié)構(gòu)，使問(wèn)題內(nèi)容或解題計(jì)劃變?yōu)橛?jì)算機(jī)能夠接受的指令或語(yǔ)句序列的過(guò)程。,例如：判斷輸入的任意整數(shù)n能否被3整除，程序如下： main

2、() int n; printf(n enter a integer:); scanf(%d, ,3、程序設(shè)計(jì)語(yǔ)言：人與計(jì)算機(jī)打交道時(shí)交流信息的一類(lèi)媒介和工具即計(jì)算機(jī)語(yǔ)言。 分類(lèi)： （1）機(jī)器語(yǔ)言（machine language）計(jì)算機(jī)直接使用的二進(jìn)制形式的程序語(yǔ)言或機(jī)器代碼。 （2）匯編語(yǔ)言（assembler language）一種面向機(jī)器的用符號(hào)表示的低級(jí)程序設(shè)計(jì)語(yǔ)言。相當(dāng)于機(jī)器指令的助記符號(hào)，與機(jī)器語(yǔ)言很接近。 add r1, 4 （3）高級(jí)語(yǔ)言:用接近自然語(yǔ)言和數(shù)學(xué)語(yǔ)言的語(yǔ)法符號(hào)描述基本操作的程序設(shè)計(jì)語(yǔ)言,4、其他概念 源程序：用戶用高級(jí)語(yǔ)言編寫(xiě)的程序稱為，C源程序文件名字后綴一般

3、必須為.c“。 程序加工：高級(jí)語(yǔ)言編寫(xiě)的程序，計(jì)算機(jī)不能直接執(zhí)行，需要把這個(gè)程序轉(zhuǎn)換成二進(jìn)制代碼的機(jī)器語(yǔ)言程序。這種轉(zhuǎn)換過(guò)程稱為程序加工。 匯編程序（assembler）：將匯編語(yǔ)言程序翻譯成機(jī)器語(yǔ)言程序的程序。 編譯程序（compiler)：把用高級(jí)語(yǔ)言寫(xiě)的源程序轉(zhuǎn)換為相應(yīng)的機(jī)器語(yǔ)言目標(biāo)模塊(object module)的程序。,二、程序設(shè)計(jì)的一般過(guò)程,用計(jì)算機(jī)解決問(wèn)題的基本過(guò)程如圖1.1所示： 對(duì)于簡(jiǎn)單問(wèn)題，前三步可看作一步，即分析問(wèn)題、設(shè)計(jì)算法。,程序設(shè)計(jì)的基本過(guò)程,(1)分析要解決的問(wèn)題，明確任務(wù)。 即分析要處理的數(shù)據(jù)是什么，從哪里來(lái)，作怎樣的處理，結(jié)果送往那里。 例如：求學(xué)生的平均成

4、績(jī)。 分析該問(wèn)題，明確它有三項(xiàng)功能： 輸入學(xué)生成績(jī)、求平均成績(jī)、輸出結(jié)果； 要處理的原始數(shù)據(jù)為：學(xué)生的成績(jī)； 要進(jìn)行的處理為：求平均； 結(jié)果為：平均值，送屏幕顯示或保存于文件中。,（2）分析問(wèn)題，建立數(shù)學(xué)模型，并選擇合適的解決方案 例如：分析求平均成績(jī)的處理過(guò)程，可以將數(shù)據(jù)的具體含義去掉，抽象為：計(jì)算一批數(shù)據(jù)的平均值。,（3）確定數(shù)據(jù)結(jié)構(gòu)和算法 ：數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)的組織方式，算法是對(duì)數(shù)據(jù)處理過(guò)程的具體描述。不同的數(shù)據(jù)結(jié)構(gòu)對(duì)應(yīng)不同的算法。 例如：有一堆盒子，上面有編號(hào)（設(shè)編號(hào)為兩位數(shù)字），要查找某個(gè)編號(hào)的盒子，如何實(shí)現(xiàn)？ 方法1：若該堆盒子已排成一隊(duì)，則可以從第一個(gè)開(kāi)始逐個(gè)比較，直至找到或找完為止

5、。 方法2：若該堆盒子已按編號(hào)排成多隊(duì)，每一隊(duì)的高位數(shù)字相同，則可以根據(jù)要找的盒子的高位直接確定他在那一隊(duì)，然后在該隊(duì)中再逐個(gè)查找。 由此可見(jiàn)，只有先確定了數(shù)據(jù)結(jié)構(gòu)，才能設(shè)計(jì)相應(yīng)的算法。,(4)編碼：即編寫(xiě)程序 。 用某種計(jì)算機(jī)語(yǔ)言將上一步設(shè)計(jì)好的算法描述出來(lái)，就是程序。 可見(jiàn)，算法是編程的基礎(chǔ)。 (5)調(diào)試程序：將源程序送入計(jì)算機(jī)，進(jìn)行排錯(cuò)、試運(yùn)行，調(diào)試的結(jié)果是得到一個(gè)能正確運(yùn)行的程序。 通常，調(diào)試程序至少占整個(gè)程序設(shè)計(jì)工作量的一半。 (6)整理資料，交付使用,三、學(xué)習(xí)程序設(shè)計(jì)的方法,1、一講、二練、三考 2、多讀源程序、多編寫(xiě)程序、多上機(jī)調(diào)試 3、忌上課只聽(tīng)不記、忌“紙上談兵”、忌課下不練

6、習(xí) 具體要求： 1、上課有重點(diǎn)、有選擇的記 2、上機(jī)有準(zhǔn)備：準(zhǔn)備好課本、筆記、作業(yè)等 3、除課后習(xí)題必須全部解決外，多做一些二級(jí)考試的模擬題 4、做一個(gè)自己感興趣的完整的程序（小項(xiàng)目）,1.2 算法及其描述,一、算法： 對(duì)解決某一特定問(wèn)題的操作步驟的具體描述。 廣義的說(shuō)，算法就是為解決一個(gè)問(wèn)題而采取的方法和步驟。 程序算法十?dāng)?shù)據(jù)結(jié)構(gòu) 就是說(shuō)：“程序是在數(shù)據(jù)的特定的組織方式的基礎(chǔ)上，對(duì)抽象算法的具體描述”。作為程序設(shè)計(jì)人員，在設(shè)計(jì)算法前，必須認(rèn)真考慮和設(shè)計(jì)數(shù)據(jù)的組織方式，即數(shù)據(jù)結(jié)構(gòu)；然后針對(duì)具體的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)相應(yīng)的操作步驟，即算法。,二、算法特性 1.有窮性 操作步驟是有限的，且有合理限度 2.

7、確定性 每個(gè)步驟都是確定的，不能是含糊摸棱兩可的 3.有零個(gè)或多個(gè)輸入 在執(zhí)行算法時(shí)需要從外界取得必要的信息 4.有一個(gè)或多個(gè)輸出 算法的目的是為了輸出，沒(méi)有輸出的算法是沒(méi)有意義的 5.有效性 算法中的每個(gè)步驟都應(yīng)當(dāng)能有效執(zhí)行，并得到確定的結(jié)果,三、算法的描述,描述算法的方法有多種，常用有： 自然語(yǔ)言（描述不夠嚴(yán)格，限于簡(jiǎn)單問(wèn)題） 流程圖* （同一問(wèn)題的流程圖不唯一） N-S 圖* （結(jié)構(gòu)清晰，但難于修改） PAD圖 （結(jié)構(gòu)清晰，唯一性好） 偽代碼* （靈活，但需要有一定的程序設(shè)計(jì)基礎(chǔ)） 學(xué)習(xí)建議： 流程圖或N-S圖一定要熟練掌握，其他表示法不要求。,1、用自然語(yǔ)言描述 通俗易懂，但文字冗長(zhǎng)，

8、易出現(xiàn)“歧義性”，且描述不夠嚴(yán)格，故僅限于簡(jiǎn)單問(wèn)題）,例1. 1 計(jì)算任意長(zhǎng)方形的面積。 分析： 要實(shí)現(xiàn)的功能有： 輸入長(zhǎng)和寬，計(jì)算面積，輸出結(jié)果。 先定義數(shù)據(jù)結(jié)構(gòu)：程序中要處理的數(shù)據(jù)有三個(gè)，即長(zhǎng)、寬、面積，設(shè)分別用實(shí)型變量length、width、area表示。則算法如下： 輸入長(zhǎng)和寬分別存入length, width 計(jì)算面積：lengthwidth = area 輸出結(jié)果area,例1. 2 計(jì)算s1+s2+s3+s4+s5（其中si表示第i個(gè)數(shù)）。 分析：要實(shí)現(xiàn)的功能是“加法運(yùn)算”，要輸入的數(shù)據(jù)是s1s5，對(duì)其進(jìn)行的運(yùn)算是“加”，結(jié)果是“累加和”，并輸出。 先定義數(shù)據(jù)結(jié)構(gòu)： 設(shè)變量 s

9、 表示累計(jì)和，初值為0； 變量 x 表示每次要處理的數(shù)據(jù)（s1s5中的一個(gè)）； 變量 i 表示要處理第幾個(gè)數(shù)（其取值范圍可以是：15），設(shè)初值為1。,例1.2算法,根據(jù)以上定義，算法設(shè)計(jì)如下： S1: 賦初值 0=s S2: 賦初值 1=i S3: 輸入第i個(gè)數(shù)x S4: 累加：s+x=s S5: 計(jì)數(shù)增值：i+1=i S6: 若i5，表示數(shù)據(jù)還未處理完，返回 S3 繼續(xù)重復(fù)S3、S4、S5；否則，計(jì)算結(jié)束，執(zhí)行S7。 S7:輸出結(jié)果 s。,例1. 3 判斷任意整數(shù)是奇數(shù)還是偶數(shù)。 分析：設(shè)整型變量 n 表示要處理的整數(shù)， 則算法為： 首先輸入n， 然后判斷條件“n%2等于0”（%是求余運(yùn)算符

10、）是否成立， 若條件成立，則輸出“n是偶數(shù)”； 否則輸出“n是奇數(shù)”。,2、用流程圖表示算法,流程圖是用幾種圖形、箭頭線和文字說(shuō)明來(lái)表示算法的框圖。 流程圖中規(guī)定使用的符號(hào)如圖1.2所示 用流程圖的優(yōu)點(diǎn)是：直觀形象、易于理解，能將設(shè)計(jì)者的思路清楚地表達(dá)出來(lái)，便于以后檢查修改和編程。,結(jié)構(gòu)化的流程圖：即一個(gè)流程圖由三種基本結(jié)構(gòu)（順序、選擇、循環(huán)結(jié)構(gòu)）組成，這三種基本結(jié)構(gòu)可以相互嵌套，組合成復(fù)雜的算法。,注：P表示條件，A、B表示一個(gè)基本操作或一個(gè)基本結(jié)構(gòu)。,例1. 1 計(jì)算長(zhǎng)方形的面積（用流程圖表示的算法如圖1.4所示）。,例1. 2 判斷任意整數(shù)是奇數(shù)還是偶數(shù)。,3. 用N-S圖表示算法,用N

11、-S圖表示的三種基本結(jié)構(gòu),當(dāng)型循環(huán)：當(dāng)條件P成立時(shí)反復(fù)執(zhí)行A操作，直到條件不成立為止。 直到型循環(huán)：先執(zhí)行A操作，若條件不成立繼續(xù)執(zhí)行A操作，若條件成立則退出循環(huán)。,例1. 3 計(jì)算長(zhǎng)方形的面積 例1. 4 判斷任意整數(shù)是奇數(shù)還是偶數(shù) 例1. 5 計(jì)算s1+s2+s3+s4+s5（其中si表示第i個(gè)數(shù)）,1.3 結(jié)構(gòu)化程序設(shè)計(jì),結(jié)構(gòu)化程序設(shè)計(jì)思想包括兩個(gè)方面的內(nèi)容： 模塊化設(shè)計(jì)和結(jié)構(gòu)化編碼 特點(diǎn)： 結(jié)構(gòu)化的程序結(jié)構(gòu)清晰，層次分明，便于程序員編寫(xiě)、閱讀和修改，提高了程序的可靠性，保證了程序的高質(zhì)量、高效率。 為了得到結(jié)構(gòu)化的程序，必須強(qiáng)調(diào)程序設(shè)計(jì)的規(guī)范化，采用結(jié)構(gòu)化的程序設(shè)計(jì)方法。,1. 模塊化

12、設(shè)計(jì)方法,模塊化設(shè)計(jì)是指把一個(gè)大程序按人們能理解的大小規(guī)模進(jìn)行分解。 其主要特點(diǎn)是： （1）模塊間的接口關(guān)系比較簡(jiǎn)單，并且每個(gè)模塊都是人的智力所能及的。 （2）各模塊的功能比較單一，當(dāng)需要修改某一功能時(shí)，一般只涉及到一個(gè)模塊，不會(huì)影響到其他模塊。 （3）人們可以脫離程序的上、下文也能單獨(dú)地驗(yàn)證一個(gè)模塊的正確性。 （4）在擴(kuò)充系統(tǒng)或建立新系統(tǒng)時(shí)，可以充分利用已有的一些模塊，用積木式的方法進(jìn)行開(kāi)發(fā)。,自頂向下，逐步細(xì)化。（常用） 其基本思想是：將一個(gè)復(fù)雜的大任務(wù)分解為若干個(gè)較小的任務(wù)，如果這些子任務(wù)還較復(fù)雜，再將其進(jìn)行劃分，直到每個(gè)任務(wù)都能很容易的實(shí)現(xiàn)其具體細(xì)節(jié)，然后“分而治之”，即分別實(shí)現(xiàn)各個(gè)小任務(wù)。這樣，對(duì)一個(gè)大任務(wù)的處理就變成了對(duì)一個(gè)個(gè)小任務(wù)的實(shí)現(xiàn)，使問(wèn)題變得相對(duì)簡(jiǎn)單了。例學(xué)生管理系統(tǒng)。 自頂向下、逐步細(xì)化的設(shè)計(jì)過(guò)程具有以下兩個(gè)優(yōu)點(diǎn)： （1）自頂向下、逐步細(xì)化的方法符合人們解決復(fù)雜問(wèn)題的普遍規(guī)律，可以顯著提高程序設(shè)計(jì)的效率； （2）用先全局后局部、先整體后細(xì)節(jié)、先抽象后具體的逐步細(xì)化過(guò)程設(shè)計(jì)出的程序具有清晰