3.1概述

計算機語言程序算法

①計算機語言計算機語言就是計算機能讀懂的語言，早期的計算機語言叫機器語言。機器語言高級語言書寫翻譯執(zhí)行計算機程序，就是計算機按一定的動作步驟完成指定任務(wù)的一系列命令，例3.1

打印一個由符號“*”組成的倒三角圖形的程序。

********

*******

******

*****

****

***

**

*

voidMain(){inti,j,l;for(i=0;i<8;i++){for(l=0;l<=i;l++){ printf(""); }for(j=8-i;j>0;j--){ printf("*"); } printf("\n"); }}②程序算法可以理解為是完成一項工作的步驟集合。例3.2

烹飪菜譜。櫻桃肉主料:牛里脊肉.雞蛋配料:淀粉.蔥.姜.蒜.白糖.醬油.番茄醬做法:

1.里脊肉切塊,用蛋清淀粉抓勻.

2.油溫五成熱時放入肉塊滑熟備用

3.用醬油.白糖.醋.水淀粉.高湯調(diào)汁.

4.起鍋下蔥.姜.蒜末熗鍋后放番茄醬,再放肉,最后倒汁.例3.3

操作說明。③算法算法在描述上一般使用半形式化的語言，而程序是用形式化的計算機語言描述的；算法對問題求解過程的描述可以比程序粗略，算法經(jīng)過細化以后可以得到計算機程序。一個計算機程序是一個算法的計算機語言表述，而執(zhí)行一個程序就是執(zhí)行一個用計算機語言表述的算法。

計算機語言、算法和程序3.2算法

算法的基本概念算法的表示算法應(yīng)用示例

①算法的基本概念

算法定義算法特性算法評價算法與計算機程序算法是一組明確的、有序的、可以執(zhí)行的步驟集合。算法的概念要求步驟集是有序的，這就要求算法中的各個步驟必須擁有定義完好的、順序執(zhí)行的結(jié)構(gòu)。

算法定義

有窮性

確切性

有0個或多個輸入

有1個或多個輸出

有效性一個算法必須保證執(zhí)行有限步之后結(jié)束算法的每一步驟必須有確切的定義描述運算對象的初始情況，所謂0個輸入是指算法本身給出了初始條件。

算法特性算法的正確性一個算法在計算機上運行所花費的時間在存儲器上所占用的存儲空間（主要考慮在算法運行過程中臨時占用的存儲空間的大?。┧惴ǖ囊鬃x性

算法評價算法是行為的說明，是一組邏輯步驟。計算機程序是算法的一種表示，是使用一些特殊編程語言表達的某些算法?？赡苡袔追N不同的計算機程序，每一種用不同的編程語言實現(xiàn)，但遵循的邏輯步驟是相同的。它們都表達同樣的算法，但是它們不是同樣的程序。

算法與計算機程序

用自然語言表示用流程圖表示用N-S流程圖表示用偽代碼表示用計算機語言表示

②算法的表示流程圖是通過箭頭相互連接的幾何圖形來表達的方法。

流程圖ANSI規(guī)定的一些常用流程圖符號。起止框輸入輸出框判斷框處理框流程線N-S流程圖一種流程圖形式,在這種流程圖中完全去掉了流程線,全部算法寫在一個矩形框內(nèi).順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)ABNoABPYesWhileP1AUntilP2A

偽代碼

偽代碼是一種描述語言。它只是一種描述程序執(zhí)行過程的工具，是面向讀者的，不能直接用于計算機，實際使用時還需轉(zhuǎn)換成某種計算機語言來表示。Sum=0n=1ifn<10thensum=sum+nn=n+1elseprintsumend流程圖即通過箭頭相互連接的幾何圖形的表達方法偽碼是一種在程序設(shè)計過程中表達想法的非正式的符號系統(tǒng)

用自然語言描述

用流程圖表示

用N-S圖表示

用C語言表示例3.4用y=x2-2x+3計算當(dāng)x=0,1,2,3,4,5所對應(yīng)的y值1.置x的下界為0；2.置x的上界為n=5；3.當(dāng)x≤n時，重復(fù)執(zhí)行如下3步，否則算法停止。用公式計算y值輸出一組x和y的值

x值增加1

用自然語言描述

用流程圖描述開始0

x5

nxn?y=x2-2x+3輸出：x與y值增值：x=x+1結(jié)束YN

用N-S圖描述0

x5

n

是x

n否計算：y=x2-2x+3打?。簒與y值增值：x=x+1

直到x>n

用C語言描述main(){intx,y,n;x=0;n=5;while(x<=n){y=x*x-2*x+3;printf(“%d%d”,x,y);x=x+1;}}

基本算法

順序查找

二分查找

排序③算法應(yīng)用示例ABBAPPA順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)算法的三種主要結(jié)構(gòu)PA當(dāng)型循環(huán)直到型循環(huán)

基本算法結(jié)構(gòu)Temp=A開始A=BB=Temp結(jié)束算法分析：要交換磁帶A與磁帶B的內(nèi)容必須借助第三盤磁帶。過程如下：步驟一：準備空白磁帶Temp；步驟二：將A盤磁帶中的音樂轉(zhuǎn)錄到Temp；步驟三：將B盤磁帶中的英語錄入A盤中；步驟四：將Temp盤中的音樂錄入B盤中?！纠}3-5】磁帶A中錄有音樂，磁帶B中錄有外語。請將兩盤磁帶中的內(nèi)容交換。算法分析：要完成題目的任務(wù)，變量a,b分別保存兩個整數(shù)，稱為變量。max稱為中間量，用于存放兩個數(shù)中最大的一個。過程如下：步驟一：輸入兩個整數(shù)到a,b；步驟二：比較a和b；步驟三：如果a>b，則將a中的數(shù)據(jù)保存到max中；步驟四：如果a<b，則將b中的數(shù)據(jù)保存到max中；步驟五：打印max。【例題3-6】從鍵盤輸入兩個數(shù)，輸出最大的一個數(shù)。YN開始max=ba>b？結(jié)束輸入兩個整數(shù)a,bmax=a輸出max【例題3-7】口令檢查。當(dāng)用戶輸入口令正確時，打印“你是合法用戶！”；當(dāng)口令不正確時，提示用戶重新輸入，當(dāng)輸入口令次數(shù)超過三次，而且不正確時結(jié)束程序。算法分析：步驟一：提示用戶輸入一個口令；步驟二：如果口令正確，則打印“你是合法用戶！”；步驟三：如果口令不正確，則打印“你的口令不正確！”，同時返回步驟一；步驟四：如果輸入口令次數(shù)超過三次，結(jié)束程序。YYNNorder←輸入口令開始N=N+1打印"你是合法用戶"Order？N>3？結(jié)束N=1(輸入口令次數(shù))打印"你是非法用戶"

查找查找就是根據(jù)給定的值，在一組數(shù)據(jù)中確定一個其數(shù)值等于給定值的數(shù)據(jù)元素，若存在這樣的數(shù)據(jù)元素說明查找是成功的，否則查找是不成功的。查找的方法：一般分為順序查找、折半查找和樹表查找。順序查找的基本思想：從第一個元素開始，逐個把元素的關(guān)鍵字值和給定值比較，若某個元素的關(guān)鍵字值和給定值相等，則查找成功；否則，若直至第n個值都不相等，說明不存在滿足條件的元素，查找失敗。順序查找法的平均查找長度是n/2。二分查找的基本思想：首先排序表中的數(shù)據(jù)元素，然后與列表“中間位置”的元素比較，若相等則查找成功；若給定值大于“中間位置”的元素值，則在后半部繼續(xù)進行折半查找；否則在前半部進行折半查找?！纠}3-8】已知一個人員名字列表{Marry,Ann,Kelly,Black,Carol,David,John,Hanrry,Fred,Elaine,Oliver,George,Irene,Larry,Nancy}。使用順序查找法，找出John。算法分析：步驟一從列表的第一項開始。步驟二對列表中的每一項，比較列表中的這個表項：a)如果不是John且該項是列表中的最后一項，執(zhí)行步驟四；b)如果不是John，則順序比較下一項，執(zhí)行步驟二；c)如果是John，則執(zhí)行步驟三；步驟三打印查找到的John步驟四結(jié)束找出John需要順序比較這個人員名字列表中的元素7次。查找Marry僅需要比較1次，而查找Nancy確需要比較15次。平均查找長度為7?！纠}3-9】將例題3.8中的人員名字列表按照字母排列，如圖所示。使用二分查找法，查找出John。通過比較中間項將查找范圍限定在表的一半來進行，從本例可見，僅需比較3次，即可找到目標。

排序基本排序算法有：選擇排序、交換排序和插入排序直接選擇排序的基本思想：掃描整個序列，從中選出最小的元素，將它交換到序列的最前面；然后對剩下的序列采用同樣的方法，直到序列空為止。對于長度為n的序列，選擇排序需要掃描n-1遍，每一遍掃描均從剩下的子序列中選出最小的元素，然后將該最小的元素與子序列中的第一個元素進行交換。原序列8921564885161947第1遍選擇1621564885891947第2遍選擇1619564885892147第3遍選擇1619214885895647第4遍選擇1619214785895648第5遍選擇1619214748895685第6遍選擇1619214748568985第7遍選擇16192147485685893.2編程語言

計算機語言解釋與編譯機器語言匯編語言高級語言FORTRANBASICCOBOLPASCALC/C++JAVA…...①

計算機語言計算機語言的發(fā)展1.機器語言由0、1代碼組成，能被計算機直接識別和執(zhí)行的指令集合。特點：占用空間小、執(zhí)行速度快，不易學(xué)習(xí)和修改不同類型機器的指令系統(tǒng)(機器語言)不同，通用性差。2.匯編語言（符號語言）

用助記符代替機器語言中的指令和數(shù)據(jù)特點：易修改，保持了速度快，占用空間小的特點不同類型機器的匯編語言不同3.高級語言由貼近自然語言的“詞”和“數(shù)學(xué)公式”組成

特點：易學(xué)、易讀，易修改，通用性好，不依賴于機器具有很強的通用性和可移植性計算機語言分類4.面向?qū)ο蟮恼Z言---面向?qū)ο蟮恼Z言應(yīng)該是高級語言一個分支.是最活躍的高級語言，它的應(yīng)用價值非常高。特點:它繼承了面向過程的高級語言的合理部分：結(jié)構(gòu)化程序設(shè)計、模塊化、并行處理等，克服了數(shù)據(jù)與對數(shù)據(jù)的處理（代碼）分離的弊端，代表了新穎的程序設(shè)計思維方法。典型的面向?qū)ο蟮恼Z言有：C++、PB、VF、VB、VC、Delphi、Java、.Net等等。C語言：

1972年至1973間由AT＆T公司Bell實驗室的D.M.Ritchie在BCPL語言基礎(chǔ)上設(shè)計而成的，著名的UNIX操作系統(tǒng)就是用C語言編寫的。特點：

語言與運行支撐環(huán)境分離、可移植性好、語言規(guī)模小因而相對簡單、具有指針類型等，C語言本身簡潔、高度靈活、程序運行效率高。此外，在C語言中，有不少操作直接對應(yīng)實際機器所執(zhí)行的動作，并在許多場合可以代替匯編語言。主要計算機語言C++語言：

以C語言為基礎(chǔ)發(fā)展起來的通用程序設(shè)計語言。C++內(nèi)置面向?qū)ο蟮臋C制，支持數(shù)據(jù)抽象。最先由Be11實驗室的B.stroustrup在1980年代設(shè)計并實現(xiàn)，至今仍在不斷發(fā)展。C++語言是對C語言的擴充，擴充的內(nèi)容絕大部分來自其他著名語言（如Simula、ALGOL68、Ada等）的最佳特性。由于C++語言既有數(shù)據(jù)抽象和面向?qū)ο竽芰Γ\行性能高，又能與C語言相兼容，使得數(shù)量巨大的C語言程序能方便地在C++語言環(huán)境中重用。主要計算機語言

②解釋與編譯解釋方式依賴名為解釋器的程序，利用它解釋和執(zhí)行高級語言程序中的語句。解釋器一次讀一條語句，然后立即翻譯并執(zhí)行每一條語句。編譯方式依賴名為編譯器的程序，當(dāng)用戶將高級語言編寫的源程序輸入計算機后，編譯器便把源程序整個地翻譯成用機器語言表示的與之等價的機器語言程序，然后計算機再執(zhí)行該機器語言程序。編譯器和解釋器是兩種語言處理程序，編譯程序與解釋程序最大的區(qū)別之一在于前者生成目標代碼，而后者不生成。輸入JavaScript解釋器<html><head><title>helloworld!</title><head><body><scripttype="text/javascript">username=prompt(“Enteryourname”,””>;document.write(“歡迎”+username+“進入大學(xué)計算機課堂”>;</script></body></html>JavaScript解釋器被嵌入到Web瀏覽器，當(dāng)瀏覽器加載含有JavaScript代碼的網(wǎng)頁時，解釋器就一次執(zhí)行代碼中的一條語句，并在頁面中顯示相應(yīng)的輸出，如圖所示。輸出輸入C++編譯器00100100001000000001111000000010010000100000000111100000#include<stdio.h>main(){inti=1,sum=0;while(i<=10){sum=sum+i;i++;}printf("%d",sum);}編譯一個C++求和程序3.4程序設(shè)計基礎(chǔ)

簡單程序設(shè)計程序中的數(shù)據(jù)描述程序設(shè)計方法程序測試①

簡單程序設(shè)計程序的組成：

說明部分程序體數(shù)據(jù)programConversion(input,output)constinchsPerFoot=12;centimetersPerInch=2.54;varfeet,inches,lengthInInches:integer;centimeters:real;begin

write('Whatisthelengthinfeetandinches?');readln(feet,inches);lengthInInches:=inchesPerFoot*feet+inches;centimeters:=centimetersPerInch*lengthInInches;writeln('Thelengthincentimetersis',centimeters:1:2');

end程序體說明部分編輯器編譯器鏈接器出錯結(jié)果filename.exefilename.c編輯編譯鏈接庫函數(shù)和其他程序執(zhí)行filename.o出錯C語言程序的編輯、編譯、鏈接和執(zhí)行過程

②程序中的數(shù)據(jù)描述高級語言程序中的數(shù)據(jù)類型：

在程序運行中不變的數(shù)值稱為常量

在程序運行中發(fā)生改變的數(shù)值稱為變量擴展的數(shù)據(jù)類型：數(shù)組、指針、結(jié)構(gòu)體高級語言程序中數(shù)據(jù)的處理方式：

在源程序代碼中直接賦值或輸入輸出語句

通過文件系統(tǒng)實現(xiàn)programConversion(input,output)constinchsPerFoot=12;centimetersPerInch=2.54;varfeet,inches,lengthInInches:integer;centimeters:real;beginwrite('Whatisthelengthinfeetandinches?');

readln(feet,inches);

lengthInInches:=inchesPerFoot*feet+inches;centimeters:=centimetersPerInch*lengthInInches;

writeln('Thelengthincentimetersis',centimeters:1:2');

end常量變量輸入數(shù)據(jù)輸出數(shù)據(jù)程序說明程序設(shè)計程序編碼測試程序最終程序文件

明確要解決的問題確定編程目標；定義想得到的輸入/輸出數(shù)據(jù)等。

使用程序設(shè)計方法設(shè)計一個問題或任務(wù)的執(zhí)行方案

使用計算機語言書寫源程序

調(diào)試源程序，消除程序的語法和邏輯錯誤。

程序代碼文件

程序說明文件

用戶操作手冊

程序設(shè)計步驟

程序結(jié)構(gòu)程序設(shè)計的原則

程序流程圖

順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)

自頂向下逐步細化模塊化設(shè)計

自然語言流程圖

N-S流程圖偽代碼

③程序設(shè)計方法

書寫檢查手工調(diào)試編譯調(diào)試采樣數(shù)據(jù)測試用戶測試

④程序測試本章拓展知識

選擇法排序

冒泡法排序

選擇法排序x1x2x3x4x5x6x7x8x9x10比較一輪后記錄最小數(shù)所在下標p=j解題思路外循環(huán)進行排列:i=0~n-1內(nèi)循環(huán)找出本次最小數(shù)位置:j=i+1~n判斷條件:a[j]<a[p]{t=a[i];a[i]=