《计算机导论课件：ch08[Part3.Computer SW] Algorithms2》由会员分享，可在线阅读，更多相关《计算机导论课件：ch08[Part3.Computer SW] Algorithms2（69页珍藏版）》请在金锄头文库上搜索。
1、Chapter 8AlgorithmsUnderstand the concept of an algorithm.Understand the concept of an algorithm.Define and use the Define and use the three constructsthree constructs for developing for developingalgorithms: sequence, decision, and repetition.algorithms: sequence, decision, and repetition.Understan
2、d and use three tools to represent algorithms:Understand and use three tools to represent algorithms:flowchart, flowchart, pseudocodepseudocode, and structure chart., and structure chart.After reading this chapter, the reader should be able to:OBJECTIVESUnderstand the concept of modularity and Under
3、stand the concept of modularity and subalgorithmssubalgorithms. .List and comprehend common algorithms. List and comprehend common algorithms. 8.1 Concept8.3 Algorithm representation8.2 Three ConstructsContents8.5 SubalgorithmsSummary8.4 More Formal Definition8.6 Basic Algorithms8.7 RecursionCONCEPT
4、CONCEPT8.1Key termsAlgorithm:算法，是一种逐步解决问题或完算法，是一种逐步解决问题或完成任务的方法。每个算法都有自己不同于其成任务的方法。每个算法都有自己不同于其他算法的名字他算法的名字。Informal definition：非正式定义Input data ：输入数据output data ：输出数据Findlargest：取最大值。（一种算法的名字）Refinement：精化Generalization：普遍化（泛化）Figure 8-1Informal definition of an algorithm used in a computerFigure 8-
5、2Finding the largest integer among five integersFigure 8-3Defining actions in FindLargest algorithmFigure 8-4FindLargest refinedFigure 8-5Generalization of FindLargestTHREE CONSTRUCTSTHREE CONSTRUCTS8.2Key termsThree Constructs：三种结构Sequence：顺序Decision(selection)：判断（选择）repetition：循环 Figure 8-6Three c
6、onstructsALGORITHMALGORITHMREPRESENTATIONREPRESENTATION8.3Key termsflowchart：流程图。使用大图的形式掩盖了算法的所有细节，只显示算法从开始到结束的整个流程。pseudocode:伪代码。类似英语的表示法。Figure 8-7Flowcharts for three constructsFigure 8-8Pseudocode for three constructsExample 1Write an algorithm in pseudocode that finds the average of two number
7、sSolutionSee Algorithm 8.1 on the next slide.AverageOfTwoInput: Two numbers1.Add the two numbers2.Divide the result by 23.Return the result by step 2EndAlgorithm 8.1:Average of twoExample 2Write an algorithm to change a numeric grade to a pass/no pass grade.SolutionSee Algorithm 8.2 on the next slid
8、e.Pass/NoPassGradeInput: One number1.if (the number is greater than or equal to 60)then 1.1 Set the grade to “pass”else 1.2 Set the grade to “nopass”End if2.Return the gradeEndAlgorithm 8.2:Pass/no pass GradeExample 3Write an algorithm to change a numeric grade to a letter grade.SolutionSee Algorith
9、m 8.3 on the next slide.LetterGradeInput: One number1. if (the number is between 90 and 100, inclusive)then 1.1 Set the grade to “A”End if2. if (the number is between 80 and 89, inclusive)then 2.1 Set the grade to “B”End ifAlgorithm 8.3: Letter gradeContinues on the next slide3. if (the number is be
10、tween 70 and 79, inclusive)then 3.1 Set the grade to “C”End if4. if (the number is between 60 and 69, inclusive)then 4.1 Set the grade to “D”End ifAlgorithm 8.3:Letter grade (continued)Continues on the next slide5. If (the number is less than 60)then 5.1 Set the grade to “F”End if6. Return the grade
11、EndAlgorithm 8.3:Letter grade (continued)Example 4Write an algorithm to find the largest of a set of numbers. You do not know the number of numbers.SolutionSee Algorithm 8.4 on the next slide.FindLargestInput: A list of positive integers1.Set Largest to 02.while (more integers) 2.1 if (the integer i
12、s greater than Largest) then 2.1.1 Set Largest to the value of the integer End ifEnd while 3.Return LargestEndAlgorithm 8.4:Find largestExample 5Write an algorithm to find the largest of 1000 numbers.SolutionSee Algorithm 8.5 on the next slide.FindLargestInput: 1000 positive integers1.Set Largest to
13、 02.Set Counter to 03.while (Counter less than 1000) 3.1 if (the integer is greater than Largest) then 3.1.1 Set Largest to the value of the integer End if 3.2 Increment CounterEnd while4.Return LargestEndAlgorithm 8.5:Find largest of 1000 numbersFind largest of 1000 numbersMORE FORMALMORE FORMALDEF
14、INITIONDEFINITION8.4Key termsMore formal definition:更正式的定义1、Ordered set：有序集合。2、unambiguous steps：明确步骤3、produce a result：产生结果。4、terminate in a finite time：在有限的时间内终止。Algorithm:An ordered set of unambiguous steps that produces a result and terminates in a finite time.Note:SUBALGORITHMSSUBALGORITHMS8.5K
15、ey termssubalgorithm：子算法。subprogram：子程序subroutine：子例程procedure：过程function：函数method：方法module：模块Figure 8-9Concept of a subalgorithmFindLargestInput: A list of positive integers1.Set Largest to 02.while (more integers) 2.1 FindLargerEnd while3.Return LargestEndAlgorithm 8.6:Find largestFindLargerInput:
16、 Largest and current integer1.if (the integer is greater than Largest)then 1.1 Set Largest to the value of the integerEnd ifEndSubalgorithm:Find largerBASICBASICALGORITHMSALGORITHMS8.6summation：求和product：乘积Smallest and largest：最大和最小Sorting：排序：排序Selection sort：选择排序Bubble sort：冒泡排序Insertion sort：插入排序S
17、earching：查找Sequential search：顺序查找binary search：折半查找Figure 8-10Summation(1)Initialization(1)Initialization(2)Iteration(2)Iteration(3)Return(3)ReturnThree Part:Three Part:Figure 8-11ProductFigure 8-11Sorting 1.Why sorting?2. Sorting Selection Sort Bubble SortInsertion Sort3. Other Sorting:Quick SortHe
18、ap SortShell SortBucket SortMerge Sort Figure 8-12Selection sort交换（第k个最小元素）Figure 8-13: part IExample of selection sortFigure 8-13: part IIExample of selection sortFigure 8-14Selection sort algorithmFigure 8-15Bubble sortFigure 8-16: part IExample of bubble sortFigure 8-16: part IIExample of bubble
19、sortFigure 8-17Insertion sortFigure 8-18: part IExample of insertion sortFigure 8-18: part IIExample of insertion sortFigure 8-19Search conceptFigure 8-20: Part ISequential SearchFigure 8-20: Part IIExample of a sequential SearchFigure 8-21Example of a binary sortRECURSIONRECURSION8.7Iterative：迭代rec
20、ursion：递归。算法自我调用。Factorial:阶乘There are two methods for solving a problem:IterationRecursionFigure 8-22Iterative definition of factorialFigure 8-23Recursive definition of factorialFigure 8-24Tracing recursive solution to factorial problemFactorialInput: A positive integer num1.Set FN to 12.Set i to 1
21、3.while (i is less than or equal to num) 3.1 Set FN to FN i 3.2 Increment iEnd while4.Return FNEndAlgorithm 8.7:Iterative factorialFactorialInput: A positive integer num1.if (num is equal to 0)then 1.1 return 1else1.2 return num Factorial (num 1) End ifEndAlgorithm 8.8:Recursive factorial非正式地讲，算法(Al
22、gorithm)是一步一步解决问题或完成任务的方法。Summary 算法接受一个输入数据的列表，生成一个输出数据的列表。Summary程序由顺序(sequence)、判断(decision)和循环(repetition)结构构成。 流程图（flowchart）是算法图形化的表示。伪代码（ pseudocode ）是算法类似英语的表示。算法正式定义为一组步骤明确的有序集合，它产生结果并在有限的时间内终止。Summary 算法可分解为称为子算法 ( subalgorithm ) 的更小单元。Summary排序(sorting)是一种基本算法。常用的有选择排序(selection sort)、冒泡排序(bubble sort)、插入排序(insertion sort)。查找(searching)是一种基本算法。常用的有顺序查找（用于无序表）、折半查找（用于有序表）。迭代算法(iterative algorithm)只包括参数而不包括算法本身。Summary递归算法(recursive algorithm)包括算法本身。
