計(jì)算機(jī)導(dǎo)論課件：ch08[Part3.Computer SW] Algorithms2

1、Chapter 8AlgorithmsKey terms Algorithm:算法，是一種逐步解決問題或完算法，是一種逐步解決問題或完成任務(wù)的方法。每個(gè)算法都有自己不同于其成任務(wù)的方法。每個(gè)算法都有自己不同于其他算法的名字他算法的名字。 Informal definition：非正式定義 Input data ：輸入數(shù)據(jù) output data ：輸出數(shù)據(jù) Findlargest：取最大值。（一種算法的名字） Refinement：精化 Generalization：普遍化（泛化）Figure 8-1Informal definition of an algorithm used in a c

2、omputerFigure 8-2Finding the largest integer among five integersFigure 8-3Defining actions in FindLargest algorithmFigure 8-4FindLargest refinedFigure 8-5Generalization of FindLargestKey terms Three Constructs：三種結(jié)構(gòu) Sequence：順序 Decision(selection)：判斷（選擇） repetition：循環(huán) Figure 8-6Three constructsKey te

3、rms flowchart：流程圖。使用大圖的形式掩蓋了算法的所有細(xì)節(jié)，只顯示算法從開始到結(jié)束的整個(gè)流程。 pseudocode:偽代碼。類似英語(yǔ)的表示法。Figure 8-7Flowcharts for three constructsFigure 8-8Pseudocode for three constructsWrite an algorithm in pseudocode that finds the average of two numbersSee Algorithm 8.1 on the next slide.AverageOfTwoInput: Two numbers1.Ad

4、d the two numbers2.Divide the result by 23.Return the result by step 2EndWrite an algorithm to change a numeric grade to a pass/no pass grade.See Algorithm 8.2 on the next slide.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

5、 Set the grade to “nopass”End if2. Return the gradeEndWrite an algorithm to change a numeric grade to a letter grade.See Algorithm 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 a

6、nd 89, inclusive)then 2.1 Set the grade to “B”End ifContinues on the next slide3. if (the number is between 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 ifContinues on the next slide5. If (the number is les

7、s than 60)then 5.1 Set the grade to “F”End if6. Return the gradeEndWrite an algorithm to find the largest of a set of numbers. You do not know the number of numbers.See Algorithm 8.4 on the next slide.FindLargestInput: A list of positive integers1. Set Largest to 02. while (more integers) 2.1 if (th

8、e integer is greater than Largest) then 2.1.1 Set Largest to the value of the integer End ifEnd while 3. Return LargestEndWrite an algorithm to find the largest of 1000 numbers.See Algorithm 8.5 on the next slide.FindLargestInput: 1000 positive integers1. Set Largest to 02. Set Counter to 03. while

9、(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 LargestEndKey terms More formal definition:更正式的定義1、Ordered set：有序集合。2、unambiguous steps：明確步驟3、produce a result：產(chǎn)生結(jié)果。4、terminate in a

10、 finite time：在有限的時(shí)間內(nèi)終止。Key terms subalgorithm：子算法。 subprogram：子程序 subroutine：子例程 procedure：過(guò)程 function：函數(shù) 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 LargestEndFindLargerI

11、nput: Largest and current integer1. if (the integer is greater than Largest)then 1.1 Set Largest to the value of the integerEnd ifEndsummation：求和product：乘積Smallest and largest：最大和最小Sorting：排序：排序 Selection sort：選擇排序 Bubble sort：冒泡排序 Insertion sort：插入排序Searching：查找 Sequential search：順序查找 binary search

12、：折半查找Figure 8-10SummationFigure 8-11ProductFigure 8-11Sorting 1.Why sorting?2. Sorting Selection Sort Bubble SortInsertion Sort3. Other Sorting:Quick SortHeap SortShell SortBucket SortMerge Sort Figure 8-12Selection sort交換（第k個(gè)最小元素）Figure 8-13: part IExample of selection sortFigure 8-13: part IIExamp

13、le of selection sortFigure 8-14Selection sort algorithmFigure 8-15Bubble sortFigure 8-16: part IExample of bubble sortFigure 8-16: part IIExample of bubble sortFigure 8-17Insertion sortFigure 8-18: part IExample of insertion sortFigure 8-18: part IIExample of insertion sortFigure 8-19Search conceptF

14、igure 8-20: Part ISequential SearchFigure 8-20: Part IIExample of a sequential SearchFigure 8-21Example of a binary sort Iterative：迭代 recursion：遞歸。算法自我調(diào)用。 Factorial:階乘There are two methods for solving a problem: Iteration RecursionFigure 8-22Iterative definition of factorialFigure 8-23Recursive defi

15、nition of factorialFigure 8-24Tracing recursive solution to factorial problemFactorialInput: A positive integer num1. Set FN to 12. Set i to 13. while (i is less than or equal to num) 3.1 Set FN to FN i 3.2 Increment iEnd while4. Return FNEndFactorialInput: A positive integer num1. if (num is equal

16、to 0)then 1.1 return 1else1.2 return num Factorial (num 1) End ifEnd 非正式地講，算法(Algorithm)是一步一步解決問題或完成任務(wù)的方法。Summary 算法接受一個(gè)輸入數(shù)據(jù)的列表，生成一個(gè)輸出數(shù)據(jù)的列表。Summary 程序由順序(sequence)、判斷(decision)和循環(huán)(repetition)結(jié)構(gòu)構(gòu)成。 流程圖（flowchart）是算法圖形化的表示。 偽代碼（ pseudocode ）是算法類似英語(yǔ)的表示。 算法正式定義為一組步驟明確的有序集合，它產(chǎn)生結(jié)果并在有限的時(shí)間內(nèi)終止。Summary 算法可分解為稱為子算