《《計(jì)算機(jī)科學(xué)導(dǎo)論》(第三版)第08章》由會(huì)員分享，可在線閱讀，更多相關(guān)《《計(jì)算機(jī)科學(xué)導(dǎo)論》(第三版)第08章（40頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、1.1 Objectives: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 whe
2、n representing algorithms. To list basic algorithms and their applications. 1.2 Objectives (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 subalgorithm
3、s and their relations to algorithms. To distinguish between iterative and recursive algorithms.1.3 1.4 8.1 ConceptIn this section we informally define an algorithm and elaborate on the concept using an example. Figure 8.1: Informal definition of an algorithm 1.5 Figure 8.2: Finding the largest integ
4、er among five integers 1.6 Figure 8.3: Defining actions in FindLargest algorithm 1.7 Figure 8.4: FindLargest refined 1.8 Figure 8.5: Generalization of FindLargest 1.9 1.10 8.2 Three constructsComputer scientists have defined three constructs for a structured program or algorithm. The idea is that a
5、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. Figure 8.6: Three cons
6、tructs 1.11 1.12 8.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. Figure 8.7: UML for three constructs 1.13 Figure 8.8: P
7、seudocode for three constructs 1.14 Algorithm 8.1 : Calculating the sum of two integers: 1.15 Algorithm 8.2 : Assigning pass/no pass grade: 1.16 Algorithm 8.3 : Assigning a letter grade: 1.17 Algorithm 8.4 : Finding the largest integer : 1.18 Algorithm 8.5 : Find the smallest integers among 1000: 1.
8、19 1.20 8.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. 1.21 8.5 Basic AlgorithmsSeveral algorithms are used in computer science so prevalently that they are consid
9、ered “basic”. We discuss the most common here. This discussion is very general: implementation depends on the language. Figure 8.9: Summation algorithm 1.22 Figure 8.10: Product algorithm 1.23 Figure 8.11: Selection sort 1.24 Figure 8.12: Example of selection sort 1.25 Figure 8.13: Selection sort al
10、gorithm 1.26 Figure 8.14: Bubble sort 1.27 Figure 8.15: Example of bubble sort 1.28 Figure 8.16: Insertion sort 1.29 Figure 8.17: Example of insertion sort 1.30 Figure 8.18: An example of a sequential search 1.31 Figure 8.19: Example of a binary search 1.32 1.33 8.6 SubalgorithmsThe three programmin
11、g 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. Figure 8.20: Concept
12、 of a subalgorithm 1.34 1.35 8.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. Figure 8.21: Iterative definition of factorial 1.36 Figure 8.22: Recursive definition of factorial 1.37 Figure 8.23: Tracing the recursive solution of factorial 1.38 Algorithm 8.6 : Iteration solution to factorial problem: 1.39 Algorithm 8.7 : A recursive solution of the factorial problem: 1.40
《計(jì)算機(jī)科學(xué)導(dǎo)論》(第三版)第08章
