《大學(xué)計算機-計算思維視角》 課件 第4章 算法與程序設(shè)計

算法概念及表示方法算法與程序設(shè)計章名：節(jié)名：算法的定義及特征算法實例算法的表示方法算法的評價1234是一種逐步解決問題或完成任務(wù)的方法。求解問題或完成任務(wù)的步驟方法輸入數(shù)據(jù)輸出數(shù)據(jù)算法算法的五個基本特征：(1)有窮性(2)確定性(3)可行性(4)有零個或多個輸入(5)有一個或多個輸出算法的定義及特征第一步

將第1個整數(shù)12當(dāng)做當(dāng)前的最大值Largest第二步Largest(12)和第2個整數(shù)(8)比較，發(fā)現(xiàn)Largest值不需要改變第三步

第3個整數(shù)(13)與Largest進行比較，將Largest的值由13代替第四步

當(dāng)前Largest(13)比第4個整數(shù)(9)大，Largest值不變第五步

當(dāng)前Largest(13)比第5個整數(shù)(11)大，Largest值不變第六步?jīng)]有其他數(shù)需要處理，輸出Largest值是13例：在以下數(shù)中（12813911）尋找最大值。算法實例算法實例（12813911）輸入數(shù)據(jù)（13）輸出數(shù)據(jù)自然語言描述方便、通俗，比較習(xí)慣和容易接受；易產(chǎn)生歧義，語句繁瑣、冗長。流程圖描述

形象、直觀，易于理解；

占用篇幅大、畫圖費時、不易修改。N-S圖描述對流程圖的改進，節(jié)省空間。偽代碼描述無固定、嚴(yán)格的語法規(guī)則，便于轉(zhuǎn)換成計算機程序。計算機語言描述算法中步驟可通過已實現(xiàn)的基本運算執(zhí)行有限次實現(xiàn)。算法的表示方法美國國家標(biāo)準(zhǔn)化協(xié)會ANSI(AmericanNationalStandardInstitute)規(guī)定了一些常用的流程圖符號：起止框判斷框處理框輸入/輸出框注釋框流向線連接點用流程圖表示算法N-S流程圖（也叫盒圖）表示算法的三種基本結(jié)構(gòu)：用N-S圖表示算法目的選擇合適算法改進算法評價指標(biāo)時間復(fù)雜度空間復(fù)雜度(1)時間復(fù)雜度時間復(fù)雜度是指計算機執(zhí)行一個算法在時間上的消耗度量。(2)空間復(fù)雜度空間復(fù)雜度是指在—個算法的運行過程中，對臨時耗費的存儲空間的度量。算法的評價編寫程序前，必須先設(shè)計算法算法是程序設(shè)計的靈魂算法當(dāng)中的三類基本單元算法需要通過一些方法表示典型算法舉例算法與程序設(shè)計章名：節(jié)名：窮舉法遞歸123排序為了提高計算機的工作效率，人們通過長時間的研究開發(fā)，總結(jié)了一些典型算法，在應(yīng)用中非常普遍。窮舉水仙花數(shù)破譯密碼百元買百雞遞歸漢諾塔求階乘排序插入排序冒泡排序選擇排序快速排序堆排序……典型算法舉例窮舉法（又稱“枚舉法”）基本思想是：按問題本身的性質(zhì)，通過多重循環(huán)，一一列舉各種可能的情況，并判斷哪一種可能是符合要求的解（不能遺漏，也不能重復(fù)），并在逐一列舉的過程中，檢驗每個可能的解是否是問題的真正解，若是，我們采用這個解，否則拋棄它。

窮舉法例：雞翁一，值錢五、雞母一，值錢三、雞雛三，值錢一，百錢買百雞，問雞翁、雞母、雞雛各幾個?分析:設(shè)雞翁、雞母、雞雛的數(shù)量分別為cocks、hens、chicks，則可得如下模型：5*cocks+3*hens+chicks/3.0=100cocks+hens+chicks=100窮舉法舉例-百元買百雞百雞問題算法描述:公雞的數(shù)目從0遍歷到20母雞的數(shù)目從0遍歷到33小雞的數(shù)目從0遍歷到100如果5*cocks+3*hens+chicks/3.0=100并且cocks+hens+chicks=100則輸出公雞的數(shù)目、母雞的數(shù)目、小雞的數(shù)目。窮舉法舉例-百元買百雞用自身的結(jié)構(gòu)來描述自身，稱為遞歸。是利用問題本身所具有的某種遞推關(guān)系求解問題的一種方法。思考：什么時候需要采用遞歸方法？問題分解遞歸遞歸舉例——階乘問題遞歸舉例——階乘問題遞歸過程與遞歸工作棧遞歸過程在實現(xiàn)時，需要自己調(diào)用自己。層層向下遞歸，返回次序正好相反。排序含義：按數(shù)據(jù)隊列的某個關(guān)鍵字，重新按一定規(guī)律排列其隊列（升序/降序）。實現(xiàn)排序的方法：選擇法冒泡法（氣泡上浮法）插入法……排序在一組數(shù)中，自前而后對相鄰的兩個數(shù)依次進行比較和調(diào)整，讓需要的數(shù)往后冒，不需要的數(shù)往下沉。關(guān)鍵：每當(dāng)相鄰的兩數(shù)比較，發(fā)現(xiàn)它們的排序與要求相反時，就將它們互換。算法名字由來:越大的元素會經(jīng)過交換慢慢“浮”到數(shù)列的頂端。排序舉例-冒泡排序比較、判斷--交換--不交換①第1個數(shù)與第2個數(shù)比較，冒出一個大數(shù)放到第2個位置；當(dāng)前數(shù)與它后面的數(shù)比較，再冒出一個大數(shù)放到后面位置；②依次進行，從1～9，直到產(chǎn)生了第1個大數(shù)；③重復(fù)①②步，從1～8；④依次類推，直至找到第9個高分排在第2位。排序舉例-冒泡排序窮舉法利用計算機高速運算的優(yōu)點，列舉所有可能情況遞歸并不是簡單的自己調(diào)用自己，而是在于問題分解算法還有很多，后續(xù)課程會學(xué)習(xí)到冒泡排序每次比較兩個元素，調(diào)整順序程序設(shè)計語言概述算法與程序設(shè)計章名：節(jié)名：程序設(shè)計語言的發(fā)展編程語言的執(zhí)行方式程序設(shè)計語言的分類123程序設(shè)計語言，即編程語言，主要用于人類和計算機之間的交互。-編程語言種類很多，但生命力強的卻不多-編程語言有600多種，大部分都不再被使用程序設(shè)計語言的發(fā)展通常情況下，分為低級語言和高級語言。編程語言和普通英語越相似，它就越高級。低級語言較難使用，但它們通常能編寫出更小更快的程序。最低級的語言是“機器語言”，它是一系列由數(shù)字0和1組成的代碼構(gòu)成，用于直接與PC的微處理器中的內(nèi)部命令進行交換。

高級語言編寫的程序代碼雖然容易被人們讀懂，但想要計算機知道該如何去做，還是要將這些普通的英文單詞轉(zhuǎn)換成一串串0、1組成的代碼，翻譯或編寫機器語言代碼是極其復(fù)雜的工作，好在有“解釋器”和“編譯器”程序?qū)⒏呒壵Z言編寫的命令翻譯成機器語言來執(zhí)行。程序設(shè)計語言的發(fā)展機器語言匯編語言高級語言面向過程面向?qū)ο笥?、1序列構(gòu)成的指令碼組成如：10000000加

10010000減用助記符號描述的指令系統(tǒng)如ADDA,B>>接近人類的自然語言，更嚴(yán)謹(jǐn)，更精確如：x=a+b程序設(shè)計語言的發(fā)展（1）

機器語言在計算機發(fā)展的早期，唯一的程序設(shè)計語言是機器語言。每臺計算機有自己的機器語言，這種機器語言的指令是由“0”和“1”的字符串組成。計算機唯一能理解的語言是機器語言。例如：完成兩個整數(shù)相加的機器語言代碼00011111111011110010010000001111000111111110111100100100000111110001000001000000000100010100000100110010000000010010010000101101000111110100001000101111111111110000000000000000程序設(shè)計語言的發(fā)展（2）

匯編語言用與代碼指令實際含義相近的英文縮寫詞、字母和數(shù)字等符號取代指令代碼，例如，用ADD代表加法，用MOV代表數(shù)據(jù)傳遞匯編語言：是用助記符號編寫程序的語言。匯編語言源程序：是用匯編語言編出的程序。匯編程序:是將匯編語言源程序翻譯成機器語言程序的程序。例如：完成兩個整數(shù)相加的機器語言代碼LOADRFKeyboardSTORENumberlRFLOADRFKeyboardSTORENumber2RFLOADRONumberlLOADR1Number2ADDIR2R0R1StoreResultR2LOADRFResultSTOREMonitorRFHALT程序設(shè)計語言的發(fā)展（3）

高級語言

與人類自然語言相接近且能為計算機所接受的通用易學(xué)的計算機語言。編程語言的發(fā)展：Result=15+15ReturnLOADRFKeyboardSTORENumberlRFLOADRFKeyboardSTORENumber2RFLOADRONumberlLOADR1Number2ADDIR2R0R1StoreResultR2LOADRFResultSTOREMonitorRFHALT00011111111011110010010000001111000111111110111100100100000111110001000001000000000100010100000100110010000000010010010000101101000111110100001000101111111111110000000000000000程序設(shè)計語言的發(fā)展計算機執(zhí)行源程序的兩種方式：編譯和解釋。-源代碼：采用某種編程語言編寫的計算機程序，人類可讀例如：result=2+3-目標(biāo)代碼：計算機可直接執(zhí)行，人類不可讀(專家除外)例如：1101001000111011編程語言的執(zhí)行方式編程語言的執(zhí)行方式編譯將源代碼一次性轉(zhuǎn)換成目標(biāo)代碼的過程源代碼編譯器目標(biāo)代碼程序執(zhí)行結(jié)果輸出程序輸入執(zhí)行編譯過程的程序叫做編譯器編程語言的執(zhí)行方式解釋將源代碼逐條轉(zhuǎn)換程目標(biāo)代碼同時逐條運行的過程源代碼編譯器程序輸入結(jié)果輸出執(zhí)行解釋過程的程序叫做解釋器靜態(tài)語言和腳本語言根據(jù)執(zhí)行方式不同，編程語言分為兩類：靜態(tài)語言：使用編譯執(zhí)行的編程語言C/C++語言、Java語言腳本語言：使用解釋執(zhí)行的編程語言Python語言、JavaScript語言、PHP語言程序設(shè)計語言的分類靜態(tài)語言和腳本語言執(zhí)行方式不同，優(yōu)勢各有不同靜態(tài)語言：編譯器一次性生成目標(biāo)代碼，優(yōu)化更充分，程序運行速度更快腳本語言：執(zhí)行程序時需要源代碼，維護更靈活，源代碼維護靈活、可跨多個操作系統(tǒng)平臺程序設(shè)計語言的分類Apr2019Apr2018ProgrammingLanguageRatingsChange11Java15.035%-0.74%22C14.076%+0.49%33C++8.838%+1.62%44Python8.166%+2.36%56VisualBasic.NET5.795%+0.85%65C#3.515%-1.75%78JavaScript2.507%-0.99%89SQL2.272%-0.38%97PHP2.239%-1.98%1014Assemblylanguage1.710%+0.05%1118Objective-C1.505%+0.25%1217MATLAB1.285%-0.17%1310Ruby1.277%-0.74%1416Perl1.269%-0.26%1511Delphi/ObjectPascal1.264%-0.70%1612R1.181%-0.63%1713VisualBasic1.060%-0.74%1819Go1.009%-0.17%1915Swift0.978%-0.56%2068Groovy0.932%+0.82%程序設(shè)計語言的分類編程語言是用于人和計算機交流的語言編程語言比自然語言更簡單、更嚴(yán)謹(jǐn)、更精確編譯器/解釋器讀入源代碼，把程序員意圖轉(zhuǎn)換成可執(zhí)行程序，供他人使用程序員按照該語言的語法編寫程序源代碼，把自己的意圖融入到代碼中程序設(shè)計方法與過程算法與程序設(shè)計章名：節(jié)名：程序設(shè)計方法程序設(shè)計過程12程序設(shè)計包括面向過程(也叫結(jié)構(gòu)化設(shè)計)和面向?qū)ο髢煞N不同設(shè)計方法。面向過程順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)面向?qū)ο髮ο箢惙庋b繼承消息多態(tài)性程序設(shè)計方法設(shè)計方法的產(chǎn)生結(jié)構(gòu)化程序設(shè)計最早在20世紀(jì)60年代中期由荷蘭科學(xué)家E.W.Dijikstra提出，程序應(yīng)以模塊化設(shè)計為中心，將待開發(fā)的軟件系統(tǒng)劃分為若干個相互獨立的模塊，這樣使完成每一個模塊的工作變得單純而明確，為設(shè)計一些較大的軟件打下了良好的基礎(chǔ)。代表語言：C，F(xiàn)ortran，Pascal……結(jié)構(gòu)化程序設(shè)計設(shè)計方法特點：1.采用自頂向下，逐步細化的模塊化設(shè)計原則。2.

采用三種基本控制結(jié)構(gòu)：順序、選擇、循環(huán)。a.順序方式，確定各部分的執(zhí)行順序。

b.選擇方式，確定某個部分的執(zhí)行條件。

c.循環(huán)方式，確定某個部分進行重復(fù)的開始和結(jié)束的條件。結(jié)構(gòu)化程序設(shè)計設(shè)計方法的產(chǎn)生面向?qū)ο蟮某绦蛟O(shè)計是20世紀(jì)80年代初就提出的，起源于SmallTalk語言。用面向?qū)ο蟮姆椒ń鉀Q問題，不再將問題分解為過程，而是將問題分解為對象。代表語言：python，C#，java,……面向?qū)ο蟪绦蛟O(shè)計基本概念

①對象：運行時的基本實體②類：同類型對象的抽象③封裝：對象的數(shù)據(jù)和代碼私有，不被外界訪問。對象名1一組屬性一組操作對象名2一組屬性一組操作消息面向?qū)ο蟪绦蛟O(shè)計設(shè)計方法特點：系統(tǒng)中一切皆為對象；對象是屬性及其操作的封裝體；對象可按其性質(zhì)劃分為類，對象成為類的實例；實例關(guān)系和繼承關(guān)系是對象之間的靜態(tài)關(guān)系；消息傳遞是對象之間動態(tài)聯(lián)系的唯一形式；面向?qū)ο蟪绦蛟O(shè)計分析問題設(shè)計算法編寫程序測試運行編寫程序文檔抽象設(shè)計編程檢測結(jié)果程序設(shè)計過程一般包括以下五個步驟：程序設(shè)計過程面向過程是一種以過程為中心的編程思想分析出解決問題的步驟，然后用函數(shù)把這些步驟一個一個實現(xiàn)與面向過程的明顯不同是封裝、繼承、類。面向?qū)ο笫且环N以事物為中心的編程思想程序的控制結(jié)構(gòu)算法與程序設(shè)計章名：節(jié)名：順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)12351程序設(shè)計按流程分為三類控制結(jié)構(gòu)：

順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)可以組成各種復(fù)雜程序!表示一個良好算法的基本單元。程序的控制結(jié)構(gòu)按程序語句或模塊在執(zhí)行流中的順序逐個執(zhí)行。順序結(jié)構(gòu)例：已知一個攝氏溫度，求對應(yīng)的華氏溫度。C語言程序如下:

#include"stdio.h"voidmain(){

floatc,f;printf("輸入攝氏溫度:");scanf("%f",&c);f=5.0*c/9.0+32;printf("華氏溫度為:%g",f);}順序結(jié)構(gòu)也叫分支結(jié)構(gòu)，按設(shè)定的條件實現(xiàn)程序執(zhí)行流的兩路或多路分支開始條件成立否？是否條件成立時執(zhí)行的語句結(jié)束條件不成立時執(zhí)行的語句分支結(jié)構(gòu)的流程圖選擇結(jié)構(gòu)例：打印學(xué)生成績，若成績≥60分打印“Pass”，否則打印“Fail”：#include<stdio.h>voidmain(){floatscore;scanf(″%f″,&score);

if(score<60.0) printf(″Fail\n″);else

printf(″Pass\n);}選擇結(jié)構(gòu)按給定條件重復(fù)執(zhí)行指定的程序段。循環(huán)結(jié)構(gòu)的流程圖初始化部分開始循環(huán)控制條件成立？修改部分需循環(huán)執(zhí)行的規(guī)則或語句。即：循環(huán)體結(jié)束是否循環(huán)結(jié)束循環(huán)結(jié)構(gòu)例：求從1到100的累加和。#include<stdio.h>voidmain(){inti,sum=0;for(i=1;i<=100;i++) sum+=i;printf(″sum=%d\n″,sum);}循環(huán)結(jié)構(gòu)由這些基本結(jié)構(gòu)按一定規(guī)律可組成程序，可解決任何復(fù)雜的問題選擇結(jié)構(gòu)程序的關(guān)鍵是理清條件和操作之間的邏輯關(guān)系循環(huán)結(jié)構(gòu)中最主要的是什么情況下執(zhí)行循環(huán)順序結(jié)構(gòu)屬于直線性思維方式程序基本構(gòu)成要素算法與程序設(shè)計章名：節(jié)名：程序構(gòu)成要素分析常量和變量運算符和表達式語句和函數(shù)1234自然語言程序設(shè)計語言詞常量、變量詞組運算符、表達式