計算機基礎(chǔ)第6章程序設(shè)計基礎(chǔ)ppt課件

1、計算機基礎(chǔ),第一章 概述 第二章 數(shù)據(jù)在計算機內(nèi)的表示 第三章 計算機硬件 第四章 操作系統(tǒng)和文件管理 第五章 多媒體技術(shù)基礎(chǔ) 第六章 程序設(shè)計基礎(chǔ) 第七章 信息系統(tǒng)概述 第八章 計算機網(wǎng)絡(luò)基礎(chǔ)知識 第九章 計算機安全,計算機基礎(chǔ),第六章 程序設(shè)計基礎(chǔ) 第一節(jié) 程序與程序語言 第二節(jié) 算法與算法設(shè)計 第三節(jié) 程序設(shè)計風格,第六章 程序設(shè)計基礎(chǔ),程序和軟件有何不同?,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,10 R=5 20 L=2*3.14*R 30 S=3.14*R*R 40 PRINT R,L,S 50 END,軟件,程序,語言,語言規(guī)則,計算機語言是 編寫程序、制 作軟件的工具,4

2、,計算機程序中規(guī)定了計算機完成某項工作的操作步驟，每一步驟均由計算機能理解的指令或語句描述，這些指令和語句告訴計算機“做什么”和“怎樣做”。,程序是處理某個事物的一系列操作步驟。,一、程序概述,10 R=5 20 L=2*3.14*R 30 S=3.14*R*R 40 PRINT R,L,S 50 END,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法,編寫程序需要兩個方面的描述：,數(shù)據(jù)結(jié)構(gòu) 對數(shù)據(jù)的描述：指定適合問題求解的數(shù)據(jù)組成形式（數(shù)據(jù)類型）。 例如，計算圓面積公式： s=r2 s不能為整數(shù)，而是實數(shù)。 算法 對操作的描述：指定操作的步驟。 1。輸入r的值 2

3、。按s=3.14*r*r計算圓面積,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,二、程序設(shè)計,程序設(shè)計數(shù)據(jù)結(jié)構(gòu)算法方法工具,數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)組織形式。對求解問題的數(shù)據(jù)的描述，影響程序的復雜程度。 算法：解題步驟。對求解問題的過程描述。 決定程序的正確性和解題效率。 程序設(shè)計方法：能編寫“好”程序的方法。 程序設(shè)計工具：可改善設(shè)計環(huán)境，方便和加快程序開發(fā)過程的開發(fā)工具。,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,三、程序設(shè)計語言,面向過程語言 面向?qū)ο笳Z言,FORTRAN BASIC C PASCAL COBOL LISP,C+ C# Visual C Visual BASIC Visual

4、 J+,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,程序設(shè)計語言是規(guī)則和符號的集合,用于編寫計算機程序的語言，包含語法、語義和語用三個方面。 程序設(shè)計語言的基本成分有： 數(shù)據(jù)成分，用于描述程序所涉及的數(shù)據(jù)； 運算成分，用以描述程序中所包含的運算； 控制成分，用以描述程序中所包含的控制； 傳輸成分，用以表達程序中數(shù)據(jù)的傳輸,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,計算機語言：是規(guī)則和符號的集合，是與計算機交流的工具 程序：求解問題的指令序列 軟件：程序的集合,學習語言 設(shè)計程序 制作軟件,概念：,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,第一代：機器語言（2進制機器指令，機器能直接執(zhí)

5、行） 第二代：匯編語言（符號代替機器語言，需要翻譯） 第三代：高級語言（英語和數(shù)學語言代替機器語言，需要翻譯）,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,程序設(shè)計語言的發(fā)展,機器語言（Machine Languages）: 由計算機直接使用的二進制編碼指令構(gòu)成的語言。提供最基本的計算機操作-加、減、比較、搬移操作數(shù)等。 -每種計算機都有自己專用的機器指令集合。 - 計算機唯一理解的語言是機器語言。 - 機器語言的指令必須由“0”和“1”的字符串組成，因為組成計算機內(nèi)部電路的電子器件只有兩種狀態(tài)：關(guān)或開。關(guān)“0”、開”1”。,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,00000000 1

6、0111000 00000000 00100101 00000000 00000101 00000000 01010100,A = 37 + 84,機器語言 二進制機器指令，機器能直接執(zhí)行。,送數(shù)到AX寄存器 被加數(shù) 37 加法 加數(shù) 84,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,符號/匯編語言（ Symbolic / Assembly language ） 用符號或助記符表示不同的機器語言指令。 -需要使用匯編程序?qū)⒅浄g成等價的機器語言。 - 每種類型的計算機都有自己的機器語言，所以有多少種機器，就有多少種匯編語言和翻譯程序。,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,MOV

7、 AX，37 送數(shù)37到AX寄存器 ADD AX，84 AX寄存器內(nèi)容+84送到寄存器AX,匯編語言 用符號代替機器語言，需要翻譯。,A=37+84,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,高級語言（High-level languages）: 高級程序設(shè)計語言與人類的思維和交流方式更接近。使用高級語言，程序設(shè)計員就能夠用類似于英語的語句編寫指令。 -由于計算機只能執(zhí)行機器碼，所以需要翻譯程序把用高級語言編寫的程序翻譯成機器碼。 -高級語言適用于許多不同的計算機。,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,A=37+84,高級語言 英語和數(shù)學語言代替機器語言，需要翻譯。,第六章 程序

8、設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,語言的翻譯器（Language Translator）: 將匯編語言或高級語言翻譯成機器碼的程序。 - 三種類型的翻譯器: 匯編器 編譯器 解釋器,匯編或高級語言編寫的程序,機器碼程序,翻譯器,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,高級語言程序的運行過程,高級語言源程序,機器語言,翻 譯,解釋器：針對解釋式程序設(shè)計語言，使用邊解釋邊執(zhí)行的方式。,編譯器：將源程序代碼全部轉(zhuǎn)換成計算機能識別的目標代碼，連接成可執(zhí)行程序后，可反復執(zhí)行。,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,C語言中的編譯、連接,編譯命令

9、,連接命令,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,四、程序設(shè)計全過程,分析問題，建立數(shù)學模型 確定數(shù)據(jù)結(jié)構(gòu) 確定算法，描述算法 編制程序，調(diào)試程序 運行結(jié)果,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,程序設(shè)計過程：,語言 處理系統(tǒng),第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,分析問題, 建立模型,問題：輸入三角形的三條邊，輸出三角形的面積。,分析：若輸入的三條邊a,b,c能構(gòu)成三角形，則計算三角形面積area的公式為：,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,確定數(shù)據(jù)結(jié)構(gòu)和算法,數(shù)據(jù)結(jié)構(gòu)：三角形的邊長a,b,c和面積area均采用實數(shù),算法：1. 輸入三角形的三條邊a,b,

10、c 2. 計算s=0.5*(a+b+c) 3.計算面積 4. 輸出三角形面積area,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,選擇語言編制程序,main( ) /* 用C語言編寫程序*/ float a,b,c,s,area;/*定義三角形邊長和面積為實型變量*/ scanf(“%f,%f,%f”,/*輸出三角形的三條邊和面積 */ ,平方根函數(shù),第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,上機調(diào)試運行程序,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,兩次運行結(jié)果：,第六章 程序設(shè)計基礎(chǔ),第一節(jié) 程序與程序語言,計算機基礎(chǔ),第六章 程序設(shè)

11、計基礎(chǔ) 第一節(jié) 程序與程序語言 第二節(jié) 算法與算法設(shè)計 第三節(jié) 程序設(shè)計風格,第六章 程序設(shè)計基礎(chǔ),一、什么是算法,算法是為解決問題而采取的方法和步驟。,決定了算法的執(zhí)行順序,算術(shù)運算、邏輯運算、比較運算和數(shù)據(jù)傳送,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,例：從一組正整數(shù)中找到最大的數(shù)。 （正整數(shù)個數(shù)2，3， N）,例如, 12, 8; 12, 8, 13; 12, 8, 13, 9; 12, 8, 13, 9, 11, .,方法1： 第一步: 比較第一個數(shù)和第二個數(shù); 第二步: 比較第一個數(shù)和第三個數(shù); 第三步: 比較第二個數(shù)和第三個數(shù);,這個方法好嗎？,第六章 程序設(shè)計基礎(chǔ),第二節(jié)

12、算法與算法設(shè)計,方法2： 第零步：將最大值置為零； 第一步：如果當前數(shù)大于最大值，那么將最大值置為當前數(shù)，否則保留原最大值； 第二步：重復第一步直至所有數(shù)全比較完。,Best!,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,舉例：插入排序法問題，有一個從小到大的數(shù)值序列，將一個新數(shù)插入到序列中。,24,？,6.2算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),12,19,26,37,48,5,9,24,24,舉例：插入排序法問題，有一個從小到大的數(shù)值序列，將一個新數(shù)插入到序列中。,24,24,24,24,24,6.2算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),算法： 開始 i=1 新數(shù)與序列第i個元素比較 如

13、果（新數(shù)比第i個元素大） i 加 1 如果(i大于m)執(zhí)行步驟 否則 執(zhí)行步驟 否則 執(zhí)行步驟 從第i到第m個元素后移一個位置 將新數(shù)置于序列第i個位置 結(jié)束,6.2算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),例如:已知研究生選課情況，安排課程考試的日程, 要求在盡可能短的時間內(nèi)完成考試。,課程之間的關(guān)系：同一研究生選修的課程之間有某種“沖突”關(guān)系，同一個研究生選修的課程不能按排在同一時間內(nèi)考試。,6.2算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),用著色法求解該問題： 每門課程作為一個頂點 頂點的每一種顏色代表一個考試時間， 用盡可能少的顏色為圖的頂點著色， 著上相同顏色的頂點可以按排在同一時間考試,選課

14、：1:ABE 2:CD 3:CEF 4:DFA 5:BF,A,B,C,D,E,F,6.2算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),A,B,D,C,E,F,6.2算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),A,B,D,C,E,F,同一研究生選 修的課程用一種顏 色的邊連接,選課：1:ABE 2:CD 3:CEF 4:DFA 5:BF,使相鄰的頂點著上不同的顏色；,A,C,B,D,E,F,6.2算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),得到如下一種考試日程: 第一天: 算法分析(A), 計算機圖形學(C) 第二天: 形式語言(B), 模式識別人工智能（D) 第三天: 計算機網(wǎng)絡(luò)(E) 第四天: 人工智能(F),

15、6.2算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),二、算法的基本特征,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,算法設(shè)計的原則,1、正確性：對于一切合法的輸入數(shù)據(jù)都能得出滿足要求的結(jié)果。,2、可讀性：算法應(yīng)該易理解，便于交流,3、健壯性：當輸入非法數(shù)據(jù)時，算法應(yīng)恰當?shù)刈鞒龇磻?yīng)或進行相應(yīng)處理。,4、高效率與低存儲量需求：算法執(zhí)行時間較少，算法執(zhí)行所需存儲空間較小。,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,三、算法的表示,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,自然語言 流程圖 N-S流程圖 偽代碼 計算機語言,1. 流程圖,用規(guī)定的一系列圖形、流程線和文字說明算法中的基本操作和控制流程

16、。 流程圖的基本元素包括： 表示相應(yīng)操作的框； 帶箭頭的流程線； 框內(nèi)外必要的文字說明。,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,（1）圖形符號,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,（2）用流程圖表示算法,例：求給定半徑R的圓面積和圓周長。,這是一個數(shù)學問題。 算法： 圓面積 S=* R2 圓周長 L=2*R 這是順序程序結(jié)構(gòu)。,順序,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,例：求給定數(shù)R的絕對值。,選擇,這是分支程序結(jié)構(gòu),第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,T里保存： 1+2+3+K的連加和。 重復進行某種運算，運算對象有規(guī)律地變化。采用循環(huán)結(jié)構(gòu)。,例: 給定

17、K值，求1到 K連加和。 T=1+2+3+K。 1 I 0 T T+I T(I=1,2,3,K),循環(huán),第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,2. NS圖,由于流程圖中的流程線可以任意轉(zhuǎn)向，所以傳統(tǒng)流程圖無法保證程序的結(jié)構(gòu)化，造成了程序設(shè)計中的一系列問題。 兩位美國學者于1973年提出了表示程序結(jié)構(gòu)的N-S圖。,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,（1）圖形符號,順序結(jié)構(gòu),第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,選擇結(jié)構(gòu),第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,循環(huán)結(jié)構(gòu):while循環(huán),第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,循環(huán)結(jié)構(gòu):do-while循環(huán),

18、第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,（2）用N-S流程圖表示算法,例：求給定半徑R的圓面積和圓周長。,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,選擇,例：求給定數(shù)R的絕對值。,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,例: 給定K值，求T=1+2+3+K。,循環(huán),第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,3.偽代碼,偽代碼是描述算法常用的工具之一； 類似英語的表示形式； 部分英語和部分結(jié)構(gòu)化代碼的組合。,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,偽代碼描述算法的一般組成：,算法頭：算法的名字。 目的、條件和返回值： 目的： 有關(guān)算法要做什么的簡短說明 前置條件：列出算

19、法所有前驅(qū)條件 后置條件：指出算法產(chǎn)生的影響 返回值： 算法返回的結(jié)果或無返回值 語句序號：表示語句之間的附屬關(guān)系。,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,例：用偽代碼描述在一數(shù)列中找最小值的算法。,Algorithm （算法）：Finding Smallest Purpose（目的）：在一數(shù)列中找最小值 Pre（前置條件）：List of numbers（數(shù)列） Post（后置條件）：None Return（返回值）：The smallest,3,2,4,1,6,a:,S,3,2,1,算法：設(shè)數(shù)列中第一個數(shù)為最小值S，然后用后續(xù)數(shù)依次與S比較，若比S小，則用該數(shù)替換原S的值，全部比較

20、完成后S即最小值。,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,1.Set smallest to the first number 2.Loop(not end of list) 2.1 if(next number smallest) 2.2.1 set smallest to next number 2.2 end if 3.end loop 4.return smallest End Finding Smallest,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,1. 數(shù)列ai ( i=1,5 ) 2. a1 S, 2 i 3. while( i5 ) 3.1 if( aiS ) t

21、hen ai S endif 3.2 i+1 i end while 4. return S,偽代碼不一定按上述嚴格的格式，且可以使用漢字，只要把算法表達清楚即可。,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,任何算法都可以由順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)這三種基本結(jié)構(gòu)組合來實現(xiàn)。,四、三種基本結(jié)構(gòu),第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,選擇結(jié)構(gòu),第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,循環(huán)結(jié)構(gòu),三種基本結(jié)構(gòu)的特點： 一個入口，一個出口，不出現(xiàn)死循環(huán)和死語句,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,死循環(huán),死語句,例如：,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,用順序

22、結(jié)構(gòu)描述將華氏溫度F轉(zhuǎn)換成攝氏溫度C的流程。 算法： C=5/9*（F-32）。,1、順序結(jié)構(gòu)設(shè)計,順序結(jié)構(gòu)中，按語句的自然順序依次執(zhí)行。,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,用順序結(jié)構(gòu)描述兩個值（a=1, b=2）交換的流程。,1,2,b,a,1,2,1,c,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,選擇結(jié)構(gòu)，又稱為分支結(jié)構(gòu)。根據(jù)選擇結(jié)構(gòu)中判斷的結(jié)果，選擇執(zhí)行相應(yīng)的語句。,2、選擇結(jié)構(gòu)及其程序設(shè)計,用選擇結(jié)構(gòu)描述求兩個數(shù)中的最大值的流程,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,第六

23、章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,用選擇結(jié)構(gòu)描述檢查某年是否閏年的流程。 N年為閏年滿足下列條件之一： 1.N能被400整除 2.N能被4整除，但不能被100整除,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,循環(huán)結(jié)構(gòu)，當循環(huán)控制條件為真時反復執(zhí)行循環(huán)體中的語句，直到循環(huán)控制條件為假時為止。,累加器,計數(shù)器,用循環(huán)結(jié)構(gòu)描述求10個學生成績之和的流程。,3、循環(huán)結(jié)構(gòu)及其程序設(shè)計,用T累計10個學生的成績（K），用I記錄累加的次數(shù)（I=1，2，10）,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,用

24、循環(huán)結(jié)構(gòu)描述求10到100之間所有不能被3整除的整數(shù)的流程,對10到100之間所有數(shù)逐一驗證，凡滿足“不能被3整除”的整數(shù)即可輸出。,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,用選擇結(jié)構(gòu)描述檢查某成績級別的流程。 成績N的級別： A級-N90 B級90N80 C級80N60 D級N60,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,循環(huán)嵌套結(jié)構(gòu)： 一個循環(huán)結(jié)構(gòu)的循環(huán)體中又出現(xiàn)另一個循環(huán)結(jié)構(gòu)。,外循環(huán) 內(nèi)循環(huán),I=1，輸出1 J=1，輸出1 I=2，輸出2 J=1，輸出1 J=2，輸出2 I=3，輸出

25、3 J=1，輸出1 J=2，輸出2 J=3，輸出3,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,在屏幕上顯示邊長為 m 的正方型 要求：從鍵盤輸入 m 值，輸出 m 行每行 m 個*號。 例：輸入 m=4，輸出的圖形如下： * * * * * * * * * * * * * * * *,算法： 1. 輸入 m 2. 重復打印 m 行，每行打印 m 個 *,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,輸出M行,每行M個*號,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,I=1: J=1 輸出 * * J=2 輸出 * * J=3 輸出 * * J=4 輸出 * * 換行 I=2: J=1，2

26、，3，4 * * I=4: J=1，2，3，4 * * * *,屏幕顯示過程,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,從鍵盤輸入n值，輸出n行用*號組成等腰三角形。 例：輸入 n=4，輸出的圖形如下： * * * * * * * * * * * * * * * *,* k=1,n-1=3個空，2*1-1=1個* * * * k=2,n-2=2個空，2*2-1=3個* * * * * * k=3,n-3=1個空，2*3-1=5個* * * * * * * * k=4,n-4=0個空，2*4-1=7個*,共n行，其中第K行由n-k個空格和2k-1

27、個*組成, ,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,分析： 1、輸出 n 行。 2、圖形的第 k 行(1=k=n)由 n-k個空格和 2k-1個 * 組成。 算法設(shè)計： 1.輸入 n; 2.外層循環(huán)n行。 內(nèi)層循環(huán)，每行先輸出n-k個空格 再輸出2k-1個* 換行 內(nèi)層循環(huán)結(jié)束 外層循環(huán)結(jié)束,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,基本思想 首先根據(jù)問題的部分條件預估計出答案的范圍 在預估計的答案范圍內(nèi)，對所有可能的情況逐一驗證。 若某個情況使驗證符合題目的全部條件，則該情況是本題目的一個

28、答案。,五、常見算法窮舉法,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,分析： 假設(shè)a、b分別代表父親和兒子的年齡，x年后a=2b。根據(jù)人的壽命，x取值為：1,2,150,問題：今年父親30歲、兒子6歲，在父親有生之年中，多少年后父親的年齡是兒子的2倍？,算法： 1. 考察x可能的范圍：x=1，2，150； 2. 30+xa, 6+xb 3. 若a=2b，則輸出x。,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,X年后，父親和兒子的年齡,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,分析：本書從1至5編號。 假設(shè)a,b兩個人分別借這5本書中的1本

29、。 當a=i時，表示a借了編號為i的書。 則a、b的取值范圍為：1 = a、b = 5。 滿足題意的一種借閱方法是，2個人所借的書的編號不相同時（a!=b）。,問題：小明有5本新書，要借給、兩位小朋友，若每人每次只能借一本，則可有多少種不同的借法？,算法： 1.考察a可能的范圍：a=1，2，3，4，5； 2.考察b可能的范圍：b=1，2，3，4，5; 3.驗證a,b的所有取值，若a!=b，則輸出a,b。,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,a=1:b=1 不輸出 b=2 輸出1，2 b=3 輸出1，3 b=4 輸出1，4 b=5 輸出1，5 a=2:b=1 輸出2，1 b=2 不輸出

30、 b=3 輸出2，3 b=4 輸出2，4 b=5 輸出2，5 ,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,第六章 程序設(shè)計基礎(chǔ),第二節(jié) 算法與算法設(shè)計,例：抓交通肇事犯 一輛卡車違犯交通規(guī)則，撞人后逃跑?，F(xiàn)場有三人目擊事件，但都沒有記住車號，只記下車號的一些特征: 甲說：牌照的前兩位數(shù)字是相同的； 乙說：牌照的后兩位數(shù)字是相同的，但與前兩位不同； 丙是位數(shù)學家，說：四位的車號剛好是一個整數(shù)的平方。 請根據(jù)以上線索求出車號。,第六章 程序設(shè)計基礎(chǔ),問題分析與算法設(shè)計： 按照題目的要求造出一個前兩位數(shù)(i)相同、后兩位數(shù)(j)相同且相互間又不同的整數(shù)。 得到： （1）0 =31） 使用窮舉法,

31、嘗試i、j的所有可能。,第六章 程序設(shè)計基礎(chǔ),循環(huán)I取值從1到9 循環(huán)J取值從0到9 如果I不等于J 求車牌后四位： I*1000+I*100+J*10+J 如果后四位開方是整數(shù) 輸出后四位 結(jié)束 結(jié)束 循環(huán)J結(jié)束 循環(huán)I結(jié)束,第六章 程序設(shè)計基礎(chǔ),第六章 程序設(shè)計基礎(chǔ),二、二分法,第六章 程序設(shè)計基礎(chǔ),a,b,x1=(a+b)/2,x2,x*,x3,x,用二分法方程的根,例 用二分法求 x3+4x-10=0 在(1,2)內(nèi)的根，要求絕對誤差不超過0.005。 解： f(1)=-50 -(1,2)+ x1 =1.5 f(1.5)0 (1,1.5) x2 =1.25 f(1.25)0 (1.25

32、,1.375) x41.313 f(1.313)0 (1.360,1.368) x8 =1.364,第六章 程序設(shè)計基礎(chǔ), 輸入?yún)^(qū)間初值:a、b 如果f(a)*f(b)0，則執(zhí)行 循環(huán) 求中點:（a+b)/2 y 如果f(y)*f(a)0, 則y a 如果f(y)*f(b)0， 則y b 如果|a-b|0.005,執(zhí)行 循環(huán)結(jié)束 輸出y,第六章 程序設(shè)計基礎(chǔ),由初始的已知條件，先計算出第(N1)步的結(jié)果，再利用前面已知的(N1)項結(jié)果，按照遞推公式（或遵照遞推規(guī)則），推出第N步結(jié)果。 遞推法是程序設(shè)計中最常用的方法之一，使用遞推法必須有明確的遞推初始值和遞推公式。,三、遞推法,第六章 程序設(shè)計基礎(chǔ),例：求菲波那奇數(shù)列第N項的值。 數(shù)列遞推通項公式為： 1 2 n n-1 n-2（n=3） 即：1、1、2、3、5、8、13、21、 根據(jù)遞推通項公式，可用遞推法編寫程序，計算第N項的值。,第六章 程序設(shè)計基礎(chǔ),輸入N,1 U1，1 U2,3 I,U1 + U2 U U2 U1 U U2 I+1 I,輸出U,N 2,I = N,第六章 程序設(shè)計基礎(chǔ),遞推算法求10的階乘。 求解過程：0！= 1 1！= 1*0！ 2！= 2*1！= 2 3！= 3*2！= 6 4！= 4*3！ = 24 5！= 5*4！ = 120