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

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

CisMax;IfB>AthenifB>Cthen

BisMax;else

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

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

(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種哪種方案更好？還有沒(méi)有更好的算法？對(duì)算法的評(píng)價(jià)與分析評(píng)價(jià)一種算法正確性可理解性時(shí)間復(fù)雜度空間復(fù)雜度算法運(yùn)行時(shí)間的函數(shù)算法占用內(nèi)存空間大小的函數(shù)時(shí)、空復(fù)雜度與求解問(wèn)題的規(guī)模及需處理數(shù)據(jù)量的大小有關(guān)二、程序設(shè)計(jì)語(yǔ)言機(jī)器語(yǔ)言：最低級(jí)的語(yǔ)言特點(diǎn)：

面向機(jī)器硬件，直接以二進(jìn)制書(shū)寫(xiě)程序，是計(jì)算機(jī)唯一能夠認(rèn)識(shí)的語(yǔ)言0001

010101101100

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

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

0000

0101

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

0000

01101110//

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

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

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

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

//停機(jī)匯編語(yǔ)言：符號(hào)化的低級(jí)語(yǔ)言特點(diǎn)

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

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

printf(“Welcome!”);else

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

2、繞開(kāi)復(fù)雜的硬件問(wèn)題，易于掌握和使用

3、主要用于編寫(xiě)位于較高層次的應(yīng)用程序常見(jiàn)高級(jí)語(yǔ)言：

AdaFortranBASIC、VisualBASIC

C、C++、C#

Java……與匯編語(yǔ)言類似需要將高級(jí)語(yǔ)言源程序翻譯

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

vs

逐行解釋不同類型的高級(jí)語(yǔ)言面向?qū)ο竺嫦蜻^(guò)程

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

InputX1InputX2

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

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