《计算机科学导论》(第三版)第08章.ppt
1.1,1.2,Objectives:,1.3,Objectives(continued):,1.4,8.1 Concept,In this section we informally define an algorithm and elaborate on the concept using an example.,1.5,Figure 8.1:Informal definition of an algorithm,1.6,Figure 8.2:Finding the largest integer among five integers,1.7,Figure 8.3:Defining actions in FindLargest algorithm,1.8,Figure 8.4:FindLargest refined,1.9,Figure 8.5:Generalization of FindLargest,1.10,8.2 Three constructs,Computer 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.,1.11,Figure 8.6:Three constructs,1.12,8.3 Algorithm Representation,So 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.,1.13,Figure 8.7:UML for three constructs,1.14,Figure 8.8:Pseudocode for three constructs,1.15,Algorithm 8.1:Calculating the sum of two integers:,1.16,Algorithm 8.2:Assigning pass/no pass grade:,1.17,Algorithm 8.3:Assigning a letter grade:,1.18,Algorithm 8.4:Finding the largest integer:,1.19,Algorithm 8.5:Find the smallest integers among 1000:,1.20,8.4 A More Formal Definition,Now 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.,1.21,8.5 Basic Algorithms,Several 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.,1.22,Figure 8.9:Summation algorithm,1.23,Figure 8.10:Product algorithm,1.24,Figure 8.11:Selection sort,1.25,Figure 8.12:Example of selection sort,1.26,Figure 8.13:Selection sort algorithm,1.27,Figure 8.14:Bubble sort,1.28,Figure 8.15:Example of bubble sort,1.29,Figure 8.16:Insertion sort,1.30,Figure 8.17:Example of insertion sort,1.31,Figure 8.18:An example of a sequential search,1.32,Figure 8.19:Example of a binary search,1.33,8.6 Subalgorithms,The 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.,1.34,Figure 8.20:Concept of a subalgorithm,1.35,8.7 Recursion,In 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.,1.36,Figure 8.21:Iterative definition of factorial,1.37,Figure 8.22:Recursive definition of factorial,1.38,Figure 8.23:Tracing the recursive solution of factorial,1.39,Algorithm 8.6:Iteration solution to factorial problem:,1.40,Algorithm 8.7:A recursive solution of the factorial problem:,
