計(jì)算思維課件3lecture

算法的實(shí)現(xiàn)—程序設(shè)計(jì)陶先平問(wèn)題1你如何將算法告訴計(jì)算機(jī)？問(wèn)題求解開始問(wèn)題理解和定義算法手工測(cè)試和檢查設(shè)計(jì)階段人可識(shí)別和使用的自然語(yǔ)言程序測(cè)試實(shí)現(xiàn)階段計(jì)算機(jī)能夠精確識(shí)別的語(yǔ)言將自然語(yǔ)言描述的“算法”“翻譯”成計(jì)算機(jī)語(yǔ)言描述的“程序”的過(guò)程請(qǐng)思考以下問(wèn)題在任何時(shí)候，編程之前必須先完成算法設(shè)計(jì)Why？計(jì)算機(jī)能夠識(shí)別和處理的“語(yǔ)言”，不僅僅是C、C++等，也可以是自己定義的語(yǔ)言Forexample？程序運(yùn)行出錯(cuò)，涉及到哪些內(nèi)容？在“翻譯”之前，盡量排除算法錯(cuò)誤問(wèn)題2計(jì)算機(jī)如何從二進(jìn)制bits中識(shí)別并執(zhí)行程序指令呢？40年代的編程：Beforethemiddleofthe1940s,computeroperators“hardwired”theirprograms而后，二進(jìn)制代碼顯然，hardwiredprogram不易修改，setswitches不能算是編碼！如何讓計(jì)算機(jī)的執(zhí)行做到：programmable?Abigproblem!Bigidea:1,計(jì)算機(jī)提供基本的hardwired“原子操作”2,提供編碼方式，支持程序員組合“原子操作”，編寫“程序”3,將“程序”存放在存儲(chǔ)空間中4,計(jì)算機(jī)“解讀”程序編碼，執(zhí)行原子操作例如：0010:操作碼,將”某個(gè)”內(nèi)存中的數(shù)據(jù)復(fù)制到”某個(gè)”寄存器中001:001號(hào)寄存器第一個(gè)操作數(shù)000000100：地址偏移量，4第二個(gè)操作數(shù)：從下一條指令所存儲(chǔ)的地址向后偏移4個(gè)16位，取值5執(zhí)行效果：將5賦值給1號(hào)寄存器問(wèn)題3你看到“編程”了嗎？你看到“語(yǔ)言”了嗎？符號(hào)語(yǔ)言Theearlyprogrammersrealizedthatitwouldbeatremendoushelptousemnemonicsymbolsfortheinstructioncodesandmemorylocations,sotheydevelopedassemblylanguageforthispurpose.高級(jí)程序設(shè)計(jì)語(yǔ)言Programminglanguageabstractionsfallintotwogeneralcategories:dataabstractionandcontrolabstraction.Dataabstractionssimplifyforhumanusersthebehaviorandattributesofdata,suchasnumbers,characterstrings,andsearchtrees.Controlabstractionssimplifypropertiesofthetransferofcontrol,thatis,themodificationoftheexecutionpathofaprogrambasedonthesituationathand.Examplesofcontrolabstractionsareloops,conditionalstatements,andprocedurecalls.Data:BasicAbstractionsBasicdataabstractionsinprogramminglanguageshidetheinternalrepresentationofcommondatavaluesinacomputerAnotherbasicdataabstractionistheuseofsymbolicnamestohidelocationsincomputermemorythatcontaindatavaluesintx;Data:StructuredAbstractionsThedatastructureistheprincipalmethodforcollectingrelateddatavaluesintoasingleunit.Array:inta[10];Record:……Data:UnitAbstractionsInalargeprogram,itisusefulandevennecessarytogrouprelateddataandoperationsonthesedatatogether.Typically,suchabstractionsincludeaccessconventionsandrestrictionsthatsupportinformationhiding.Theunitabstractionisoftenassociatedwiththeconceptofanabstractdatatype,broadlydefinedasasetofdatavaluesandtheoperationsonthosevalues.ClassesinC++andJavaControl:BasicAbstractionsTypicalbasiccontrolabstractionsarethosestatementsinalanguagethatcombineafewmachineinstructionsintoanabstractstatementthatiseasiertounderstandthanthemachineinstructions.SUM=FIRST+SECONDControl:StructuredAbstractionsStructuredcontrolabstractionsdivideaprogramintogroupsofinstructionsthatarenestedwithinteststhatgoverntheirexecution.They,thus,helptheprogrammertoexpressthelogicoftheprimarycontrolstructuresofsequencing,selection,anditeration(loops)Control:StructuredAbstractionsProcedure：ThisallowsaprogrammertoconsiderasequenceofactionsasasingleactionthatcanbecalledorinvokedfrommanyotherpointsinaprogramControl:UnitAbstractionsControlcanalsobeabstractedtoincludeacollectionofproceduresthatprovidelogicallyrelatedservicestootherpartsofaprogramandthatformaunit,orstand-alone,partoftheprogramForexampleintn=0;grade=compute_grade[n];while((grade<90)&&(n<number_of_students)){n++;pute_grade[n];}if(grade>=90)cout<<“Thereisastudentwhogotascoreof”<<grade<<endl;elsecout<<“Nostudenthasahighscore”Problem4:Wherearethedataabstractions?Wherearethecontrolabstractions?問(wèn)題5：如何做到編制出來(lái)的程序“精確”、“無(wú)歧義”？語(yǔ)言的語(yǔ)法和語(yǔ)義例如：intsum=0;intsalary[100];forindexfrom0to99by1dosum=sum+salary[index];end例如：intsum=0;intsalary[100];forindex=0to99by1dosum=sum+salary[index];end語(yǔ)法：規(guī)定了什么樣的句子是合法的，進(jìn)而規(guī)定了什么樣的程序是合法的！語(yǔ)法規(guī)定了程序的正確性嗎？語(yǔ)言的語(yǔ)法和語(yǔ)義語(yǔ)義：用來(lái)精確定義一條語(yǔ)句乃至一個(gè)程序的準(zhǔn)確意義例：#include"stdio.h"

main(){

intx,y;

x=3;

y=x+(++x)+(++x);

printf("%d,%d",x,y);

}總結(jié)算法設(shè)計(jì)和程序設(shè)計(jì)是問(wèn)題求解的兩個(gè)重要環(huán)節(jié)當(dāng)然，數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)隱藏在兩者中間出于不同的目的，我們可以采納不同“級(jí)別”和“風(fēng)格”的程序設(shè)計(jì)語(yǔ)言進(jìn)行編程程序語(yǔ)言需要在“數(shù)據(jù)”和“