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

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

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

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

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

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

形象、直觀，易于理解；

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

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

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

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

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

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

高級(jí)語言

與人類自然語言相接近且能為計(jì)算機(jī)所接受的通用易學(xué)的計(jì)算機(jī)語言。編程語言的發(fā)展：Result=15+15ReturnLOADRFKeyboardSTORENumberlRFLOADRFKeyboardSTORENumber2RFLOADRONumberlLOADR1Number2ADDIR2R0R1StoreResultR2LOADRFResultSTOREMonitorRFHALT00011111111011110010010000001111000111111110111100100100000111110001000001000000000100010100000100110010000000010010010000101101000111110100001000101111111111110000000000000000程序設(shè)計(jì)語言的發(fā)展計(jì)算機(jī)執(zhí)行源程序的兩種方式：編譯和解釋。-源代碼：采用某種編程語言編寫的計(jì)算機(jī)程序，人類可讀例如：result=2+3-目標(biāo)代碼：計(jì)算機(jī)可直接執(zhí)行，人類不可讀(專家除外)例如：1101001000111011編程語言的執(zhí)行方式編程語言的執(zhí)行方式編譯將源代碼一次性轉(zhuǎn)換成目標(biāo)代碼的過程源代碼編譯器目標(biāo)代碼程序執(zhí)行結(jié)果輸出程序輸入執(zhí)行編譯過程的程序叫做編譯器編程語言的執(zhí)行方式解釋將源代碼逐條轉(zhuǎn)換程目標(biāo)代碼同時(shí)逐條運(yùn)行的過程源代碼編譯器程序輸入結(jié)果輸出執(zhí)行解釋過程的程序叫做解釋器靜態(tài)語言和腳本語言根據(jù)執(zhí)行方式不同，編程語言分為兩類：靜態(tài)語言：使用編譯執(zhí)行的編程語言C/C++語言、Java語言腳本語言：使用解釋執(zhí)行的編程語言Python語言、JavaScript語言、PHP語言程序設(shè)計(jì)語言的分類靜態(tài)語言和腳本語言執(zhí)行方式不同，優(yōu)勢(shì)各有不同靜態(tài)語言：編譯器一次性生成目標(biāo)代碼，優(yōu)化更充分，程序運(yùn)行速度更快腳本語言：執(zhí)行程序時(shí)需要源代碼，維護(hù)更靈活，源代碼維護(hù)靈活、可跨多個(gè)操作系統(tǒng)平臺(tái)程序設(shè)計(jì)語言的分類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è)計(jì)語言的分類編程語言是用于人和計(jì)算機(jī)交流的語言編程語言比自然語言更簡單、更嚴(yán)謹(jǐn)、更精確編譯器/解釋器讀入源代碼，把程序員意圖轉(zhuǎn)換成可執(zhí)行程序，供他人使用程序員按照該語言的語法編寫程序源代碼，把自己的意圖融入到代碼中程序設(shè)計(jì)方法與過程算法與程序設(shè)計(jì)章名：節(jié)名：程序設(shè)計(jì)方法程序設(shè)計(jì)過程12程序設(shè)計(jì)包括面向過程(也叫結(jié)構(gòu)化設(shè)計(jì))和面向?qū)ο髢煞N不同設(shè)計(jì)方法。面向過程順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)面向?qū)ο髮?duì)象類封裝繼承消息多態(tài)性程序設(shè)計(jì)方法設(shè)計(jì)方法的產(chǎn)生結(jié)構(gòu)化程序設(shè)計(jì)最早在20世紀(jì)60年代中期由荷蘭科學(xué)家E.W.Dijikstra提出，程序應(yīng)以模塊化設(shè)計(jì)為中心，將待開發(fā)的軟件系統(tǒng)劃分為若干個(gè)相互獨(dú)立的模塊，這樣使完成每一個(gè)模塊的工作變得單純而明確，為設(shè)計(jì)一些較大的軟件打下了良好的基礎(chǔ)。代表語言：C，F(xiàn)ortran，Pascal……結(jié)構(gòu)化程序設(shè)計(jì)設(shè)計(jì)方法特點(diǎn)：1.采用自頂向下，逐步細(xì)化的模塊化設(shè)計(jì)原則。2.

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

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

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

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

順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)可以組成各種復(fù)雜程序!表示一個(gè)良好算法的基本單元。程序的控制結(jié)構(gòu)按程序語句或模塊在執(zhí)行流中的順序逐個(gè)執(zhí)行。順序結(jié)構(gòu)例：已知一個(gè)攝氏溫度，求對(duì)應(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è)定的條件實(shí)現(xiàn)程序執(zhí)行流的兩路或多路分支開始條件成立否？是否條件成立時(shí)執(zhí)行的語句結(jié)束條件不成立時(shí)執(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è)計(jì)章名：節(jié)名：程序構(gòu)成要素分析常量和變量運(yùn)算符和表達(dá)式語句和函數(shù)1234自然語言程序設(shè)計(jì)語言詞常量、變量詞組運(yùn)算符、表達(dá)式