计算机科学导论课件：Chap5-algorithms-and-programming-languag

1

TheProgrammingLayer2OutlineConceptsDefinitionHowtodevelopanalgorithmEssentialfeaturesThreeConstructsAlgorithmRepresentationPseudocodeBasicalgorithms

3OutlineEvolutionCategoriesoflanguages Buildingprograms4ObjectivesDefinealgorithms.Listthe5essentialpropertiesofanalgorithm.Defineandusethethreeconstructsfordeveloping

algorithms:sequence,decision,andrepetition.Understandandusetoolstorepresentalgorithms:pseudocodeUnderstandtheconceptofmodularityandsubalgorithms.Listandcomprehendcommonalgorithms,suchassortingandsearching.5ObjectivesHaveavisionofcomputerlanguageevolution.Distinguishbetweenmachine,assembly,andhigh-levellanguages.Distinguishbetweenthedifferentcategoriesoflanguages:procedural,object-oriented,functional,declarative,andspecial.Understandtheprocessofcreatingandrunningaprogram.6part1

DEFINITION7Informaldefinition8Example--Findingthelargestinteger

amongfiveintegers9Definingactions10Refinement2problemswiththepreviousmethod:Theactioninthefirststepisdifferentfromtheonesfortheothersteps.Thewordingisnotthesameinsteps2to5.11Generalization12FormaldefinitionAlgorithm:anorderedsetofunambiguousstepsthatproducesaresultandterminatesinafinitetime.Itisastep-by-stepproblem-solvingprocedure,especiallyanestablished,recursivecomputationalprocedureforsolvingaprobleminafinitenumberofsteps.Itisaprecise,systematicmethodforproducingaspecifiedresult.135essentialpropertiesofalgorithmsTowritealgorithmsthatarespecifiedwellenoughforacomputertofollow,makesureeveryalgorithmhasfiveessentialproperties:InputsspecifiedOutputsspecifiedDefinitenessEffectivenessFiniteness14InputspecifiedTheinputsarethedatathatwillbetransformedduringthecomputationtoproducetheoutput.Wemustspecifythetypeofthedata,theamountofdata,andtheformthatthedatawilltake.Supposethealgorithmisarecipe.Wemustlisttheingredients(typeofinputs),theirquantities(amountofinput),andtheirpreparation,ifany(formofinputs),asin“1/4cuponion,minced.”15OutputsspecifiedTheoutputsarethedataresultingfromthecomputation,theintendedresult.Oftenthedescriptionisgiveninthenameofthealgorithm,asin“Algorithmtocomputeabattingaverage.”Aswithinputs,wemustspecifythetype,amount,andanyformoftheoutputs.“3dozen3-inchchocolatechipcookies.”Apossibleoutputforsomecomputationisastatementthattherecanbenooutput—thatis,nosolutionispossible.16DefinitenessAlgorithmsmustspecifyeverystep.

Definitenessmeansspecifyingthesequenceofoperationsfortransformingtheinputsintotheoutputs.Everydetailofeachstepmustbespelledout,includinghowtohandleerrors.Definitenessensuresthatifthealgorithmisperformedatdifferenttimesorbydifferentagents(peopleorcomputers)usingthesamedata,theoutputwillbethesame.17EffectivenessItmustbepossiblefortheagenttoexecutethealgorithmmechanicallywithoutanyfurtherinputs,specialtalent,clairvoyance,creativity,helpfromSuperman,andsoon.Whereasdefinitenessspecifieswhichoperationstodo,effectivenessmeansthattheyaredoable.Examplesofineffectiveness:“Entertheamountofincomeyouwouldhavereceivedthisyearhadyouworkedharder”18FinitenessAnalgorithmmusthavefiniteness;itmusteventuallystop,eitherwiththerightoutputorwithastatementthatnosolutionispossible.Ifnoanswercomesback,wecan’ttellwhetherthealgorithmisstillworkingonananswerorisjustplain“stuck”.Finitenessbecomesanissueforcomputeralgorithmsbecauseifthealgorithmdoesn’tspecifywhentostoptherepetition,thecomputerwillcontinuetorepeattheinstructionsforever.Forexample,divide3into10.Anyprocesshavingthesefivepropertieswillbecalledanalgorithm.19part2

3CONSTRUCTS203ConstructsComputerscientistshavedefinedthreeconstructsforastructuredprogramoralgorithm.Theideaisthataprogrammustbemadeupofacombinationofonlythesethreeconstructs:sequence,decision(selection),andrepetition.21SequenceAnalgorithm,andeventuallyaprogram,isasequenceofinstructions,whichcanbeasimpleinstructionoreitheroftheothertwoconstructs.Aprogramisanalgorithmthathasbeencustomizedtosolveaspecifictaskunderaspecificsetofcircumstancesinaspecificlanguage.22Decision23RepetitionInsomeproblems,thesamesequenceofinstructionsmustberepeated.Youhandlethiswiththerepetition(loop)construct.24part3

AlgorithmRepresentation25AlgorithmRepresentationWecanusedifferenttoolstorepresentalgorithms:Pseudo-code26PseudocodeItisanEnglish-likerepresentationofthecoderequiredforanalgorithm.ItispartEnglishandpartstructuredcode.Englishpartprovidesarelaxedsyntaxthatiseasytoread.Codepartconsistsofanextendedversionofthebasicalgorithmicconstructs(sequence,decisionandrepetition).Untilnow,thereisnostandardforpseudocode.27PseudocodeexampleAlgorithm:FindingSmallestPurpose:Thisalgorithmfindsthesmallestnumberamongalistofnumbers.Pre:ListofnumbersPost:NoneReturn:TheSmallest1.Setsmallesttothefirstnumber2.loop(notendoflist)2.1if(nextnumber<smallest)2.1.1setsmallesttonextnumber2.2endif3.endloop4.ReturnsmallestEndfindingSmallest28PseudocodeAnalgorithmwritteninpseudocodecanbedecomposedintoseveralelementsandconstructs.

Header:namethealgorithm.Purpose,precondition,postconditionandreturn:Thepurposeisashortstatementaboutwhatthealgorithmdoes;Thepreconditionlistsanyrequirements;Thepostconditionidentifiesanyeffectcreated;Thereturnshowswhatisreturnedfromthealgorithm.Ifthereisnothingtobereturned,thenullshouldbespecified.

Statementnumbers:listexecutionorder.

Statementconstructs:basedonthreeconstructs. 29PseudocodeExample1WriteanalgorithminpseudocodethatfindstheaverageoftwonumbersSolution

AverageOfTwo

Input:

TwonumbersAddthetwonumbersDividetheresultby2Returntheresultofstep2

EndExample2Writeanalgorithmtochangeanumericgradetoapass/nopassgrade.Solution

Pass/NoPassGrade

Input:

Onenumberif(thenumberisgreaterthanorequalto60)

then1.1Setthegradeto“pass”else1.2Setthegradeto“nopass”EndifReturnthegrade

EndExample3Writeanalgorithmtochangeanumericgradetoalettergrade.Solution

LetterGrade

Input:

Onenumber1. if(thenumberisbetween90and100,inclusive)

then1.1Setthegradeto“A”Endif2. if(thenumberisbetween80and89,inclusive)

then2.1Setthegradeto“B”Endif…Seepage148Example4Writeanalgorithmtofindthelargestofasetofnumbers.Youdonotknowthenumberofnumbers.Solution

FindLargest

Input:

AlistofpositiveintegersSetLargestto0while(moreintegers)

2.1if(theintegerisgreaterthanLargest)

then

2.1.1Setlargesttothevalueoftheinteger

Endif

EndwhileReturnLargest

EndExample5Writeanalgorithmtofindthelargestof1000numbers.Solution

FindLargest

Input:

1000positiveintegersSetLargestto0SetCounterto0while(Counterlessthan1000)

3.1if(theintegerisgreaterthanLargest)

then

3.1.1SetLargesttothevalueoftheinteger

Endif

3.2IncrementCounter

EndwhileReturnLargest

End35SubprogramsTheprinciplesofstructuredprogrammingrequirethatanalgorithmbebrokenintosmallunitscalledsubalgorithms(thetermsubprograms,subroutines,procedures,functions,methods,andmodulesarealsoused).Eachsubalgorithmisinturndividedintosmallersubalgorithms.Theprocesscontinuesuntilthesubalgorithmbecomeintrinsic(understoodeasily).36SubprogramsWecandivide“AlgorithmFindLargest”intoamainalgorithmandasubalgorithm.Ineachiteration,thealgorithmfindsthelargeroftwointegers.Wecanseparatethispartofthetaskandcreateasmallsubtaskoutofit.37SubprogramsInline2.1,FindLargestissuspendedandFindLargerbegins.FindLargerfindsthelargernumberbetweenthecurrentLargestvalueandthecurrentintegervalue.Thisisknownasafunctioncall.Notethatineachiteration,FindLargeriscalledonce.Theadvantagesofusingsubalgorithms:Itismoreunderstandable.Asubalgorithmcanbecalledmanytimesindifferentpartsofthemainalgorithmwithoutbeingrewritten.38Subprograms

FindLargest Input:

AlistofpositiveintegersSetLargestto0while(moreintegers)

2.1FindLarger

EndwhileReturnLargest

End

FindLarger Input:

Largestandcurrentintegerif(theintegerisgreaterthanLargest)

then

1.1SetLargesttothevalueoftheinteger

Endif

End39Example40Example2.

Writeanalgorithmforasimplecalculator(in

pseudocode

and

structurechart).Pseudocode:Gettwonumbersandtheoperationdesired.Checktheoperation:2.1Ifoperationisaddition,theresultisthefirst+thesecond;2.2Ifoperationissubtraction,theresultisthefirst-thesecond;2.3Ifoperationismultiplication,theresultisthefirst*thesecond;2.4Ifoperationisdivision,checkthesecondnumber:

2.4.1Ifzero,senderrormessage. 2.4.2Ifnotzero,thefirst/thesecond.Printouttheresultortheerrormessage.41Example3.Writeanalgorithminpseudocodeforaprogramtocalculatetheareaofsimpleshapes(rectangle,righttriangleandcircle).Gettheshapedesired.Ifitisarectangle:2.1getthelengthandwidth.2.2calculatetheareaaslength*width.Ifitisarighttriangle:3.1getthebaseandheight.3.2calculatetheareaasbase*height/2.Ifitisacircle:4.1gettheradius.4.2calculatetheareaasradius*radius*3.14.Printoutthearea.42part4

BasicAlgorithms43Summation44Product45SortingSortingistheprocessbywhichdataarearrangedaccordingtotheirvalues.Therearethreefundamentalsortingalgorithms:SelectionsortBubblesortInsertionsort46SelectionsortInselectionsort,thelistisdividedinto2sublists—sortedandunsorted—whicharedividedbyanimaginarywall.Youfindthesmallestelementfromtheunsortedsublistandswapitwiththeelementatthebeginningoftheunsorteddata.Aftereachselectionandswapping,theimaginarywallmovesoneelementahead,increasingthenumberofsortedelementsanddecreasingthenumberofunsortedones.Eachtimeyoumoveoneelementfromtheunsortedsublisttothesortedsublist,youhavecompletedasortpass.Alistofnelementsrequiresn-1passestocompletelyrearrangethedata.47484950BubblesortInbubblesortmethod,thelistisdividedinto2sublists—sortedandunsorted.Thesmallestelementisbubbledfromtheunsortedsublistandmovedtothesortedsublist.Afterthesmallestelementhasbeenmovedtothesortedlist,thewallmovesoneelementahead.Eachtimeanelementmovesfromtheunsortedsublisttothesortedsublist,onesortpassiscompleted.Givenalistofnelements,bubblesortrequiresupton-1passestosortthedata.5152InsertionsortIninsertionsortmethod,thelistisdividedinto2sublists—sortedandunsorted.Ineachpass,thefirstelementoftheunsortedsublistispickedup,transferredtothesortedlist,andinsertedattheappropriateplace.Notethatalistofnelementswilltakeatmostn-1passestosortthedata.5354SearchingSearchingistheprocessoffindingthelocationofatargetamongalistofobjects.Inthecaseofalist,searchingmeansthatgivenavalue,youwanttofindthelocation(index)ofthefirstelementinthelistthatcontainsthatvalue.55SequentialsearchSequentialsearchisusedifthelistbeingsearchedisnotordered.Inasequentialsearch,youstartsearchingforthetargetfromthebeginningofthelist.Youcontinueuntilyoueitherfindthetargetoryouaresurethatitisnotinthelist(becauseyouhavereachedtheendofthelist).5657Binarysearch58part6

Evolution59EvolutionAcomputerlanguageisasetofpredefinedwordsthatarecombinedintoaprogramaccordingtopredefinedrules(syntax).Computerlanguageshaveevolvedfrommachinelanguagetonaturallanguages.60MachinelanguagesMachinelanguage,thelowestleveloflanguage,isthebasiclanguageofthecomputer,representingdataas1sand0s.Machineprogramsvaryfromcomputertocomputer;thatis,theyaremachinedependent.Theonlylanguageunderstoodbyacomputerismachinelanguage.Thesebinarydigitscorrespondtotheonandoffelectricalstatesofthecomputer.61MachinelanguagesAdvantage:itworksefficientlyforcomputer.Disadvantage:itisnotconvenientforpeopletoreadanduse.1234567891011121314151662SymboliclanguagesSymboliclanguage,alsocalledassemblylanguage,isalow-levellanguagethatallowsaprogrammertouseabbreviationsoreasilyrememberedwordsinsteadofnumbers.Assemblylanguagevariesfromcomputertocomputer;it’smachinedependent.Aprogrammercanwriteinstructionsinassemblylanguagemorequicklythaninmachinelanguage;however,it’sstillnotaneasyonetolearn,andit’ssotedioustousethatmistakesarefrequent.63Symboliclanguages12345678910111213141516Entry main, ^m<r2>subl2 #12,spjsb C$MAIN_ARGSmovab $CHAR_STRING_CONpushal -8(fp)pushal (r2)calls #2,readpushal -12(fp)pushal 3(r2)calls #2,readmull3 -8(fp),-12(fp),-pushal 6(r2)calls #2,printclrl r0ret64LanguagetranslatorsAspecialprogramcalledanassemblerisusedtotranslatesymboliccodeintomachinelanguage.Alanguagetranslatorisatypeofsystemsoftwarethattranslatesaprogramwritteninasecond-orhigher-generationlanguageintomachinelanguage.65LanguagetranslatorsLanguagestranslatorsareofthreetypes:AssemblersCompilersInterpreters SourceCodeObjectCodeLanguageTranslator66High-levellanguagesAhighlevellanguageisanEnglish-likelanguagethatallowsuserstowriteinafamiliarnotation,ratherthannumbersorabbreviations.Mosthigh-levellanguagesarenotmachinedependent;theycanbeusedonmorethanonekindofcomputers.Theyareportable,allowingtheprogrammertoconcentrateontheapplicationratherthantheintricaciesofthecomputer.67High-levellanguagesThetranslatorforhigh-levellanguagesisdependingonthelanguage,eitheracompileroraninterpreter.Compiler—executelater.It’ssoftwarethatlooksatanentirehigh-levelprogrambeforetranslatingitintomachinelanguage.ExamplesareCandCOBOL.Interpreter—executeimmediately.It’ssoftwarethatconvertshigh-levellanguagestatementsintomachinelanguageoneatatime,insuccession.ExamplesareBASICandLISP.68NaturallanguagesNaturallanguagesareoftwotypes.Thefirstareordinaryhumanlanguages(suchasChinese,English,Spanishandsoon).Thesecondareprogramminglanguagesthatusehumanlanguagetogivepeopleamorenaturalconnectionwithcomputer.Naturallanguagesarepartofthefieldofstudyknownasartificialintelligence(AI).69part7

Categoriesoflanguages70CategoriesoflanguagesWedividecomputerlanguagesintofivecategories:71ProcedurallanguagesAprocedurallanguageisasetofinstructionsthatareexecutedonebyonefrombeginningtoendunlessaninstructionforcesthecontrolelsewhere.Whenprogrammersneedtosolveaproblemusingoneoftheprocedurallanguages,theyshouldknowtheproceduretofollow.Becauseeachinstructionofprocedurallanguagesisacommandtothecomputersystemtodosomespecifictask,procedurallanguagessometimescalledimperativelanguages.72ProcedurallanguagesFORTRAN(FORmulaTRANslation)COBOL(CommonBusiness-OrientedLanguagePascalCAda73Object-orientedlanguagesUnlikeCandPascalareproceduralorientedlanguages,forcingtheusertofollowapredeterminedpathfromstepAtoStepBandsoon,object-orientedlanguagesareeventdriven—thatis,theyrespondtoinput