語言算法和程序設計方法

語言算法和程序設計方法第一頁，共五十頁，2022年，8月28日從算法到程序再到軟件計算機完成各種不同的任務，需要不同的軟件軟件開發(fā)算法程序軟件程序設計是軟件開發(fā)的一部分程序設計分解為幾個步驟程序設計需要使用程序設計語言算法設計

軟件開發(fā)的任務之一選擇一種語言使用這個語言編寫完成操作任務的代碼程序設計軟件開發(fā)的核心工作是算法設計第二頁，共五十頁，2022年，8月28日算法一項工作如何被完成的步驟數(shù)學問題——尋找如何解決特定問題的方法一個著名的算法歐幾里德算法：求兩個正整數(shù)A和B的最大公約數(shù)

如：9、6的最大公約數(shù)是3第一步：比較A和B這兩個數(shù)，將A設置為較大的數(shù)，B設置 為較小的數(shù)；第二步：A除以B，得到余數(shù)C；第三步：如果C等于0，則最大公約數(shù)就是B； 否則將B賦值給A，C賦值給B，重復進行第二、三步從算法到程序再到軟件ABC9636303第三頁，共五十頁，2022年，8月28日圖靈理論只要能被分解為有限步驟的問題就可以被計算機執(zhí)行有限的步驟能夠將這些步驟設計為計算機所執(zhí)行的程序程序設計中，首先尋找算法，算法找到后，實現(xiàn)算法的步驟算法的描述使用某種計算機語言不同的計算機語言對一個算法具有不同的實現(xiàn)方法算法是程序設計的基礎從算法到程序再到軟件第四頁，共五十頁，2022年，8月28日程序和指令程序program計算機執(zhí)行某種任務的一系列操作步驟的總和一組計算機指令的有序集合

指令instruction控制計算機執(zhí)行各種基本操作的命令指令是計算機執(zhí)行的最基本操作

如：處理器從內存中讀取一個數(shù)據(jù) 二進制的算術運算加、減、乘、除 邏輯判斷等處理器能執(zhí)行的二進制代碼第五頁，共五十頁，2022年，8月28日程序和指令指令作為計算機軟件和硬件的接口指令在處理器中以邏輯電路實現(xiàn)軟件硬件指令第六頁，共五十頁，2022年，8月28日指令系統(tǒng)一個CPU能夠執(zhí)行的所有指令指令的主要類型

數(shù)據(jù)傳輸類

將數(shù)據(jù)從一個地方(源)傳輸?shù)搅硗庖粋€地方(目的) 一種是在CPU內部、存儲器內部、CPU和存儲器之間進行 一種是在CPU和外設（外設接口）之間進行的

算術邏輯運算類 控制操作類

有條件轉移、無條件轉移第七頁，共五十頁，2022年，8月28日翻譯系統(tǒng)基本概念源程序

用各種語言編寫的程序目標程序

源程序經過翻譯，成為機器可執(zhí)行的機器語言程序庫文件 由一些標準子程序(函數(shù)和過程)及常用的應用程序塊組成的文件可執(zhí)行程序 目標程序與庫文件連接后形成的程序程序的整個處理過程

翻譯和庫文件連接裝入源程序目標程序可執(zhí)行程序

執(zhí)行第八頁，共五十頁，2022年，8月28日翻譯系統(tǒng)語言處理系統(tǒng)，翻譯計算機程序任務是把非機器語言編寫的源程序翻譯成目標程序是系統(tǒng)軟件不同編程語言的翻譯系統(tǒng)是不同的分類

匯編程序編譯程序解釋程序逐條翻譯并執(zhí)行源程序的語句，不生成可執(zhí)行文件把源程序代碼一次性翻譯成目標程序代碼，最終生成可執(zhí)行文件把匯編語言源程序翻譯為機器語言程序第九頁，共五十頁，2022年，8月28日編譯系統(tǒng)的結構和工作過程詞法分析程序語法分析程序中間代碼生成程序優(yōu)化程序目標代碼生成程序目標程序源程序Ifx>=0Theny=1Elsey=-1第十頁，共五十頁，2022年，8月28日程序設計語言發(fā)展階段機器語言 低級語言匯編語言 中級語言面向過程的高級語言面向對象的高級語言第十一頁，共五十頁，2022年，8月28日機器語言和指令機器語言計算機能直接執(zhí)行的程序設計語言

二進制語言，用二進制機器指令來編寫程序機器指令的信息操作類型操作數(shù)或操作數(shù)的地址（操作數(shù)的存儲位置）操作結果的存儲位置下一條指令的地址信息指令格式操作碼操作數(shù)或地址碼下一條指令的地址第十二頁，共五十頁，2022年，8月28日機器語言和指令指令的例子：數(shù)1和3的相加指令 100000000000000100000011

“加”操作碼Number1：1Number2：3實現(xiàn)過程用計算器

計算機

程序

過程指令執(zhí)行過程特點既簡單又難執(zhí)行速度最快面向機器，兼容性差，移植性差最低級語言第十三頁，共五十頁，2022年，8月28日計算器的工作原理第十四頁，共五十頁，2022年，8月28日用VB設計的加法程序PrivateSubCommand1_Click()DimAAsInteger,BAsInteger,SAsIntegerA=Val(InputBox("請輸入第一個數(shù)"))B=Val(InputBox("請輸入第二個數(shù)"))S=A+BPrintA;"+";B;"=";SEndSub第十五頁，共五十頁，2022年，8月28日MemoryInputOutput控制器ALUForExample：1+3=4命令：輸入111命令：輸入333WriteWriteReadRead134OutAdd+第十六頁，共五十頁，2022年，8月28日

一條指令的執(zhí)行過程

1.取操作碼2.內部譯碼3.取第一個數(shù)4.取第二個數(shù)5.ALU完成加6.保存結果7.取下一條指令第十七頁，共五十頁，2022年，8月28日匯編語言機器語言的“符號化”用容易記憶的文字符號(助記符)表示指令中的操作碼和地址碼指令格式

助記符符號地址例：加法語句ADDA，B

特點機器不能直接識別可讀性好面向機器，兼容性差，移植性差中級語言

第十八頁，共五十頁，2022年，8月28日高級語言與機器完全獨立的語言，描述解題過程語法與自然語言接近特點面向問題，通用，可移植分類面向過程BASICCPASCALFORTRANCOBOLAda面向對象VisualBasic

C++JAVADelphiPowerBuild第十九頁，共五十頁，2022年，8月28日面向對象程序設計程序的基本成分對象 是具有特殊屬性(數(shù)據(jù))

和方法(行為、操作)的實體特點封裝性繼承性多態(tài)性

把對象的屬性和操作結合在一起，構成一個獨立的對象子類可以擁有父類的屬性和行為基類中定義的屬性和行為被子類繼承后，可以具有不同的數(shù)據(jù)類型或不同的行為第二十頁，共五十頁，2022年，8月28日*其它語言函數(shù)型語言

LISPScheme

說明性語言邏輯語言，用于根據(jù)邏輯推理的原則回答問題Prolog超文本鏈接標記語言(HTML)由一種格式標記和超鏈接組成的“偽語言”，主要用于網絡上的信息服務XML可擴展標記語言其它語言如SQL

第二十一頁，共五十頁，2022年，8月28日*基于組件的程序設計基于組件的程序設計是微軟提出的思想COM（ComponentObjectModel，組件對象模型）組件技術屬于面向對象的程序設計技術使用COM技術，一個新的應用系統(tǒng)的開發(fā)不必按照傳統(tǒng)的方法進行所有代碼的編寫，可以通過組件進行“組裝”軟件對于提高開發(fā)速度、降低開發(fā)成本、增加應用軟件的靈活性、降低軟件維護費用很有幫助軟件開發(fā)技術的主流方向第二十二頁，共五十頁，2022年，8月28日程序設計語言的發(fā)展歷史第二十三頁，共五十頁，2022年，8月28日怎樣編寫程序程序設計是一個系統(tǒng)過程不是簡單的編寫程序代碼一般可以分為六個步驟問題的定義（程序說明）設計解決問題的方案編寫程序代碼進行程序測試編寫程序的文檔程序應用（程序運行與維護）第二十四頁，共五十頁，2022年，8月28日一、理解問題：程序說明程序設計中最重要的部分是對問題的描述設計一個程序是為了解決某個特定的問題分析特定問題，決定應該做什么，如何做 ——系統(tǒng)分析員主要弄清以下問題：程序的目標是什么？即程序需要解決什么樣的問題可能需要輸入哪些數(shù)據(jù)？數(shù)據(jù)具體的處理過程和要求是什么？程序可能產生的數(shù)據(jù)輸出以及輸出形式是什么？示例1

示例2第二十五頁，共五十頁，2022年，8月28日二、設計解決問題的方案對要解決的問題設計出具體的解決方案確定程序的邏輯結構關鍵—設計算法例：歐幾里德算法

——求兩個正整數(shù)A和B的最大公約數(shù)第一步：比較A和B這兩個數(shù)，將A設置為較大的數(shù)，B設 置為較小的數(shù)；第二步：A除以B，得到余數(shù)C；第三步：如果C等于0，則最大公約數(shù)就是B； 否則將B賦值給A，C賦值給B，重復進行第二、三步第二十六頁，共五十頁，2022年，8月28日程序的邏輯結構所有程序都由三種結構構成順序結構

按命令出現(xiàn)的先后順序依次執(zhí)行分支結構

根據(jù)設定的條件來決定程序的執(zhí)行方向循環(huán)結構

按照設定的條件重復執(zhí)行一組命令

當型

直到型

流程圖第二十七頁，共五十頁，2022年，8月28日順序結構A

B分支結構X>=0X=5Y=2*X第二十八頁，共五十頁，2022年，8月28日循環(huán)結構當型結構直到型結構X>=0X>=0第二十九頁，共五十頁，2022年，8月28日三、編寫程序代碼編寫程序代碼選擇合適的編程語言按照上階段設計的算法編寫代碼選擇哪種程序設計語言？主要看是否能夠完成程序設計任務編程人員對這個語言的熟悉程度程序代碼的例子計算5！

fac=1*2*3*4*5 分別用C語言、VB和Java實現(xiàn) 第三十頁，共五十頁，2022年，8月28日一個程序代碼的例子（C語言）

計算5！

#include<stdio.h> /*C語言編譯系統(tǒng)的庫函數(shù)*/main() /*程序開始*/{inti,fac; /*定義變量*/fac=1; /*變量fac被賦值1*/for(i=2;i<=5;i++) /*從2到5，循環(huán)執(zhí)行乘法得到5的階乘*/fac=fac*i;printf("the5!=%d",fac)；/*輸出結果*/}第三十一頁，共五十頁，2022年，8月28日一個程序代碼的例子（VB語言） DimiAsInteger,facAsInteger

'定義i、fac為整型數(shù)變量 fac=1 '變量fac賦值1 Fori=2To5Step1'循環(huán)，從2到5，每次步長為1 fac=fac*i '計算5的階乘Nexti 'next和for構成循環(huán)體 Print"fac=";fac '輸出階乘結果計算5！第三十二頁，共五十頁，2022年，8月28日一個程序代碼的例子（Java語言） publicclassFactorial{ publicstaticvoidmain(Stringargs[]){ inti=1; //循環(huán)控制變量 doublefac=1;//存放結果的變量，注意類型 while(i<=5){ fac=fac*i;//循環(huán)體 i=i+1; } System.out.println("5!="+fac);//輸出結果 } }

計算5！第三十三頁，共五十頁，2022年，8月28日四、尋找錯誤：程序測試調試程序，找出程序中的錯誤語法錯誤違反編程語言的語法規(guī)則邏輯錯誤程序得到的結果不對

需用大量數(shù)據(jù)測試

測試方法黑盒測試 例：加法程序白盒測試 專業(yè)測試，使用一組特意設計的數(shù)據(jù)測試第三十四頁，共五十頁，2022年，8月28日五、編寫程序文檔對前面所做的各種設計形成完整的手冊設計過程中形成的文檔 流程圖 變量列表 程序代碼 運行結果等

供日后程序的維護、升級使用設計完成后的使用手冊 程序的功能 操作說明第三十五頁，共五十頁，2022年，8月28日六、運行與維護培訓用戶程序的安裝、設置等程序進行修改甚至升級第三十六頁，共五十頁，2022年，8月28日算法算法是一組明確的、可以執(zhí)行的步驟的有序集合就是為了解決問題而采用的方法和步驟算法分類數(shù)值運算算法非數(shù)值運算算法算法特性

確定性有窮性有效性可有零個或多個輸入有一個或多個輸出第三十七頁，共五十頁，2022年，8月28日算法的表示方法自然語言流程圖偽代碼PAD圖（問題分析圖）例：求5！的算法

①*用自然語言描述②*用偽代碼表示③用流程圖表示

P=1*2*3*4*5P=P*IP I P*I1 1 11 2 22

3 66

4 2424

5 120

120 6第三十八頁，共五十頁，2022年，8月28日用自然語言表示的求5！的算法第一步：使P＝1第二步：使I＝2第三步：計算P*I，乘積仍放在P中第四步：使I的值加1再放到I中第五步：如果I不大于5，返回重新執(zhí)行第三 步及其后的步驟，否則執(zhí)行第六步第六步：打印出P的值，算法結束第三十九頁，共五十頁，2022年，8月28日開始置P的初值為1置I的初值為2當I<=5,執(zhí)行下面循環(huán)操作：使P=P*I使I=I+1(循環(huán)體到此結束)打印出P的值結束用偽代碼表示的求5！的算法第四十頁，共五十頁，2022年，8月28日

用流程圖表示求5！的算法P第四十一頁，共五十頁，2022年，8月28日算法設計程序設計有兩個階段第一是設計算法第二是實現(xiàn)算法解決問題的基本原理(4個步驟)1.理解問題2.設計一個解決問題的方案3.執(zhí)行這個方案4.檢驗這個方案第四十二頁，共五十頁，2022年，8月28日*常用的算法結構迭代結構遞歸結構排序問題

查找問題第四十三頁，共五十頁，2022年，8月28日迭代結構

不斷用變量的舊值遞推出新值的過程進行數(shù)值計算建立在循環(huán)基礎上的算法關鍵--找到迭代公式

例子分析歐幾里德算法計算S=1!+2!+3!+…+10!

迭代公式 S0=0 a0=1 ai=ai-1*i Si=Si-1+ai開始置S的初值為0置a的初值為1置i的初值為1當i<=10,執(zhí)行下面操作： 使a=a*i 使S=S+a 使i=i+1打印出S的值結束第四十四頁，共五十頁，2022年，8月28日例子分析判斷一個整數(shù)是否為素數(shù)素數(shù)是指只能被1和它本身整除的數(shù)判斷方法：用2到(n-1)的各個整數(shù)輪流去除n，如果都不能 整除，則n是素數(shù)。算法：

第1步：輸入n的值第2步：j=2(準備用j去除n)第3步：n被j除，得到余數(shù)a第4步：如a=0，表示n能被j整除，輸出信息 “n不是素數(shù)”，算法結束；否則就是 n不能被j整除，進入下一步；第5步：將j加1送回給j第6步：如果j<n，則跳到第3步執(zhí)行，否則輸出 “n是素數(shù)”的信息算法結束第四十五頁，共五十頁，2022年，8月28日遞歸結構遞歸指用一個概念本身直接或間接地去定義該概念把一個或者一類問題分解或分割為一個個更小的問題，然后解決這些小