第5章算法與程序設計算法4.程序設計開發環境3.程序設計方法2.程序設計語言1.一、算法什么是算法?規范的定義：定義一個可終止過程的有序的、無歧義的、可執行的步驟的集合簡單的理解：解決計算問題的方法，可以用一系列操作步驟來描述所有步驟應有明確的執行順序每一步操作均應具體、唯一每一步操作都應有效應帶來最終的確定執行結果1、若A大于B，則比較A、C2、若A大于C，則A最大；否則C最大3、若B大于A，則比較B、C4、若B大于C，則B最大；否則C最大使用不同類型的語言怎樣表示算法?舉例在A、B、C中找出最大數ifA>BthenifA>CthenAisMax;else

CisMax;IfB>AthenifB>Cthen

BisMax;else

CisMax;A>B?max←AEndStartmax←BC>max?max←CYesYesNoNo算法描述方法：自然語言、流程圖、偽代碼、程序設計語言……流程圖：算法的常用描述方法A>B?max←AEndStartmax←BC>max?max←CYesYesNoNo用一組幾何圖形和有向線條、配以簡單文字符號來表示算法起止框處理框判斷框流程線I/O框連接點用以上符號可以表示任意復雜的算法如何發現算法？發現算法是一種富有挑戰性的藝術性工作今有雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。凡百錢買雞百只，問雞翁母雛各幾何。FORa=0TO100FORb=0TO100FORc=0TO100IFa+b+c=100AND5a+3b+c/3=100THENPRINTa,b,cENDIFNEXTcNEXTbNEXTa

窮舉法①a+b+c=100②5a+3b+c/3=100其它基本算法累加、累乘、迭代、遞歸、交換、查找、排序、……對同一問題有不同的算法

(X1+X2)X3Y=+Y=X1X3X2X3vsFORa=0TO100FORb=0TO100FORc=0TO100IFa+b+c=100AND5a+3b+c/3=100THENPRINTa,b,cENDIFNEXTcNEXTbNEXTa

a、b、c的組合方案數：共100*100*100種若考慮：a最多為100/5=20，則a、b、c的組合方案數：共20*100*100種若考慮：b最多為100/3=33，則a、b、c的組合方案數：共20*33*100種哪種方案更好？還有沒有更好的算法？對算法的評價與分析評價一種算法正確性可理解性時間復雜度空間復雜度算法運行時間的函數算法占用內存空間大小的函數時、空復雜度與求解問題的規模及需處理數據量的大小有關二、程序設計語言機器語言：最低級的語言特點：

面向機器硬件，直接以二進制書寫程序，是計算機唯一能夠認識的語言0001

010101101100

//將內存6C單元數據加載進寄存器R50001

011001101101//將內存6D單元數據加載進寄存器R60101

0000

0101

0110//將R5與R6相加，結果送入寄存器R00011

0000

01101110//

將R0數據存儲進內存6E單元1100

000000000000//停機缺陷編寫困難，代碼冗長，容易出錯，難以閱讀和理解，可移植性差LDR5,6C//將內存6C單元數據加載進寄存器R5LDR6,6D

//將內存6D單元數據加載進寄存器R6ADDR0,R5,R6//將R5與R6相加，結果送入寄存器R0STR0,6E//

將R0數據存儲進內存6E單元HLT

//停機匯編語言：符號化的低級語言特點

與機器語言本質相同，面向底層硬件操作，因采用助記符而較易使用計算機能直接認識匯編語言嗎？否！必須經過匯編操作！對匯編語言程序的匯編操作匯編程序：一類系統軟件LDR5,6CLDR6,6DADDR0,R5,R6STR0,6EHLT00010101011011000001011001101101010100000101011000110000011011101100000000000000

源程序目標程序高級語言：類自然、數學語言inputX1;inputX2;Y=X1+X2;printY;scanf(“%d”,&x1);if(x1==my_password)

printf(“Welcome!”);else

printf(“Error!”);“高級”的含義：1、從問題的角度考慮，而非從機器的角度

2、繞開復雜的硬件問題，易于掌握和使用

3、主要用于編寫位于較高層次的應用程序常見高級語言：

AdaFortranBASIC、VisualBASIC

C、C++、C#

Java……與匯編語言類似需要將高級語言源程序翻譯

成機器語言目標程序整體編譯

vs

逐行解釋不同類型的高級語言面向對象面向過程

面向問題面向函數面向過程型：注重解決問題的算法和實現過程細節面向對象型：模擬現實世界中各種對象之間的交互三、程序設計方法程序設計的一般過程AddYourTitle分析問題理解問題明確要求整理入口規劃出口設計算法總體規劃逐層抽象自上而下由粗到細編碼確定語言選擇工具遵守語法自下而上調試程序編譯連接試運行反復調試以輸入密碼登錄系統為例AddYourTitle整理文檔使用說明開發資料階段化成果連接將編譯產生的目標程序轉換為可執行程序程序設計中的基本概念變量：X1、X2、Y運算符：+、-、*、/、and、or、not、……InputX1InputX2Y=X1+X2PrintYINPUTpwdIFpwd=my_passwordTHENPRINT“Welcome!”ELSEPRINT“Error!”ENDIF整型int：X1=13;X2=378實型float：X1=12.47;X2=3.9字符型char：x1=‘a’;x2=‘K’字符串型string：pwd=“helloword”……變量有不同數據類型常量：X1=123表達式：X1+X2語句：Y=X1+X2因此變量在使用之前必須先行定義程序設計中的基本概念DefineX1,X2,YasIntegerInputX1InputX2Y=X1+X2PrintYDefinex1asStringINPUTx1IFx1=my_passwordTHENPRINT“Welcome!”ELSEPRINT“Error!”ENDIF注釋語句//在屏幕上顯示X1和X2相運算的結果執行性語句說明性語句說明性語句：編譯后不產生目標代碼執行性語句：編譯后將產生目標代碼順序結構三種基本程序控制結構語句A語句BInputX1InputX2Y=X1+X2PrintY分支結構語句B語句A條件TrueFalseINPUTx1IFx1=“123”THENPRINT“Yse”ELSEPRINT“No”ENDIF循環結構語句A條件TrueFalse可以是多條語句的集合Sum=0i=1DoSum=Sum+ii=i+1LoopWhilei<=100PrintSum語句A條件TrueFalseWhile-do型Do-while型結構化程序設計方法任何復雜算法，都可以由此三種結構組成子程序：另一種重要的基本結構子程序、過程、函數、……功能相對獨立的程序段，可以由其它程序調用InputX1InputX2Y=X1+X2PrintY……InputX1InputX2Y=X1+X2PrintY……InputX1InputX2Y=X1+X2PrintYSubAdder

InputX1InputX2

Y=X1+X2PrintYEndSubCallAdder……CallAdder……CallAdder……子程序的要素調用、跳轉、執行、返回程序模塊化1、將復雜程序劃分為若干個功能模塊2、各個模塊可相對獨立開發3、模塊之間通過一定的接口相互聯系面向對象的方法：更接近現實世界面向過程的方法：強調如何實現過程的細節，將數據及其操作截然分開面向對象的方法：模擬現實世界中的人類思維方式，用對象表達各種元素面向對象的方法面向過程的方法主控程序發球回擊計算路徑判分考慮一個網球游戲開發PlayerAPlayerB技巧Skill力度Endurance發球Serve回擊Return屬性方法PlayerClassJudgeScore面向對象的方法：更接近現實世界JudgeScorePlayerAPlayerB裁決發球裁決回擊修改計分要求回擊要求回擊裁決回擊可實現軟件復用像其它工程領域一樣，將已有的軟件產品做成構件(組件),

并用于新的軟件系統組裝和集成，從而實現產業化四、程序設計開發環境狹義的程序設計過程編輯編譯連接調試發布產生源程序產生目標程序產生可執行程序編輯程序Editor編譯程序Compiler連接程序Linker調試程序DebuggerIDE集成開發環境IntegratedDevelopmentEnvironment整合以上各項工具的應用軟件套件一般針對特定語言量身打造TurboC：學習C語言編程的經典工具小巧，快捷、但：只能用鍵盤操作，只能編輯一份程序VisualC++：C&C++語言的