第01章_程序設(shè)計基礎(chǔ)(提供給學(xué)生閱讀)

1、 河南科技大學(xué)河南科技大學(xué)計算機系計算機系第第1 1章章 緒論緒論計算機基礎(chǔ)知識第第2 2|87|87頁頁教學(xué)目標(biāo)教學(xué)目標(biāo)n了解計算機程序設(shè)計的一般過程n了解常見語言n掌握面向過程和面向?qū)ο蟪绦蛟O(shè)計思想第第3 3|87|87頁頁授授 課課 內(nèi)內(nèi) 容容 程序設(shè)計的一般過程 程序設(shè)計語言結(jié)構(gòu)化程序設(shè)計與面向?qū)ο蟪绦蛟O(shè)計 第第4 4|87|87頁頁問題的提出問題的提出n什么是程序設(shè)計？n為什么要要程序設(shè)計？n用什么工具進行程序設(shè)計？n第第5 5|87|87頁頁“程序設(shè)計是具有一種知識背景的程序設(shè)計是具有一種知識背景的人為具有另一種知識背景的人進人為具有另一種知識背景的人進行的創(chuàng)造性勞動行的創(chuàng)造性勞動

2、” 。程序設(shè)計是一種創(chuàng)造性的勞動程序設(shè)計是一種創(chuàng)造性的勞動第第6 6|87|87頁頁設(shè)計過程是把實用知識影射到計算知識。設(shè)計是一個影射設(shè)計是一個影射 功能功能 用戶操作用戶操作 約束約束 例外例外 器件器件 組織 結(jié)構(gòu) 算法 資源 數(shù)據(jù)實用知識計算知識第第7 7|87|87頁頁 “一個設(shè)計者能對著復(fù)雜的設(shè)計沉思幾月。然后突然間簡單、雅致而又漂亮的解決辦法冒出。當(dāng)這發(fā)生在你身上時，感覺好像是上帝正在說話!也許真的是這樣?！?Leo Leo FrankowskiFrankowski in in The Cross-Time EngineerThe Cross-Time Engineer關(guān)于設(shè)計的論

3、述一關(guān)于設(shè)計的論述一第第8 8|87|87頁頁 “好的設(shè)計者應(yīng)具備深厚的應(yīng)用領(lǐng)域知識好的設(shè)計者應(yīng)具備深厚的應(yīng)用領(lǐng)域知識?！?Curtis lawCurtis law關(guān)于設(shè)計的論述二關(guān)于設(shè)計的論述二第第9 9|87|87頁頁“層次結(jié)構(gòu)減少復(fù)雜度層次結(jié)構(gòu)減少復(fù)雜度?！?Simons lawSimons law關(guān)于設(shè)計的論述三第第1010|87|87頁頁模塊化處理模塊化處理n模塊化就是把程序劃分為若干個模塊，而每個模塊完成一個子功能，把這些模塊匯總起來構(gòu)成一個有機整體，即可完成指定的功能。n模塊化的目的是為了降低軟件復(fù)雜度，使軟件設(shè)計，調(diào)試和維護等操作變得簡易。第第1111|87|87頁頁層次結(jié)構(gòu)、

4、模塊化舉例層次結(jié)構(gòu)、模塊化舉例n這是一個銷售管理信息系統(tǒng)。首先畫出“樹根”，接著畫出第二層的“支干”，然后再畫出第三層的“支干”，最后，畫出“樹葉”（實質(zhì)性的數(shù)據(jù)結(jié)構(gòu)）。銷售銷售MISMIS銷售銷售MISMIS經(jīng)營經(jīng)營庫存庫存財務(wù)財務(wù)1）2）3）銷售銷售MISMIS經(jīng)營經(jīng)營庫存庫存財務(wù)財務(wù)市場分析市場分析統(tǒng)計分析統(tǒng)計分析客戶檔案客戶檔案盤點結(jié)存盤點結(jié)存訂貨管理訂貨管理工資核算工資核算采購計劃采購計劃工資核算工資核算成本核算成本核算第第1212|87|87頁頁 “讀一本魔術(shù)原理的書，如果你不經(jīng)?？捶饷娴脑?，你會以為在看的是軟件設(shè)計的書?！?Bruce Tognazzini 關(guān)于軟件設(shè)計的論述第第

5、1313|87|87頁頁“有兩種方法來設(shè)計一個軟件。第一種方法是設(shè)計非常簡單的軟件以至于沒有明顯的不足。另一種方法是設(shè)計非常復(fù)雜的軟件也沒有明顯的不足?！?C.A.R. Hoare C.A.R. Hoare 軟件設(shè)計的妙語第第1414|87|87頁頁程序設(shè)計的一般過程程序設(shè)計的一般過程 n為什么要進行程序設(shè)計 n什么時候需要程序設(shè)計n怎樣進行程序設(shè)計n程序設(shè)計的一般過程第第1515|87|87頁頁為什么要進行程序設(shè)計為什么要進行程序設(shè)計n因為，在面臨的應(yīng)用領(lǐng)域中沒有合適的、可使用的應(yīng)用軟件。n種地（或加工零件、包餃子）與程序設(shè)計n餃子的各種吃法n評估：n預(yù)期需求n可得到的工具n自身能力n在計算

6、機的各個技術(shù)應(yīng)用中，應(yīng)清楚自身所處的層次、所需的技能第第1616|87|87頁頁用什么進行程序設(shè)計用什么進行程序設(shè)計n可用的工具n通用應(yīng)用軟件 (Office)n文字處理: Wordn表格處理: EXCEL n科學(xué)計算 MATLAB . n程序設(shè)計語言 nmicrosoft:Visual C+、Visual BasicnBorland:Delphi、C+BuildernSun:javan沒有合適的開發(fā)工具怎么辦？第第1717|87|87頁頁一、程序設(shè)計的一般過程一、程序設(shè)計的一般過程n計算機可以做任何事情；只要能把實際問題抽象、制作為計算機可求解的程序。n計算機求解問題的步驟：分析抽象模型求解

7、命令編程調(diào)試程序?qū)嶋H 問題 求解 編制 問題問題 模型 算法 程序 實現(xiàn)第第1818|87|87頁頁程序設(shè)計的一般過程程序設(shè)計的一般過程n問題定義 n算法設(shè)計 n程序編制 n調(diào)試運行 n文檔 第第1919|87|87頁頁問題定義問題定義問題一：n給定兩個正整數(shù)p和q, 求其最大公因數(shù)。問題二：n統(tǒng)計大學(xué)中一個班級的學(xué)生的考試成績，并選出優(yōu)秀學(xué)生。 n多少科目的成績？n優(yōu)秀的定義（總分？平均分？第一名？前五名？）n數(shù)據(jù)如何錄入？如何輸出？n這是初學(xué)者認(rèn)為最簡單而在實際工程中最難的工作。在軟件工程中被稱作“需求分析”。第第2020|87|87頁頁算法設(shè)計算法設(shè)計 n前因后果：n問題定義確定了未來程

8、序的輸入、處理、輸出（IPO,即Input,Process,Output）；n算法(Algorithm)是對解決問題步驟的描述；n算法不能被計算機理解、執(zhí)行。 第第2121|87|87頁頁算法示例（一）算法示例（一）步驟1：輸入全部學(xué)生姓名、學(xué)號、英語成績、計算機基礎(chǔ)成績；步驟2：對各個學(xué)生成績求合計；步驟3：按合計對學(xué)生進行排序；步驟4：取排序的學(xué)生列表中第一個學(xué)生；步驟5：該學(xué)生有不及格嗎？沒有，則打印姓名并結(jié)束；有不及格，則取下一個學(xué)生并重復(fù)步驟5 。第第2222|87|87頁頁算法示例（二）算法示例（二）n步驟1：輸入一個學(xué)生的姓名、學(xué)號、英語成績、計算機基礎(chǔ)成績；n步驟2：該學(xué)生有不

9、及格嗎？有則轉(zhuǎn)步驟1n步驟3：該合計大于以前學(xué)生的合計嗎？大于則記錄姓名、學(xué)號、合計成績；n步驟4：重復(fù)步驟1直到輸入全部學(xué)生成績 n步驟5：打印姓名、學(xué)號、合計成績 第第2323|87|87頁頁算法的表示算法的表示n偽代碼（Pseudo code） SUM = 0FOR I=1 TO N 循環(huán)求累加和 SUM = SUM+I輸出 SUMn流程圖(Flow chat) 第第2424|87|87頁頁算法的流程圖表示算法的流程圖表示開始或結(jié)束輸入或輸出判斷計算連接線開始輸入姓名1、學(xué)號1、英語成績1、輸入姓名2、學(xué)號2、英語成績2、求合計1求合計2合計1合計2?英語成績10 并且計算機基礎(chǔ)成績10

10、輸出姓名1、合計1是結(jié)束英語成績20 并且計算機基礎(chǔ)成績20輸出姓名2、合計2否否否第第2525|87|87頁頁的計算問題的計算問題n計算方法：121.753239145116121753nxxxxxarctgxarctgarctgnnMachin公式.917151311(1).73523152313112(2)(3) 044499263901103!4!4229801nnnnnnRamanujan公式(4) 033640320!3!13591409545140134!610005426880nnnnnnChudnovsky公式(5)第第2626|87|87頁頁理論分析理論分析n公式計算量小，

11、程序編制簡單，收斂很慢；n公式計算量不大，收斂較快，程序編制較簡單；nMachin公式每計算一項可以得到1.4位的十進制精度，收斂較快，容易在計算機上編程實現(xiàn)；nRamanujan公式和Chudnovsky公式收斂更快，要使用FFT(Fast Fourier Transform)算法，將兩個大數(shù)的乘除運算時間由O(n2)縮短為O(nlogn)，程序?qū)崿F(xiàn)比較復(fù)雜。第第2727|87|87頁頁編程實現(xiàn)：編程實現(xiàn)：n計算方法（1）int s = 1;double n = 1.0, t = 1.0, pi = 0.0;while(fabs(t)=1e-10) pi = pi+t; n = n+2; s

12、 = -s; t = s/n;.917151311第第2828|87|87頁頁程序編制程序編制n程序語言的基本語句sum1 := en1 + com1 這是Pascal的語句sum1 = en1 + com1; 這是C+的語句n程序的執(zhí)行起始點 n子程序（Subprogram） 模塊化示例 將一個大程序分成若干小程序塊，每一個小程序塊（子程序）完成相對單一的功能，由一個主程序調(diào)用別的子程序，最終形成一個樹狀結(jié)構(gòu)，這樣就將一個龐大的功能拆分成若干相對簡單的功能了（像積木塊搭房子一樣）。 n程序的執(zhí)行順序 第第2929|87|87頁頁程序編制程序編制C+C+程序代碼程序代碼 #include vo

13、id main() char name120,name220; /姓名姓名 int num1,num2; /學(xué)號學(xué)號 double en1,en2,com1,com2; /英語和計算機基礎(chǔ)成績英語和計算機基礎(chǔ)成績 int sum1,sum2; /合計合計 / = 以上為變量定義以上為變量定義= cout “請輸入學(xué)生請輸入學(xué)生1姓名、學(xué)號、英語成績、計算機基礎(chǔ)成績姓名、學(xué)號、英語成績、計算機基礎(chǔ)成績” name1num1en1com1; sum1=en1+com1; /計算合計計算合計 cout “請輸入學(xué)生請輸入學(xué)生2姓名、學(xué)號、英語成績、計算機基礎(chǔ)成績姓名、學(xué)號、英語成績、計算機基礎(chǔ)成績”

14、 name2num2en2com2; sum2=en2+com2; /計算合計計算合計 if(sum1sum2) if(en160 & com1 60) cout “第一名：第一名：”name160 & com2 60) cout “第一名：第一名：”name2 sum2 THEN IF en1 60 AND com1 60 THEN PRINT name1,sum1 END IF ELSE IF en2 60 AND com2 60 THEN PRINT name2,sum2 END IFEND IFEND程序編制程序編制BasicBasic程序代碼程序代碼變量名后加變量名后

15、加$表示存儲文表示存儲文本本,不加不加$表示存儲數(shù)值表示存儲數(shù)值用用REM開頭表示注釋信息開頭表示注釋信息THENENDIF相當(dāng)于相當(dāng)于C+的的 符號符號第第3131|87|87頁頁程序編制程序編制 Subprogram #include iostream.h#include int MyMax(int a,intint MyMax(int a,int b) b) int tmp int tmp; ; if(ab) tmp if(ab) tmp=a;=a; else tmp else tmp = b; = b; return tmp return tmp; ; void main()void

16、main() int int i,j; i,j; cout cout “ “請輸入兩個整數(shù)：請輸入兩個整數(shù)：” ” endl i j ; i j ; coutcout“兩數(shù)中較大者為兩數(shù)中較大者為：” ” MyMax(i,j)endl MyMax(i,j)endl; ; 這是一個函數(shù)，找出兩這是一個函數(shù)，找出兩個數(shù)中較大者個數(shù)中較大者在在main函數(shù)中調(diào)用函數(shù)中調(diào)用MyMax函數(shù)函數(shù)第第3232|87|87頁頁程序的執(zhí)行順序程序的執(zhí)行順序 void main() int i,j; cout “請輸入兩個整數(shù)：請輸入兩個整數(shù)：” i j ; cout “兩數(shù)中較大者為：兩數(shù)中較大者為：” MyM

17、ax(i,j) b) tmp=a;else tmp = b;return tmp;2按書寫順序一按書寫順序一條條執(zhí)行語句條條執(zhí)行語句1.程序從這里開始執(zhí)行程序從這里開始執(zhí)行4遇見遇見return語語句，結(jié)束子程序，句，結(jié)束子程序，回到原程序繼續(xù)執(zhí)回到原程序繼續(xù)執(zhí)行行.3遇見子程遇見子程序，就轉(zhuǎn)到子序，就轉(zhuǎn)到子程序中執(zhí)行程序中執(zhí)行第第3333|87|87頁頁程序編制程序編制n要點n如何用語句表達思想（算法）？ n（初級）了解語句、語法n（高級）熟悉語言提供的功能、你需要做的工作 不同語言提供的功能、性能有較大差距n如何組織程序代碼 n開始點n執(zhí)行過程（子程序拆分、調(diào)用）n結(jié)束點第第3434|87

18、|87頁頁調(diào)試運行調(diào)試運行 nIDE環(huán)境n語法錯誤n邏輯錯誤第第3535|87|87頁頁調(diào)試程序的調(diào)試程序的煩惱煩惱？ 程序員約翰在調(diào)試程序過程中遇到了麻煩程序員約翰在調(diào)試程序過程中遇到了麻煩第第3636|87|87頁頁編譯、調(diào)試程序的例子編譯、調(diào)試程序的例子第第3737|87|87頁頁調(diào)試運行調(diào)試運行n邏輯錯誤 求a和b中的最大數(shù) if（a=b） max=a; else max = a; if（ab） max=a; max = b; if（a=b） max=a; else max = b;OK？第第3838|87|87頁頁計算機語言問題的提出計算機語言問題的提出n人識別高級語言，計算機識別機

19、器語言，人和計算機之間如何交流？n一個中國經(jīng)理和一個德國商人談生意，需要一個翻譯，才能進行語言溝通。n與不同國家的人進行交流需要不同的語言翻譯。在不同的場合，即使是某種語言，也需要不同的翻譯。例如，計算機、醫(yī)學(xué)不同領(lǐng)域n計算機語言也面臨類似問題第第3939|87|87頁頁二、程序設(shè)計語言二、程序設(shè)計語言n語言的大類 n機器語言 n匯編語言 n高級語言 n程序的編譯與解釋 n常見語言介紹nProlog/LispnC,C+,C#,JAVA,Delphi,VB,AdanScript語言第第4040|87|87頁頁 語言名稱 適用范圍 BASIC 教學(xué)和小型應(yīng)用程序的開發(fā) FORTRAN 科學(xué)與工程計

20、算程序的開發(fā) PASCAL 專業(yè)教學(xué)與應(yīng)用程序的開發(fā) PROLOG 人工智能程序的開發(fā) COBOL 商業(yè)與管理應(yīng)用程序的開發(fā) C 中小型系統(tǒng)程序的開發(fā) C+ 面向?qū)ο蟪绦虻拈_發(fā) LISP 人工智能程序的開發(fā) JAVA 基于Web的應(yīng)用程序開發(fā) ATA 美國軍方用的防御體系開發(fā) VC、VB 可視化、面向?qū)ο缶幊陶Z言常用高級語言第第4141|87|87頁頁語言的大類n機器語言是計算機能直接執(zhí)行的二進制形式。對人來說既難理解又難掌握，只在早期高級語言還沒出現(xiàn)時使用過。n匯編語言用助記碼與符號地址來代替機器指令中的操作碼與操作數(shù)n編譯語言和解釋語言第第4242|87|87頁頁2.2.編譯器建立命令編譯

21、器建立命令字、數(shù)據(jù)、操作符字、數(shù)據(jù)、操作符的縮寫（標(biāo)簽）。的縮寫（標(biāo)簽）。3.3.編譯器分析標(biāo)編譯器分析標(biāo)簽，將標(biāo)簽安排簽，將標(biāo)簽安排成機器語言的格成機器語言的格式。式。4.4.編譯器分析語編譯器分析語法，產(chǎn)生機器語法，產(chǎn)生機器語言指令。言指令。CountCount Num1=5 Num1=5 num2=4 num2=4VarVar Total_integer Total_integerbeginbegin1.1.編譯器掃描源代編譯器掃描源代碼中它理解的命碼中它理解的命令字、數(shù)據(jù)、操令字、數(shù)據(jù)、操作符。放棄注釋作符。放棄注釋語句。語句。Compiled編譯編譯第第4343|87|87頁頁Int

22、erpreted Interpreted 解釋解釋1.1.解釋器是一種計算解釋器是一種計算機程序，是程序語言機程序，是程序語言環(huán)境的一部分。解釋環(huán)境的一部分。解釋器檢查程序中每一個器檢查程序中每一個命令字。命令字。2.2.解釋器在語言的有解釋器在語言的有效命令表中查找該命效命令表中查找該命令字。令字。3.3.如果該命令在表中如果該命令在表中，解釋器讀取命令的，解釋器讀取命令的其它部分，以確定該其它部分，以確定該命令符合語法規(guī)定。命令符合語法規(guī)定。4.4.如果語法正確，解如果語法正確，解釋器將該命令轉(zhuǎn)換成釋器將該命令轉(zhuǎn)換成機器語言，并將指令機器語言，并將指令送往處理器。送往處理器。第第4444|

23、87|87頁頁三、結(jié)構(gòu)化程序設(shè)計與面向?qū)ο蟪绦蛟O(shè)計三、結(jié)構(gòu)化程序設(shè)計與面向?qū)ο蟪绦蛟O(shè)計n基本程序控制結(jié)構(gòu)n結(jié)構(gòu)化程序設(shè)計思想n面向?qū)ο蟪绦蛟O(shè)計第第4545|87|87頁頁結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法 n“軟件危機”-結(jié)構(gòu)化程序設(shè)計 n基本觀點： n程序設(shè)計的目標(biāo)不應(yīng)再集中于如何充分發(fā)揮硬件的效率方面，新的程序設(shè)計方法應(yīng)以能設(shè)計出結(jié)構(gòu)清晰、可讀性強、易于分工合作編寫和調(diào)試的程序。 n結(jié)構(gòu)化設(shè)計方法是以模塊化設(shè)計為中心。第第4646|87|87頁頁模塊化程序結(jié)構(gòu) n模塊化 模塊化示例n就是把程序劃分為若干個部分，每個部分獨立存放、完成一個特定的功能。其目的是降低程序的復(fù)雜度，使設(shè)計出來的程

24、序便于閱讀、調(diào)試和維護。 n一個模塊可以是一條語句、一段程序、一個函數(shù)等。 n基本特征是其僅有一個入口和一個出口 n模塊相互獨立，內(nèi)聚性很強，一個模塊完成一個功能。 第第4747|87|87頁頁三種基本程序結(jié)構(gòu)三種基本程序結(jié)構(gòu) n按照結(jié)構(gòu)化程序設(shè)計的觀點, 任何算法功能都可以通過由程序模塊組成的三種基本程序結(jié)構(gòu)的組合: n順序結(jié)構(gòu)：程序是按程序語句或模塊在執(zhí)行流中的順序逐個執(zhí)行。 n選擇結(jié)構(gòu)：程序是按設(shè)定的條件實現(xiàn)程序執(zhí)行流的多路分支。 n循環(huán)結(jié)構(gòu)：程序是按給定的條件重復(fù)地執(zhí)行指定的程序段或模塊。 n結(jié)論：理論上已經(jīng)證明，用三種基本程序結(jié)構(gòu)可以實現(xiàn)任何復(fù)雜的算法。第第4848|87|87頁頁順

25、序結(jié)構(gòu)順序結(jié)構(gòu)n順序結(jié)構(gòu)語句包括：n說明語句 int a，b，c；n賦值語句 sum=a+b；nI/O 語句 printf（“Sum=%d、n”，sum）；n子函數(shù)調(diào)用語句 call multi（a，b）n返回語句 return （a+b）第第4949|87|87頁頁選擇結(jié)構(gòu)（之一）選擇結(jié)構(gòu)（之一）n一路分支 語句格式： if （表達式） 語句序列n兩路分支 語句格式： if （表達式） 語句序列1 else 語句序列2條件？條件？成立成立不成立不成立語句序列語句序列條件？條件？語句序列語句序列 1成立成立不成立不成立語句序列語句序列 2語句序列可以是一個語句，也可以是復(fù)合語句結(jié)構(gòu)。示例示例示

26、例示例第第5050|87|87頁頁選擇結(jié)構(gòu)之二選擇結(jié)構(gòu)之二n多路（開關(guān)）選擇語句語句格式： switch（整數(shù)表達式） case 數(shù)值1： 語句序列1； . case 數(shù)值n： 語句序列n； default : 語句序列n+1； 計算整型表達式計算整型表達式值值 = ？語句語句序列序列1.語句語句序列序列2語句語句序列序列n示例示例第第5151|87|87頁頁循環(huán)結(jié)構(gòu)（之一）循環(huán)結(jié)構(gòu)（之一）n當(dāng)型循環(huán) 語句格式： while （表達式） 語句序列 n直到型循環(huán) 語句格式： do 語句序列 while（表達式）;循環(huán)體循環(huán)體條件？條件？語句序列語句序列成立成立不成立不成立語句序列語句序列不成立不

27、成立成立成立條件？條件？示例示例示例示例第第5252|87|87頁頁舉例：求舉例：求11001100的累加和的累加和n int i=1，sum=0； while（i =100) sum=sum+i; i=i+1; i=100？sum=sum+i; i=i+1;Ysum=0，i=0;N N第第5353|87|87頁頁循環(huán)結(jié)構(gòu)（之二）循環(huán)結(jié)構(gòu)（之二）nfor 循環(huán)結(jié)構(gòu) 語句格式： for ( e1 ; e2 ; e3 ) 語句序列 ne1、e2、e3是三個表達式，分別表示循環(huán)變量的初值、終值和增量。1、循環(huán)從e1值開始2、判別e2是否為真3、若真，執(zhí)行語句序列，并e1加e3，轉(zhuǎn)2；4、若假，退出循

28、環(huán)。 計算計算 e1e2 為真？為真？執(zhí)行語句序列執(zhí)行語句序列計算計算 e3e1= e1+e3是是否否第第5454|87|87頁頁VC+語言的控制結(jié)構(gòu)n順序n選擇（分支）nif ( ) else ;nswitch() case ;default:;n循環(huán)nwhile();nfor(.);ndo. while(.);n出口nbreak; continue;第第5555|87|87頁頁結(jié)構(gòu)化程序設(shè)計思想n結(jié)構(gòu)化程序設(shè)計支持“自頂向下, 逐步求精”的程序設(shè)計方法。 n“自頂向下” n是將復(fù)雜、大的問題劃分為小問題，找出問題的關(guān)鍵、重點所在，然后用精確的思維定性、定量地去描述問題。 n“逐步求精” n

29、是將現(xiàn)實世界的問題經(jīng)抽象轉(zhuǎn)化為邏輯空間或求解空間的問題。復(fù)雜問題經(jīng)抽象化處理變?yōu)橄鄬Ρ容^簡單的問題。經(jīng)若干步抽象（精化）處理，最后到求解域中只是比較簡單的編程問題。 第第5656|87|87頁頁例例7-3 驗證驗證“哥德巴赫猜想哥德巴赫猜想”n“哥德巴赫猜想”是數(shù)論中的一個著名難題，200多年來無數(shù)數(shù)學(xué)家為其嘔心瀝血，卻始終無人能夠證明或偽證這個猜想。n“哥德巴赫猜想”表述為：任何一個大于等于4的偶數(shù)均可以表示為兩個素數(shù)之和。n1742年法國數(shù)學(xué)愛好者哥德巴赫在給著名數(shù)學(xué)家歐拉的信中提出“哥德巴赫猜想”問題。第第5757|87|87頁頁問題的分解問題的分解n求解第一步 提出問題： 驗證哥德巴赫

30、猜想。 驗證哥德巴赫猜想驗證哥德巴赫猜想第第5858|87|87頁頁問題的分解（續(xù)一）問題的分解（續(xù)一）n第二步 設(shè)一上限數(shù)M，驗證從4到M的所有偶數(shù)是否能被分解為兩個素數(shù)之和。1. 定義一個變量X，初值為4。2. 每次令其加2，并驗證X能否被分解為兩個素數(shù)之和，直到X不小于M為止。X = 4X M ?驗證驗證x是否能被分解是否能被分解為兩個素數(shù)之和為兩個素數(shù)之和X = X +2否否是是第第5959|87|87頁頁問題的分解（續(xù)二）問題的分解（續(xù)二）n第三步 如何驗證X是否能被分解為兩個素數(shù)之和。1.從P=2開始；2.判別X-P是否仍為素數(shù)：3.若是，打印該偶數(shù)的分解式。4.否則，換更大的素數(shù)

31、，再繼續(xù)執(zhí)行2.。如此循環(huán)，直到用于檢測的素數(shù)大X/2且X 與其之差仍不是素數(shù)，則打印“哥德巴赫猜想”不成立。 P = 2P= x / 2 ?處理哥德巴赫猜想處理哥德巴赫猜想不成立的情況不成立的情況打印出打印出X的的分解情況分解情況是是否否第第6060|87|87頁頁問題的分解（續(xù)三）問題的分解（續(xù)三）n第四步 生成下一個素數(shù)。 當(dāng)前素數(shù)P加1 判別P是否是素數(shù)； 若是素數(shù)，返回P； 否則，P加1，繼續(xù)執(zhí)行。 P = P + 1是素數(shù)？是素數(shù)？P = P + 1否否返回素數(shù)返回素數(shù) P第第6161|87|87頁頁問題的分解（續(xù)四）問題的分解（續(xù)四）n經(jīng)過四步分解精化，將“驗證哥德巴赫猜想”這個

32、命題已經(jīng)分解為計算機可以求解的數(shù)學(xué)模型了。n剩下的問題就是編程求解了。如何編程是程序設(shè)計課程要解決的問題。第第6262|87|87頁頁哥德巴赫猜想算法分析1) 用“篩選”法生成素數(shù)表PrimeListM。先在素數(shù)表中產(chǎn)生到-1的所有自然數(shù)，然后將已確定的所有素數(shù)的倍數(shù)置(求模取余為）。 2，3，5，7，11，13，17，19，23，29，31.2) 這樣一來，素數(shù)表中有許多0，為找下一個素數(shù)，要跳過這些0。3) 分解0到M-1之間的所有偶數(shù)；循環(huán)(x M) x初值取4 先取素數(shù)P=2,判別 若PrimeListx-p等于0，說明分解不成功，p取素數(shù)表中下一個素數(shù)；再執(zhí)行若PrimeListx-

33、p不等于0，分解成功，打印分解式x = x + 2，繼續(xù)執(zhí)行 ，檢查下一個偶數(shù)。第第6363|87|87頁頁程序邏輯功能框圖 建立素數(shù)表建立素數(shù)表reatPrimeList（PrimeList）X M ？P =M/2？P = 2x = x +2是是否否是是否否是是否否x = 4打印該偶數(shù)分解式打印該偶數(shù)分解式顯示顯示“哥德巴赫猜想錯哥德巴赫猜想錯“第第6464|87|87頁頁程序模塊結(jié)構(gòu) 主函數(shù)主函數(shù)main（）（）子函數(shù)生成素數(shù)表子函數(shù)生成素數(shù)表CreatPrimeList（ ）子函數(shù)求下一個素數(shù)子函數(shù)求下一個素數(shù)NextPrimeNomber（）（）子函數(shù)求下一個素數(shù)子函數(shù)求下一個素數(shù)Ne

34、xtPrimeNomber（）（）第第6565|87|87頁頁程序（生成素數(shù)表子函數(shù)）#include #define M 31 /* 定義驗證范圍 */void CreatPrimeList(int PrimeList) int i, j; for(i=0; iM; i = i+1) /* 生成素數(shù)表，置初值 */ PrimeListi = i; i = 2; /* i 取初值 2 */ while( i M / 2 )/* A能分解為兩個因子相乘的話,其中一個因子 */ /* 必小于或等于INT（ sqrt（ A） ）。*/ for(j=i+1; jM; j=j+1)/* 將表中各素數(shù)的倍

35、數(shù)置0 */ if(PrimeListj!=0 & PrimeListj%PrimeListi=0) PrimeListj = 0; i = NextPrimeNumber（i，PrimeList）；/*取下一個素數(shù) */ 第第6666|87|87頁頁求下一個素數(shù)子函數(shù)/*- 函數(shù) NextPrimeNumber: 求下一個素數(shù) -*/ int NextPrimeNumber(int p, int PrimeList ) p = p+1; while(PrimeListp=0) p = p+1; return PrimeListp; 第第6767|87|87頁頁主函數(shù) main() i

36、nt PrimeListM; int x, p; CreatPrimeList(PrimeList); /*生成素數(shù)表 */ x = 4; /* 從4到 M 開始驗證 */ while(x=M) p = PrimeList2; /* 第1個素數(shù)是2 */ /* 驗證偶數(shù)減去一個素數(shù)后的余數(shù)是否仍為素數(shù) */ while(p=M/2) /* 找到一個不能分解為兩個素數(shù)和的偶數(shù) */ printf(Great discovery: Goldbahe is wrong!n); else /* PrimeListx-p0 分解成功 */ printf(The even number %d = %d +

37、 %dn,x,p,x-p); /* 驗證下一個偶數(shù) */ x = x+2;源代碼第第6868|87|87頁頁面向?qū)ο蟪绦蛟O(shè)計面向?qū)ο蟪绦蛟O(shè)計n基本思想n基本過程n主要特點第第6969|87|87頁頁面向?qū)ο蟮幕靖拍蠲嫦驅(qū)ο蟮幕靖拍頽“面向?qū)ο蟆昂喎Q為“OO”。這是目前計算機業(yè)界使用的高頻詞?！癘O”代表著一種新的思維方式，代表著一種新的程序設(shè)計方法的潮流。n什么是OO方法？什么是OOP？n為什么要選擇OO方法？第第7070|87|87頁頁面向?qū)ο蟪绦蛟O(shè)計基本思想面向?qū)ο蟪绦蛟O(shè)計基本思想n面向過程的程序設(shè)計(Structure Programming)n以功能為中心,采用函數(shù)來描述(動詞)n

38、傳統(tǒng)的程序設(shè)計方法，出發(fā)點是“怎樣做（How）？”。n面向?qū)ο蟪绦蛟O(shè)計(OOP)n面向?qū)ο蟪绦蛟O(shè)計方法認(rèn)為，客觀世界是由各種各樣的實體組成的，這些實體就是面向?qū)ο蠓椒ㄖ械膶ο蟆?n消息是向某對象請求服務(wù)的一種表達方式 n對象之間的交互通過發(fā)送消息來實現(xiàn)。 n消息包括:目標(biāo)對象 ,請求的方法 ,參數(shù)第第7171|87|87頁頁什么是面向?qū)ο蠓椒ㄊ裁词敲嫦驅(qū)ο蠓椒╪面向?qū)ο螅∣O）方法的出發(fā)點是：“是什么（What）?”。n現(xiàn)實世界是由物質(zhì)組成的，人認(rèn)識事物的規(guī)律：首先是認(rèn)識問題域（Domain），它“是什么？”,再去認(rèn)識事物的本質(zhì)。n“對象”表現(xiàn)現(xiàn)實世界中的某個具體的事物。第第7272|87|8

39、7頁頁 傳統(tǒng)程序設(shè)計方法存在的問題傳統(tǒng)程序設(shè)計方法存在的問題n生產(chǎn)率提高的幅度遠不能滿足需要n軟件重用程度很低n軟件維護困難n軟件不能真正滿足用戶的需要第第7373|87|87頁頁 生產(chǎn)率提高幅度遠不能滿足需要生產(chǎn)率提高幅度遠不能滿足需要u生命周期方法學(xué)強調(diào)需求分析的重要性，強調(diào)每個階段結(jié)束之前必須進行嚴(yán)格的評審和質(zhì)量把關(guān)。這種“按部就班”式的開發(fā)方法效率不高。u據(jù)統(tǒng)計資料表明：u從上個世紀(jì)的30中，美國軟件生產(chǎn)率翻了兩翻u但社會對軟件需求每年以兩位數(shù)字的百分比增長u軟件的開發(fā)，已成為影響計算機應(yīng)用的巨大桎梏和瓶頸。第第7474|87|87頁頁軟件重用程度很低軟件重用程度很低u“重用”也稱“再

40、用”或“復(fù)用”。顯然，軟件重用是節(jié)約人力，提高軟件生產(chǎn)率的重要途徑。u傳統(tǒng)的程序設(shè)計方法沒能很好地解決軟件重用問題。例如,建立標(biāo)準(zhǔn)函數(shù)庫和子程序庫是一種低級的可重用的嘗試。僅僅限于數(shù)學(xué)和統(tǒng)計學(xué)方面。u對于傳統(tǒng)程序設(shè)計技術(shù)而言，思維成果的可重用性很差。第第7575|87|87頁頁軟件維護困難軟件維護困難u按生命周期方法學(xué)開發(fā)出的軟件，維護成本很高，據(jù)統(tǒng)計數(shù)據(jù)表明，軟件維護的生產(chǎn)率比軟件開發(fā)的生產(chǎn)率低幾十倍。u80年代，美國一年花費的軟件維護費用高達300多億美元。u90年代，軟件維護費用占系統(tǒng)研制、開發(fā)總費用的70%80%。第第7676|87|87頁頁軟件不能真正滿足用戶的需要軟件不能真正滿足用

41、戶的需要n在美國，實踐表明，開發(fā)出的系統(tǒng)中：符合用戶需要并順利投入使用的系統(tǒng)僅占總數(shù)的1/4；中途夭折的系統(tǒng)占1/4；將近1/2的系統(tǒng)，雖然完成了開發(fā)過程，但并未被用戶采用或并未被長期使用。n還表現(xiàn)在：n開發(fā)出的軟件系統(tǒng)與用戶預(yù)期的系統(tǒng)不一致，不能滿足用戶的需要。n所開發(fā)出的系統(tǒng)不能適應(yīng)用戶經(jīng)常變化的情況，系統(tǒng)的穩(wěn)定性和可擴充性不能滿足要求。第第7777|87|87頁頁設(shè)計方法主觀隨意性很大設(shè)計方法主觀隨意性很大n結(jié)構(gòu)化方法采用“自頂向下，逐步求精”進行分解。但因開發(fā)人員的經(jīng)驗、知識背景對問題認(rèn)識的不同，而造成分解的隨意性。n即使是對同一個系統(tǒng)，不同的人可能分解出不同的軟件結(jié)構(gòu)。第第7878|

42、87|87頁頁n更加自然n當(dāng)系統(tǒng)不斷地演化時，內(nèi)部的功能會變化，但是對象本質(zhì)不變n面向?qū)ο蟮南到y(tǒng)更容易維護n面向?qū)ο蠓治龇◤娬{(diào)對象間定義良好的界面為什么選擇面向?qū)ο蠓治龇?？第?979|87|87頁頁OOOO方法的主要優(yōu)點方法的主要優(yōu)點n與人類習(xí)慣的思維方法一致n穩(wěn)定性好n可重用性好n可維護性好第第8080|87|87頁頁與人類習(xí)慣的思維方法一致與人類習(xí)慣的思維方法一致n人的認(rèn)識過程是從一般到特殊的漸進思維過程，是從“是什么?”開始，認(rèn)識事物及其本質(zhì)規(guī)律，主觀隨意性受到限制。n而傳統(tǒng)方法是從“怎樣做？”開始，到“做什么？”，反認(rèn)識規(guī)律而動，主觀隨意性太多。第第8181|87|87頁頁穩(wěn)定性好穩(wěn)

43、定性好n傳統(tǒng)方法以“過程為中心”，完全基于功能的分析和分解。當(dāng)功能需求發(fā)生變化時，將引起對軟件結(jié)構(gòu)整體的修改，這樣的系統(tǒng)是不穩(wěn)定的。nOO方法以“對象為中心”，它是以對象模擬問題領(lǐng)域中的實體，以對象間的聯(lián)系描述實體間的聯(lián)系。在分析、研究對象及其屬性的過程中根據(jù)其內(nèi)在的規(guī)律建立求解模型。n基于這種方法建立的軟件系統(tǒng)，不管功能需求如何變化，其內(nèi)在規(guī)律不變，因而不會引起軟件系統(tǒng)結(jié)構(gòu)的整體變化。因此是穩(wěn)定的。第第8282|87|87頁頁可重用性好可重用性好nOO方法中類的繼承性是一種代碼重用的有效途徑。開發(fā)者在設(shè)計軟件的過程中，將一些精心設(shè)計、測試過的代碼不斷加入到已有的類庫中。而類庫是可供共享的代碼庫。n因此用OOP開發(fā)的軟件具有較好的可重用性。第第8383|87|87頁頁可維護性好可維護性好n穩(wěn)定性較好 局部修改，不影響大局，錯誤不會傳播；n易修改