计算机科学导论PPT幻灯片.pptx

1.1,Objectives:,1.2,Objectives(continued):,1.3,1.4,8.1Concept,Inthissectionweinformallydefineanalgorithmandelaborateontheconceptusinganexample.,Figure8.1:Informaldefinitionofanalgorithm,1.5,Figure8.2:Findingthelargestintegeramongfiveintegers,1.6,Figure8.3:DefiningactionsinFindLargestalgorithm,1.7,Figure8.4:FindLargestrefined,1.8,Figure8.5:GeneralizationofFindLargest,1.9,1.10,8.2Threeconstructs,Computerscientistshavedefinedthreeconstructsforastructuredprogramoralgorithm.Theideaisthataprogrammustbemadeofacombinationofonlythesethreeconstructs:sequence,decision(selection),andrepetition.Ithasbeenproventhereisnoneedforanyotherconstructs.Usingonlytheseconstructsmakesaprogramoranalgorithmeasytounderstand,debug,orchange.,Figure8.6:Threeconstructs,1.11,1.12,8.3AlgorithmRepresentation,Sofar,wehaveusedfigurestoconveytheconceptofanalgorithm.Duringthelastfewdecades,toolshavebeendesignedforthispurpose.Twoofthesetools,UMLandpseudocode,arepresentedhere.,Figure8.7:UMLforthreeconstructs,1.13,Figure8.8:Pseudocodeforthreeconstructs,1.14,Algorithm8.1:Calculatingthesumoftwointegers:,1.15,Algorithm8.2:Assigningpass/nopassgrade:,1.16,Algorithm8.3:Assigningalettergrade:,1.17,Algorithm8.4:Findingthelargestinteger:,1.18,Algorithm8.5:Findthesmallestintegersamong1000:,1.19,1.20,8.4AMoreFormalDefinition,Nowthatwehavediscussedtheconceptofanalgorithmandshownitsrepresentation,hereisamoreformaldefinition.Letuselaborateonthisdefinition.,1.21,8.5BasicAlgorithms,Severalalgorithmsareusedincomputersciencesoprevalentlythattheyareconsidered“basic”.Wediscussthemostcommonhere.Thisdiscussionisverygeneral:implementationdependsonthelanguage.,Figure8.9:Summationalgorithm,1.22,Figure8.10:Productalgorithm,1.23,Figure8.11:Selectionsort,1.24,Figure8.12:Exampleofselectionsort,1.25,Figure8.13:Selectionsortalgorithm,1.26,Figure8.14:Bubblesort,1.27,Figure8.15:Exampleofbubblesort,1.28,Figure8.16:Insertionsort,1.29,Figure8.17:Exampleofinsertionsort,1.30,Figure8.18:Anexampleofasequentialsearch,1.31,Figure8.19:Exampleofabinarysearch,1.32,1.33,8.6Subalgorithms,Thethreeprogrammingconstructsdescribedearlierallowustocreateanalgorithmforanysolvableproblem.Theprinciplesofstructuredprogramming,however,requirethatanalgorithmbebrokenintosmallunitscalledsubalgorithms.Eachsubalgorithmisinturndividedintosmallersubalgorithms.,Figure8.20:Conceptofasubalgorithm,1.34,1.35,8.7Recursion,Ingeneral,therearetwoapproachestowritingalgorithmsforsolvingaproblem.Oneusesiteration,theotherusesrecursion.Recursionisaprocessinwhichanalgorithmcallsitself.,Figure8.21:Iterativedefinitionoffactorial,1.36,Figure8.22:Recursivedefinitionoffactorial,1.37,Figure8.23:Tracingtherecursives