《计算机科学导论》-(第三版)-第08章.ppt

1Objectives:To define an algorithm and relate it to problem solving.To define three constructssequence,selection,and repetitionand describe their use in algorithms.To describe UML diagrams and how they can be used when representing algorithms.To describe pseudocode and how it can be used when representing algorithms.To list basic algorithms and their applications.2Objectives(continued):To describe the concept of sorting and understand the three primitive sorting algorithms.To describe the concept of searching and understand two common searching algorithms.To define subalgorithms and their relations to algorithms.To distinguish between iterative and recursive algorithms.38.1 ConceptIn this section we informally define an algorithm and elaborate on the concept using an example.4Figure 8.1:Informal definition of an algorithm5Figure 8.2:Finding the largest integer among five integers6Figure 8.3:Defining actions in FindLargest algorithm7Figure 8.4:FindLargest refined8Figure 8.5:Generalization of FindLargest98.2 Three constructsComputer scientists have defined three constructs for a structured program or algorithm.The idea is that a program must be made of a combination of only these three constructs:sequence,decision(selection),and repetition.It has been proven there is no need for any other constructs.Using only these constructs makes a program or an algorithm easy to understand,debug,or change.10Figure 8.6:Three constructs118.3 Algorithm RepresentationSo far,we have used figures to convey the concept of an algorithm.During the last few decades,tools have been designed for this purpose.Two of these tools,UML and pseudocode,are presented here.12Figure 8.7:UML for three constructs13Figure 8.8:Pseudocode for three constructs14Algorithm 8.1:Calculating the sum of two integers:15Algorithm 8.2:Assigning pass/no pass grade:16Algorithm 8.3:Assigning a letter grade:17Algorithm 8.4:Finding the largest integer:18Algorithm 8.5:Find the smallest integers among 1000:198.4 A More Formal DefinitionNow that we have discussed the concept of an algorithm and shown its representation,here is a more formal definition.Let us elaborate on this definition.208.5 Basic AlgorithmsSeveral algorithms are used in computer science so prevalently that they are considered“basic”.We discuss the most common here.This discussion is very general:implementation depends on the language.21Figure 8.9:Summation algorithm22Figure 8.10:Product algorithm23Figure 8.11:Selection sort24Figure 8.12:Example of selection sort25Figure 8.13:Selection sort algorithm26Figure 8.14:Bubble sort27Figure 8.15:Example of bubble sort28Figure 8.16:Insertion sort29Figure 8.17:Example of insertion sort30Figure 8.18:An example of a sequential search31Figure 8.19:Example of a binary search328.6 SubalgorithmsThe three programming constructs described earlier allow us to create an algorithm for any solvable problem.The principles of structured programming,however,require that an algorithm be broken into small units called subalgorithms.Each subalgorithm is in turn divided into smaller subalgorithms.33Figure 8.20:Concept of a subalgorithm348.7 RecursionIn general,there are two approaches to writing algorithms for solving a problem.One uses iteration,the other uses recursion.Recursion is a process in which an algorithm calls itself.35Figure 8.21:Iterative definition of factorial36Figure 8.22:Recursive definition of factorial37Figure 8.23:Tracing the recursive solution of factorial38Algorithm 8.6:Iteration solution to factorial problem:39Algorithm 8.7:A recursive solution of the factorial problem:40