《程序設(shè)計基礎(chǔ)知識》PPT課件.ppt

1、C語言程序設(shè)計,計算機學院軟件工程教研室,預(yù)備知識與參考書,計算機文化基礎(chǔ) 參考書 C語言程序設(shè)計 清華大學出版社 譚浩強編 C語言程序設(shè)計教程習題與上機指導(dǎo) 北京理工大學出版社 王樹武編 最好的參考資料是網(wǎng)絡(luò)資料！,本課程總的教學要求,教學內(nèi)容： 理論講解+上機實踐，使學生了解面向過程程序設(shè)計的思想，掌握基本的程序設(shè)計方法（三種程序設(shè)計結(jié)構(gòu)）。 教學目標： 掌握C語言的基本語法和規(guī)定 掌握程序設(shè)計基本算法和思路 提高上機操作能力 培養(yǎng)自學能力，開拓思路 養(yǎng)成良好的程序設(shè)計習慣,如何學,要求： 課堂學和課下學并重。出席并認真聽每節(jié)課，完成作業(yè)和參加上機實習。 如何學： 以課堂為主，重視課下自學

2、。重視開始，掌握主線和學習方法，強調(diào)實踐，閱讀參考書，多動手編程。有問題要及時解決。 目標： 1.通過考試; 2.掌握C語言的的基本知識，精通C語言程序設(shè)計; 3.了解不同的程序設(shè)計方法的基本概念,學習過程中可能出現(xiàn)的問題,注重理論學習，忽視上機編程實踐 入門時自以為難度大，產(chǎn)生畏難情緒 太注重學習語句的語法規(guī)定，忽視了對編程的思路和方法的訓練 急于求成，總想編寫綜合性的程序，忽視基本概念，忽視基本功的訓練和練習,學習方法,認真聽講，積極思考，提高上課效率； 上機編程是學好C語言的關(guān)鍵環(huán)節(jié)，多上機，多練習，提高動手能力； 加強交流，多討論，多請教，多提問，及時答疑解惑； 開闊眼界，打開思路，多

3、看幾本參考書； 初學時重點是掌握C語言的語法和規(guī)定； 后期應(yīng)重點掌握編程思路和基本算法。,要求,上課請不要遲到 課上不要影響其他同學 請按時交作業(yè) 上機要事先編好程序，提高上機效率 努力加強自學，提高自學能力,考核與成績評定,考核性質(zhì)：考試課，百分制 考試方法：閉卷、筆試 考試用時：期末120分鐘 成績評定： 期末總評成績=平時成績* 20%（出勤成績*10%+作業(yè)成績*10%）+實驗成績20%+卷面成績60% 補考方法： 期末總評成績低于60分的學生，須參加學校統(tǒng)一組織的補考。 補考總成績平時成績*20+補考卷面成績*80,課程結(jié)構(gòu)與課時安排：總共48學時(32+16),第1章：程序設(shè)計基礎(chǔ)

4、知識 2學時 第2章：C語言概述 2學時 第3章：數(shù)據(jù)類型與運算規(guī)則 4學時 第4章：順序結(jié)構(gòu)的程序設(shè)計2學時 第5章：選擇結(jié)構(gòu)的程序設(shè)計2學時 第6章：循環(huán)結(jié)構(gòu)的程序設(shè)計6學時 第7章：數(shù)組8學時 第8章：函數(shù)6學時,第1章 程序設(shè)計基礎(chǔ)知識,1.程序與程序語言 2.算法和算法的表示 3.結(jié)構(gòu)化程序設(shè)計方法,1.程序與程序語言 1.1 什么是計算機 1.2 什么是計算機程序 1.3 什么是計算機語言 1.4 C語言的發(fā)展及其特點,目前的PC機可每秒執(zhí)行十億次加法 人用計算器一生也完不成PC機1秒鐘完成的計算量,1.1 什么是計算機,硬件（hardware） 鍵盤、鼠標、顯示器、硬盤、DVDs

5、、內(nèi)存、CPU 硬件成本下降很快 摩爾定律 每過18個月微芯片的集成度翻一番，而芯片價格保持不變 軟件（software） 運行于計算機之上的程序（Program） 如何降低軟件開發(fā)成本？,1.1 什么是計算機,計算機行業(yè)的夢想,計算機行業(yè)的夢想 與人自然交流，像人一樣地思考 人工智能（Artificial Intelligence） 圖靈測試 1950年，英國數(shù)學家A.M.Turing在思想（mind）雜志上發(fā)表“計算機與人工智能”一文，提出判定機器是否具有智能的測試方法,計算機行業(yè)的夢想,博弈被認為是智能活動，AI之初主要研究下棋程序 1997年，IBM公司研制的深藍超級計算機在一場“人機

6、大戰(zhàn)”中打敗了國際象棋大師卡斯帕羅夫 被譽為“人工智能的一大勝利” 世界排名第二的棋手印度人阿南得說： 這是一個像人的機器和一個像機器的人之間的戰(zhàn)斗 深藍的主要研制者之一許峰雄博士： 勝利靠的只是不知疲倦地高速運算，并不是什么智能 深藍中輸入了近200萬棋譜,1.2 什么是計算機程序,程序：一組計算機能識別和執(zhí)行的指令 只要讓計算機執(zhí)行這個程序，計算機就會自動地、有條不紊地進行工作 計算機的一切操作都是由程序控制的，離開程序，計算機將一事無成,編寫程序源代碼（Source Code）的人 程序員（Programmer） 計算機、程序員、程序之間的關(guān)系 如果計算機是樂隊，那么程序員就是指揮家，程

7、序就是樂譜。 如果計算機是軍隊，那么程序員就是總司令，程序就是作戰(zhàn)計劃。,1.2 什么是計算機程序,1.3 什么是計算機語言,計算機語言：人和計算機交流信息的、計算機和人都能識別的語言,1.3 什么是計算機語言,計算機語言發(fā)展階段： 機器語言（由0和1組成的指令） 符號語言（用英文字母和數(shù)字表示指令） 高級語言（接近于人的自然語言和數(shù)學語言） 面向過程的語言 （非結(jié)構(gòu)化的語言、結(jié)構(gòu)化語言） 面向?qū)ο蟮恼Z言,低級語言,很像廚師的菜譜，定義了執(zhí)行某個任務(wù)所需的步驟 但不幸和不同的是，你不能使用你自己的母語來寫Code,1.3 什么是計算機語言,計算機語言與自然語言比較,;,計算機能讀懂的語言 機器

8、語言（Machine Language） 由一系列二進制0和1組成 機器語言編寫的1+1程序 低級語言,10111000 00000001 00000000 00000101 00000001 00000000,像不像天書？,1.3 什么是計算機語言,程序設(shè)計語言（programming language） BASIC語言編寫的1+1程序 C語言編寫的1+1程序 既不是英語，也非機器語言 但更像英語 高級語言 比寫機器語言程序容易，但比使用英語難,PRINT 1+1,結(jié)果顯示在屏幕上,#include main() printf(%dn, 1+1); ,1.3 什么是計算機語言,怎樣讓計算機讀

9、懂高級語言？,編譯器（Compiler） 把源代碼轉(zhuǎn)換為可被計算機理解的機器代碼 把機器代碼以可執(zhí)行文件（Executable File）的形式保存在磁盤上 一種程序設(shè)計語言對應(yīng)一種編譯器,程序員按照該語言的語法編寫程序源代碼 把自己的意圖寫入源代碼中 編譯器讀入源代碼 把程序員的意圖轉(zhuǎn)換成可執(zhí)行程序，供他人使用,C語言,可執(zhí)行程序,編譯器,怎樣讓計算機讀懂高級語言？,程序設(shè)計語言是人與計算機進行交流的語言 有很多種，分別適合做不同的事情 現(xiàn)在人還只能主動學計算機的語言 做不到計算機學會人的語言 當計算機懂了人的自然語言，就幾乎不再需要編程，想讓計算機干什么，盡管對著它說好了，那時程序員可能也

10、就失業(yè)了。,怎樣讓計算機讀懂高級語言？,程序是如何運行的？,計算機把機器代碼讀入到內(nèi)存（Memory） 由CPU運行這些代碼 讀取輸入（Input） 產(chǎn)生輸出（Output） 完成程序員預(yù)定的功能 計算機專業(yè)后續(xù)課程 計算機原理 編譯原理 操作系統(tǒng),程序開發(fā)步驟,分析 設(shè)計 編碼 鏈接 編譯 編輯 運行 調(diào)試,計算機為什么用二進制呢？,為什么不用我們?nèi)粘Ｊ煜さ氖M制呢？ 二進制在在電器元件中容易實現(xiàn) 計算機進行二進制運算比進行十進制運算簡單 1946年，馮.諾伊曼在計算機中引入二進制，提出著名的馮.諾伊曼結(jié)構(gòu)，至今仍被采用，被譽為“計算機之父”,“馮諾依曼機”結(jié)構(gòu),大腦,記憶裝置,眼睛和耳朵,

11、計算機語言的發(fā)展,機器語言,匯編語言,高級語言,面向過程,面向?qū)ο?智能語言,第四代語言,CPU指令系統(tǒng)，由0、1序列構(gòu)成的指令碼組成 如：10000000 加 10010000 減,用助記符號描述的指令系統(tǒng) 如 ADD A, B,面向機器的語言,程序設(shè)計是數(shù)據(jù)被加工的過程,客觀世界可以分類，對象是類的實例對象是數(shù)據(jù)和方法的封裝 對象間通過發(fā)送和接受消息發(fā)生聯(lián)系,程序設(shè)計關(guān)鍵是定義類，并由類派生對象,告知計算做什么，無須告知怎么做,人工智能，接近自然語言,高級語言的魅力,易學、易用、易讀、易懂、強大、可移植 百家爭鳴，據(jù)不完全統(tǒng)計2500種，絕大多數(shù)是高級語言 http:/people.ku.

12、edu/nkinners/LangList/Extras/langlist.htm可看到其列表和簡介 影響最大、壽命最長的是C語言 程序設(shè)計語言數(shù)以千計，能廣為流傳的不過幾十種，能夠風光20年的更是屈指可數(shù),C程序設(shè)計語言,C語言被分類為高級語言，但實際上它是一種介于高級語言和低級語言之間的語言。 很多流行語言、新生語言都借鑒了它的思想、語法 從C+，到Java，再到C# 正確地學好C語言，是學習這些流行語言的基礎(chǔ)。,C程序設(shè)計語言的地盤,硬件（Hardware）,操作系統(tǒng)（OS）,應(yīng)用程序（Application）,應(yīng)用平臺,基于平臺的應(yīng)用程序,低級語言的地盤,高級語言的地盤,C語言的地盤,

13、1.4 C語言的發(fā)展及其特點,C語言是國際上廣泛流行的計算機高級語言。 C語言的發(fā)展：,BCPL語言,B語言,C語言,精練、接近硬件，但 過于簡單, 無數(shù)據(jù)類型,具有多種數(shù)據(jù)類型,2.算法和算法的表示 2.1 什么是算法 2.2 簡單的算法舉例 2.3 算法的特性 2.4 怎樣表示一個算法,一個程序主要包括以下兩方面的信息： (1) 對數(shù)據(jù)的描述。在程序中要指定用到哪些數(shù)據(jù)以及這些數(shù)據(jù)的類型和數(shù)據(jù)的組織形式 這就是數(shù)據(jù)結(jié)構(gòu)(data structure) (2) 對操作的描述。即要求計算機進行操作的步驟 也就是算法(algorithm),程序設(shè)計,數(shù)據(jù)是操作的對象 操作的目的是對數(shù)據(jù)進行加工處

14、理，以得到期望的結(jié)果 著名計算機科學家沃思(Nikiklaus Wirth)提出一個公式： 算法 + 數(shù)據(jù)結(jié)構(gòu) = 程序,程序設(shè)計,一個程序除了算法和數(shù)據(jù)結(jié)構(gòu)這主要要素外，還應(yīng)當采用結(jié)構(gòu)化程序設(shè)計方法進行程序設(shè)計，并且用某一種計算機語言表示 算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計方法和語言工具是一個程序設(shè)計人員應(yīng)具備的知識,程序設(shè)計,算法是解決“做什么”和“怎么做”的問題 程序中的操作語句，是算法的體現(xiàn) 不了解算法就談不上程序設(shè)計,程序設(shè)計,1.分析問題，建立數(shù)學模型； 2.確定數(shù)據(jù)結(jié)構(gòu)和算法； 3.編制程序； 4.調(diào)試程序。,如何進行程序設(shè)計？,2.1 什么是算法,廣義地說，為解決一個問題而采取的方法和步

15、驟，就稱為“算法” 對同一個問題，可以有不同的解題方法和步驟 為了有效地進行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法,計算機算法可分為兩大類別： 數(shù)值運算算法 非數(shù)值運算算法 數(shù)值運算的目的是求數(shù)值解 非數(shù)值運算包括的面十分廣泛，最常見的是用于事務(wù)管理領(lǐng)域,2.1 什么是算法,2.2簡單的算法舉例,例2.1 求12345 可以用最原始的方法進行： 步驟1：先求1*2，得到結(jié)果2。 步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6。 步驟3：將6再乘以4，得24。 步驟4：將24再乘以5，得120。這就是最后的結(jié)果。（X1000?）,太繁瑣,改進的算法： 設(shè)變量p為被乘數(shù)

16、變量i為乘數(shù) 用循環(huán)算法求結(jié)果,2.2簡單的算法舉例,S1：使p=1，或?qū)懗?p S2：使i=2，或?qū)懗?i S3：使p與i相乘，乘積仍放在變量p中，可表示為：p*ip S4：使i的值加1，即i+1 i S5：如果i不大于5，返回重新執(zhí)行S3；否則，算法結(jié)束 最后得到p的值就是 5!的值,2.2簡單的算法舉例,S1：使p=1，或?qū)懗?p S2：使i=2，或?qū)懗?i S3：使p與i相乘，乘積仍放在變量p中，可表示為：p*ip S4：使i的值加1，即i+1 i S5：如果i不大于5，返回重新執(zhí)行S3；否則，算法結(jié)束 最后得到p的值就是 5!的值 if i11返回S3？,若求1357911,3,3,

17、2,2,11,相當于i 11,2.2簡單的算法舉例,例2.2 有50個學生，要求將成績在80分以上的學生的學號和成績輸出。 用ni代表第i個學生學號，gi表示第i個學生成績 S1：1i S2：如果gi80， 則輸出ni和gi，否則不輸出 S3：i+1i S4：如果i50，返回到步驟S2，繼續(xù)執(zhí)行，否則，算法結(jié)束,例2.3 判定20002500年中的每一年是否閏年，并將結(jié)果輸出。 閏年的條件： (1)能被4整除，但不能被100整除的年份都是閏年，如2008、2012、2048年 (2)能被400整除的年份是閏年，如2000年 不符合這兩個條件的年份不是閏年 例如2009、2100年,設(shè)year為

18、被檢測的年份。算法表示如下： S1：2000year S2：若year不能被4整除，則輸出year 的值和“不是閏年”。然后轉(zhuǎn)到S6 S3：若year能被4整除，不能被100整除，則輸出year的值和“是閏年”。然后轉(zhuǎn)到S6 S4：若year能被400整除，則輸出year的值和“是閏年” ，然后轉(zhuǎn)到S6 S5: 其他情況輸出year的值和“不是閏年” S6：year+1year S7：當year2500時，轉(zhuǎn)S2，否則停止,year不能被4整除,非閏年,year被4整除，但不能被100整除,閏年,year被100整除，又能被400整除,閏年,其他,非閏年,逐漸縮小判斷的范圍,例2.4 給出一個

19、大于或等于3的正整數(shù)，判斷它是不是一個素數(shù)。 所謂素數(shù)(prime)，是指除了1和該數(shù)本身之外，不能被其他任何整數(shù)整除的數(shù) 例如，13是素數(shù)，因為它不能被2，3，4，12整除。,判斷一個數(shù)n(n3)是否素數(shù)：將n作為被除數(shù)，將2到(n-1)各個整數(shù)先后作為除數(shù)，如果都不能被整除，則n為素數(shù) S1：輸入n的值 S2：i=2 （i作為除數(shù)） S3：n被i除，得余數(shù)r S4：如果r=0，表示n能被i整除，則輸出n“不是素數(shù)”，算法結(jié)束；否則執(zhí)行S5 S5：i+1i S6：如果in-1，返回S3；否則輸出n “是素數(shù)”，然后結(jié)束。,可改為n/2,2.3算法的特性,一個有效算法應(yīng)該具有以下特點： (1)

20、 有窮性。一個算法應(yīng)包含有限的操作步驟，而不能是無限的。 (2) 確定性。算法中的每一個步驟都應(yīng)當是確定的，而不應(yīng)當是含糊的、模棱兩可的。,一個有效算法應(yīng)該具有以下特點： (3) 有零個或多個輸入。所謂輸入是指在執(zhí)行算法時需要從外界取得必要的信息。 (4) 有一個或多個輸出。算法的目的是為了求解，“解” 就是輸出。 沒有輸出的算法是沒有意義的。 (5) 有效性。算法中的每一個步驟都應(yīng)當能有效地執(zhí)行，并得到確定的結(jié)果。,2.3算法的特性,2.3 算法的特性,對于一般最終用戶來說: 他們并不需要在處理每一個問題時都要自己設(shè)計算法和編寫程序 可以使用別人已設(shè)計好的現(xiàn)成算法和程序 只需根據(jù)已知算法的要

21、求給予必要的輸入，就能得到輸出的結(jié)果,輸入3個數(shù),黑箱子,3個數(shù)中最大數(shù),求3個數(shù)的最大數(shù),2.4怎樣表示一個算法,常用的方法有： 自然語言 傳統(tǒng)流程圖 結(jié)構(gòu)化流程圖 偽代碼 ,2.4.1 用自然語言表示算法,2.2節(jié)介紹的算法是用自然語言表示的 用自然語言表示通俗易懂，但文字冗長，容易出現(xiàn)歧義性 用自然語言描述包含分支和循環(huán)的算法，不很方便 除了很簡單的問題外，一般不用自然語言,2.4.2用流程圖表示算法,流程圖是用一些圖框來表示各種操作 用圖形表示算法，直觀形象，易于理解,起止框,輸入輸出框,處理框,判斷框,流程線,連接點,注釋框,x0,Y,N,一個入口,兩個出口,2.4.2用流程圖表示算

22、法,流程圖是用一些圖框來表示各種操作 用圖形表示算法，直觀形象，易于理解,起止框,輸入輸出框,處理框,判斷框,流程線,連接點,注釋框,位置不夠,防止交叉,例2.6 將例2.1的算法用流程圖表示。 求12345 如果需要將最后結(jié)果輸出:,1t,i5,開始,2i,t*it,i+1i,結(jié)束,N,Y,例2.6 將例2.1的算法用流程圖表示。 求12345 如果需要將最后結(jié)果輸出:,1t,輸出t,i5,開始,2i,t*it,i+1i,結(jié)束,N,Y,例2.7 例2.2的算法用流程圖表示。有50個學生，要求將成績在80分以上的學生的學號和成績輸出。,1i,i50,開始,i+1i,結(jié)束,N,Y,輸入ni、gi

23、,1i,開始,gi80,輸出ni、gi,i+1i,i50,N,Y,Y,N,如果包括輸入數(shù)據(jù)部分,1i,i50,開始,i+1i,結(jié)束,N,Y,輸入ni、gi,1i,gi80,輸出ni、gi,i+1i,i50,N,Y,Y,N,如果包括輸入數(shù)據(jù)部分,例2.8 例2.3判定閏年的算法用流程圖表示。判定20002500年中的每一年是否閏年，將結(jié)果輸出。,N,Y,N,Y,Y,N,Y,N,例2.9 例2.4判斷素數(shù)的算法用流程圖表示。對一個大于或等于3的正整數(shù)，判斷它是不是一個素數(shù)。,N,Y,2i,n%ir,i+1i,Y,N,通過以上幾個例子可以看出流程圖是表示算法的較好的工具 一個流程圖包括以下幾部分：

24、(1) 表示相應(yīng)操作的框 (2) 帶箭頭的流程線 (3) 框內(nèi)外必要的文字說明 流程線不要忘記畫箭頭，否則難以判定各框的執(zhí)行次序,2.4.3 三種基本結(jié)構(gòu)和改進的流程圖,1.傳統(tǒng)流程圖的弊端 傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對流程線的使用沒有嚴格限制 使用者可以毫不受限制地使流程隨意地轉(zhuǎn)來轉(zhuǎn)去，使人難以理解算法的邏輯,2.4.3 三種基本結(jié)構(gòu)和改進的流程圖,2.三種基本結(jié)構(gòu) (1) 順序結(jié)構(gòu),A,B,2.4.3 三種基本結(jié)構(gòu)和改進的流程圖,2.三種基本結(jié)構(gòu) (2) 選擇結(jié)構(gòu),A,B,Y,N,A,Y,N,2.4.3 三種基本結(jié)構(gòu)和改進的流程圖,2.三種基本結(jié)構(gòu) (3) 循環(huán)結(jié)構(gòu) 當型循環(huán)

25、結(jié)構(gòu),A,Y,N,Y,N,0 x,x+1x,輸出1,2,3,4,5,2.4.3 三種基本結(jié)構(gòu)和改進的流程圖,2.三種基本結(jié)構(gòu) (3) 循環(huán)結(jié)構(gòu) 直到型循環(huán)結(jié)構(gòu),A,Y,N,Y,N,0 x,x+1x,輸出1,2,3,4,5,以上三種基本結(jié)構(gòu)，有以下共同特點： (1) 只有一個入口 (2) 只有一個出口 一個判斷框有兩個出口 一個選擇結(jié)構(gòu)只有一個出口 (3) 結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到。也就是說，對每一個框來說，都應(yīng)當有一條從入口到出口的路徑通過它 (4) 結(jié)構(gòu)內(nèi)不存在“死循環(huán)”,由三種基本結(jié)構(gòu)派生出來的結(jié)構(gòu)：,A,N,Y,B,根據(jù)表達式p 的值進行選擇,A,B,p=p1,p=p2,M,N,

26、p=pm,p=pn,2.4.4 用N-S流程圖表示算法,N-S流程圖用以下的流程圖符號：,順序結(jié)構(gòu),選擇結(jié)構(gòu),循環(huán)結(jié)構(gòu) （當型）,循環(huán)結(jié)構(gòu)（直到型）,例2.10將例2.1的求5!算法用N-S圖表示。,直到i5,1t,輸出t,2i,t*it,i+1i,例2.11 將例2.2的算法用N-S圖表示。將50名學生中成績高于80分者的學號和成績輸出。,直到i50,1t,1i,i+1i,輸入ni、gi,i+1i,直到i50,gi80,否,是,輸出ni,gi,例2.12 將例2.3判定閏年的算法用N-S圖表示,直到y(tǒng)ear2500,2000year,year+1year,否,是,year%4為0,否,是,輸出 year 非閏年,year%100不為0,year%400為0,是,否,輸出year 非閏年,輸出year 閏年,輸出 year 閏年,例2.13 將例2.4判別素數(shù)的算法用N-S流程圖表示。 例2.9的流程圖不是由三種基本結(jié)構(gòu)組成的 循環(huán)有兩