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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、。 流程圖的基本元素包括： 表示相應(yīng)操作的框； 帶箭頭的流程線(xiàn)； 框內(nèi)外必要的文字說(shuō)明。,第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),（1）圖形符號(hào),第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),（2）用流程圖表示算法,例：求給定半徑R的圓面積和圓周長(zhǎng)。,這是一個(gè)數(shù)學(xué)問(wèn)題。 算法： 圓面積 S=* R2 圓周長(zhǎng) L=2*R 這是順序程序結(jié)構(gòu)。,順序,第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),例：求給定數(shù)R的絕對(duì)值。,選擇,這是分支程序結(jié)構(gòu),第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),T里保存： 1+2+3+K的連加和。 重復(fù)進(jìn)行某種運(yùn)算，運(yùn)算對(duì)象有規(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è)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),2. NS圖,由于流程圖中的流程線(xiàn)可以任意轉(zhuǎn)向，所以傳統(tǒng)流程圖無(wú)法保證程序的結(jié)構(gòu)化，造成了程序設(shè)計(jì)中的一系列問(wèn)題。 兩位美國(guó)學(xué)者于1973年提出了表示程序結(jié)構(gòu)的N-S圖。,第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),（1）圖形符號(hào),順序結(jié)構(gòu),第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),選擇結(jié)構(gòu),第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),循環(huán)結(jié)構(gòu):while循環(huán),第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),循環(huán)結(jié)構(gòu):do-while循環(huán),

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

19、法所有前驅(qū)條件 后置條件：指出算法產(chǎn)生的影響 返回值： 算法返回的結(jié)果或無(wú)返回值 語(yǔ)句序號(hào)：表示語(yǔ)句之間的附屬關(guān)系。,第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),例：用偽代碼描述在一數(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ù)列中第一個(gè)數(shù)為最小值S，然后用后續(xù)數(shù)依次與S比較，若比S小，則用該數(shù)替換原S的值，全部比較

20、完成后S即最小值。,第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),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è)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),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,偽代碼不一定按上述嚴(yán)格的格式，且可以使用漢字，只要把算法表達(dá)清楚即可。,第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),任何算法都可以由順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)這三種基本結(jié)構(gòu)組合來(lái)實(shí)現(xiàn)。,四、三種基本結(jié)構(gòu),第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),選擇結(jié)構(gòu),第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),循環(huán)結(jié)構(gòu),三種基本結(jié)構(gòu)的特點(diǎn)： 一個(gè)入口，一個(gè)出口，不出現(xiàn)死循環(huán)和死語(yǔ)句,第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),死循環(huán),死語(yǔ)句,例如：,第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),用順序

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

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

24、循環(huán)結(jié)構(gòu)描述求10到100之間所有不能被3整除的整數(shù)的流程,對(duì)10到100之間所有數(shù)逐一驗(yàn)證，凡滿(mǎn)足“不能被3整除”的整數(shù)即可輸出。,第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),用選擇結(jié)構(gòu)描述檢查某成績(jī)級(jí)別的流程。 成績(jī)N的級(jí)別： A級(jí)-N90 B級(jí)90N80 C級(jí)80N60 D級(jí)N60,第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),循環(huán)嵌套結(jié)構(gòu)： 一個(gè)循環(huán)結(jié)構(gòu)的循環(huán)體中又出現(xiàn)另一個(gè)循環(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è)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),在屏幕上顯示邊長(zhǎng)為 m 的正方型 要求：從鍵盤(pán)輸入 m 值，輸出 m 行每行 m 個(gè)*號(hào)。 例：輸入 m=4，輸出的圖形如下： * * * * * * * * * * * * * * * *,算法： 1. 輸入 m 2. 重復(fù)打印 m 行，每行打印 m 個(gè) *,第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),輸出M行,每行M個(gè)*號(hào),第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),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 * * * *,屏幕顯示過(guò)程,第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),從鍵盤(pán)輸入n值，輸出n行用*號(hào)組成等腰三角形。 例：輸入 n=4，輸出的圖形如下： * * * * * * * * * * * * * * * *,* k=1,n-1=3個(gè)空，2*1-1=1個(gè)* * * * k=2,n-2=2個(gè)空，2*2-1=3個(gè)* * * * * * k=3,n-3=1個(gè)空，2*3-1=5個(gè)* * * * * * * * k=4,n-4=0個(gè)空，2*4-1=7個(gè)*,共n行，其中第K行由n-k個(gè)空格和2k-1

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

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

29、。 當(dāng)a=i時(shí)，表示a借了編號(hào)為i的書(shū)。 則a、b的取值范圍為：1 = a、b = 5。 滿(mǎn)足題意的一種借閱方法是，2個(gè)人所借的書(shū)的編號(hào)不相同時(shí)（a!=b）。,問(wèn)題：小明有5本新書(shū)，要借給、兩位小朋友，若每人每次只能借一本，則可有多少種不同的借法？,算法： 1.考察a可能的范圍：a=1，2，3，4，5； 2.考察b可能的范圍：b=1，2，3，4，5; 3.驗(yàn)證a,b的所有取值，若a!=b，則輸出a,b。,第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),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è)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),第六章 程序設(shè)計(jì)基礎(chǔ),第二節(jié) 算法與算法設(shè)計(jì),例：抓交通肇事犯 一輛卡車(chē)違犯交通規(guī)則，撞人后逃跑?，F(xiàn)場(chǎng)有三人目擊事件，但都沒(méi)有記住車(chē)號(hào)，只記下車(chē)號(hào)的一些特征: 甲說(shuō)：牌照的前兩位數(shù)字是相同的； 乙說(shuō)：牌照的后兩位數(shù)字是相同的，但與前兩位不同； 丙是位數(shù)學(xué)家，說(shuō)：四位的車(chē)號(hào)剛好是一個(gè)整數(shù)的平方。 請(qǐng)根據(jù)以上線(xiàn)索求出車(chē)號(hào)。,第六章 程序設(shè)計(jì)基礎(chǔ),問(wèn)題分析與算法設(shè)計(jì)： 按照題目的要求造出一個(gè)前兩位數(shù)(i)相同、后兩位數(shù)(j)相同且相互間又不同的整數(shù)。 得到： （1）0 =31） 使用窮舉法,

31、嘗試i、j的所有可能。,第六章 程序設(shè)計(jì)基礎(chǔ),循環(huán)I取值從1到9 循環(huán)J取值從0到9 如果I不等于J 求車(chē)牌后四位： I*1000+I*100+J*10+J 如果后四位開(kāi)方是整數(shù) 輸出后四位 結(jié)束 結(jié)束 循環(huán)J結(jié)束 循環(huán)I結(jié)束,第六章 程序設(shè)計(jì)基礎(chǔ),第六章 程序設(shè)計(jì)基礎(chǔ),二、二分法,第六章 程序設(shè)計(jì)基礎(chǔ),a,b,x1=(a+b)/2,x2,x*,x3,x,用二分法方程的根,例 用二分法求 x3+4x-10=0 在(1,2)內(nèi)的根，要求絕對(duì)誤差不超過(guò)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è)計(jì)基礎(chǔ), 輸入?yún)^(qū)間初值:a、b 如果f(a)*f(b)0，則執(zhí)行 循環(huán) 求中點(diǎ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è)計(jì)基礎(chǔ),由初始的已知條件，先計(jì)算出第(N1)步的結(jié)果，再利用前面已知的(N1)項(xiàng)結(jié)果，按照遞推公式（或遵照遞推規(guī)則），推出第N步結(jié)果。 遞推法是程序設(shè)計(jì)中最常用的方法之一，使用遞推法必須有明確的遞推初始值和遞推公式。,三、遞推法,第六章 程序設(shè)計(jì)基礎(chǔ),例：求菲波那奇數(shù)列第N項(xiàng)的值。 數(shù)列遞推通項(xiàng)公式為： 1 2 n n-1 n-2（n=3） 即：1、1、2、3、5、8、13、21、 根據(jù)遞推通項(xiàng)公式，可用遞推法編寫(xiě)程序，計(jì)算第N項(xiàng)的值。,第六章 程序設(shè)計(jì)基礎(chǔ),輸入N,1 U1，1 U2,3 I,U1 + U2 U U2 U1 U U2 I+1 I,輸出U,N 2,I = N,第六章 程序設(shè)計(jì)基礎(chǔ),遞推算法求10的階乘。 求解過(guò)程：0！= 1 1！= 1*0！ 2！= 2*1！= 2 3！= 3*2！= 6 4！= 4*3！ = 24 5！= 5*4！ = 120