計算機基礎(chǔ)課件-算法與程序設(shè)計

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

CisMax;IfB>AthenifB>Cthen

BisMax;else

CisMax;A>B?max←AEndStartmax←BC>max?max←CYesYesNoNo算法描述方法：自然語言、流程圖、偽代碼、程序設(shè)計語言……流程圖：算法的常用描述方法A>B?max←AEndStartmax←BC>max?max←CYesYesNoNo用一組幾何圖形和有向線條、配以簡單文字符號來表示算法起止框處理框判斷框流程線I/O框連接點用以上符號可以表示任意復(fù)雜的算法如何發(fā)現(xiàn)算法？發(fā)現(xiàn)算法是一種富有挑戰(zhàn)性的藝術(shù)性工作今有雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。凡百錢買雞百只，問雞翁母雛各幾何。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的組合方案數(shù)：共100*100*100種若考慮：a最多為100/5=20，則a、b、c的組合方案數(shù)：共20*100*100種若考慮：b最多為100/3=33，則a、b、c的組合方案數(shù)：共20*33*100種哪種方案更好？還有沒有更好的算法？對算法的評價與分析評價一種算法正確性可理解性時間復(fù)雜度空間復(fù)雜度算法運行時間的函數(shù)算法占用內(nèi)存空間大小的函數(shù)時、空復(fù)雜度與求解問題的規(guī)模及需處理數(shù)據(jù)量的大小有關(guān)二、程序設(shè)計語言機器語言：最低級的語言特點：

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

010101101100

//將內(nèi)存6C單元數(shù)據(jù)加載進寄存器R50001

011001101101//將內(nèi)存6D單元數(shù)據(jù)加載進寄存器R60101

0000

0101

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

0000

01101110//

將R0數(shù)據(jù)存儲進內(nèi)存6E單元1100

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

//將內(nèi)存6D單元數(shù)據(jù)加載進寄存器R6ADDR0,R5,R6//將R5與R6相加，結(jié)果送入寄存器R0STR0,6E//

將R0數(shù)據(jù)存儲進內(nèi)存6E單元HLT

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

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

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

printf(“Welcome!”);else

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

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

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

AdaFortranBASIC、VisualBASIC

C、C++、C#

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

成機器語言目標(biāo)程序整體編譯

vs

逐行解釋不同類型的高級語言面向?qū)ο竺嫦蜻^程

面向問題面向函數(shù)面向過程型：注重解決問題的算法和實現(xiàn)過程細(xì)節(jié)面向?qū)ο笮停耗M現(xiàn)實世界中各種對象之間的交互三、程序設(shè)計方法程序設(shè)計的一般過程AddYourTitle分析問題理解問題明確要求整理入口規(guī)劃出口設(shè)計算法總體規(guī)劃逐層抽象自上而下由粗到細(xì)編碼確定語言選擇工具遵守語法自下而上調(diào)試程序編譯連接試運行反復(fù)調(diào)試以輸入密碼登錄系統(tǒng)為例AddYourTitle整理文檔使用說明開發(fā)資料階段化成果連接將編譯產(chǎn)生的目標(biāo)程序轉(zhuǎn)換為可執(zhí)行程序程序設(shè)計中的基本概念變量：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(chǎn)’;x2=‘K’字符串型string：pwd=“helloword”……變量有不同數(shù)據(jù)類型常量：X1=123表達式：X1+X2語句：Y=X1+X2因此變量在使用之前必須先行定義程序設(shè)計中的基本概念DefineX1,X2,YasIntegerInputX1InputX2Y=X1+X2PrintYDefinex1asStringINPUTx1IFx1=my_passwordTHENPRINT“Welcome!”ELSEPRINT“Error!”ENDIF注釋語句//在屏幕上顯示X1和X2相運算的結(jié)果執(zhí)行性語句說明性語句說明性語句：編譯后不產(chǎn)生目標(biāo)代碼執(zhí)行性語句：編譯后將產(chǎn)生目標(biāo)代碼順序結(jié)構(gòu)三種基本程序控制結(jié)構(gòu)語句A語句BInputX1InputX2Y=X1+X2PrintY分支結(jié)構(gòu)語句B語句A條件TrueFalseINPUTx1IFx1=“123”THENPRINT“Yse”ELSEPRINT“No”ENDIF循環(huán)結(jié)構(gòu)語句A條件TrueFalse可以是多條語句的集合Sum=0i=1DoSum=Sum+ii=i+1LoopWhilei<=100PrintSum語句A條件TrueFalseWhile-do型Do-while型結(jié)構(gòu)化程序設(shè)計方法任何復(fù)雜算法，都可以由此三種結(jié)構(gòu)組成子程序：另一種重要的基本結(jié)構(gòu)子程序、過程、函數(shù)、……功能相對獨立的程序段，可以由其它程序調(diào)用InputX1InputX2Y=X1+X2PrintY……InputX1InputX2Y=X1+X2PrintY……InputX1InputX2Y=X1+X2PrintYSubAdder

InputX1InputX2

Y=X1+X2PrintYEndSubCallAdder……CallAdder……CallAdder……子程序的要素調(diào)用、跳轉(zhuǎn)、執(zhí)行、返回程序模塊化1、將復(fù)雜程序劃分為若干個功能模塊2、各個模塊可相對獨立開發(fā)3、模塊之間通過一定的接口相互聯(lián)系面向?qū)ο蟮姆椒ǎ焊咏F(xiàn)實世界面向過程的方法：強調(diào)如何實現(xiàn)過程的細(xì)節(jié)，將數(shù)據(jù)及其操作截然分開面向?qū)ο蟮姆椒ǎ耗M現(xiàn)實世界中的人類思維方式，用對象表達各種元素面向?qū)ο蟮姆椒嫦蜻^程的方法主控程序發(fā)球回?fù)粲嬎懵窂脚蟹挚紤]一個網(wǎng)球游戲開發(fā)PlayerAPlayerB技巧Skill力度Endurance發(fā)球Serve回?fù)鬜eturn屬性方法PlayerClassJudgeScore面向?qū)ο蟮姆椒ǎ焊咏F(xiàn)實世界JudgeScorePlayerAPlayerB裁決發(fā)球裁決回?fù)粜薷挠嫹忠蠡負(fù)粢蠡負(fù)舨脹Q回?fù)艨蓪崿F(xiàn)軟件復(fù)用像其它工程領(lǐng)域一樣，將已有的軟件產(chǎn)品做成構(gòu)件(組件),

并用于新的軟件系統(tǒng)組裝和集成，從而實現(xiàn)產(chǎn)業(yè)化四、程序設(shè)計開發(fā)環(huán)境狹義的程序設(shè)計過程編輯編譯連接調(diào)試發(fā)布產(chǎn)生源程序產(chǎn)生目標(biāo)程序產(chǎn)生可執(zhí)行程序編輯程序Editor編譯程序Compiler連接程序Linker調(diào)試程序DebuggerIDE集成開發(fā)環(huán)境IntegratedDevelopmentEnvironment整合以上各項工具的應(yīng)用軟件套件一般針對特定語言量身打造TurboC：學(xué)習(xí)C語言編程的經(jīng)典工具小巧，快捷、但：只能用鍵盤操作，只能編輯一份程序VisualC++：C&C++語言的