《第二章算法c语言基础说课讲解》由会员分享，可在线阅读，更多相关《第二章算法c语言基础说课讲解（43页珍藏版）》请在金锄头文库上搜索。
1、IIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. Sci. & Technol.,YBULecture 2 Basic of AlgorithmLecture 2 Basic of Algorithm 算法基础算法基础IIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. Sci. & Technol.,YBULecture 2 Basic of AlgorithmLecture 2 Basic of Algorith
2、mrrConcept of AlgorithmConcept of AlgorithmrrRepresentation of AlgorithmRepresentation of AlgorithmrrStructured Programming Structured Programming MethodMethodIIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. Sci. & Technol.,YBULecture 2 Basic of AlgorithmLecture 2 Basic of Algo
3、rithmrrConcept of AlgorithmConcept of Algorithm算法的概念算法的概念rr 【重点重点】算法的定义算法的定义rr 【难点难点】算法的五个特性算法的五个特性rrRepresentation of AlgorithmRepresentation of AlgorithmrrStructured Programming Structured Programming MethodMethodIIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. Sci. & Technol
4、.,YBUrr算法算法(Algorithm)(Algorithm)的定义的定义n n AnalgorithmisaAnalgorithmisawell-orderedwell-ordered collectionofcollectionofunambiguousunambiguousandandeffectivelycomputableeffectivelycomputable operationsoperationsthatwhenexecutedthatwhenexecutedproducesaproducesaresultresultandhaltsinaandhaltsinafinit
5、eamountfiniteamountoftimeoftime (SchneiderandGersting(SchneiderandGersting1995)1995)Concept of AlgorithmConcept of AlgorithmIIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. Sci. & Technol.,YBUrr算法算法(Algorithm)(Algorithm)的定义的定义【重点重点】l l 算法是一组算法是一组有穷、有序有穷、有序的规则，它们规的规则，它们规定了解决特定问题
6、的一系列操作，是对定了解决特定问题的一系列操作，是对解题方案的明解题方案的明确、有效确、有效而而完整完整的描述的描述FF 算法是在有限步骤内求解某一问题所使算法是在有限步骤内求解某一问题所使用的一组定义明确的规则用的一组定义明确的规则l l 算法是计算机处理信息的本质算法是计算机处理信息的本质Concept of AlgorithmConcept of AlgorithmIIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. Sci. & Technol.,YBUrr算法算法(Algorithm)(Algor
7、ithm)的定义的定义【重点重点】l l 计算机只能解决能够用算法表示其解决计算机只能解决能够用算法表示其解决方案的问题方案的问题l l 计算机程序本质上是一个计算机程序本质上是一个算法的符号表算法的符号表示示，告诉计算机确切的步骤来执行一个，告诉计算机确切的步骤来执行一个指定的任务指定的任务l l 算法算法 计算方法计算方法&课后阅读：课后阅读：【pp17-21pp17-21】例例2.1-2.52.1-2.5 Concept of AlgorithmConcept of AlgorithmIIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab
8、., Dept.of Comput. Sci. & Technol.,YBUrr一个简单而有用的算法一个简单而有用的算法Concept of AlgorithmConcept of Algorithm1 12 23 3x xy yt tStep 1Step 1：t t x xStep 2Step 2：x x y yStep 3Step 3：y y t tswapswapIIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. Sci. & Technol.,YBUrr算法的五个特性算法的五个特性【难点难点】uu
9、有穷性有穷性(Algorithms(Algorithms halthalt inin aa finitefinite amountamount ofoftime)time)：算法必须在执行有穷步之后结束，而每一步都算法必须在执行有穷步之后结束，而每一步都必须在有穷时间内完成必须在有穷时间内完成uu确定性确定性(Algorithms(Algorithmshavehaveunambiguousunambiguousoperations)operations)：算法中每一步操作的含义都必须是确定算法中每一步操作的含义都必须是确定的，不能有二义性的，不能有二义性uu可行性可行性( (有效性、能行性；有
10、效性、能行性；AlgorithmsAlgorithmshavehaveeffectivelyeffectively computablecomputable operations)operations)：算法中有待算法中有待实现的运算都是基本的，每种运算至少在原理上能由人实现的运算都是基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成用纸和笔在有限的时间内完成uu输输 入入：一个算法可以有一个算法可以有零个零个或多个输入或多个输入uu输输 出出(Algorithms(Algorithms produceproduce aa result)result)：一个算法有一个算法有一个或多个
11、输出一个或多个输出Concept of AlgorithmConcept of Algorithm计算过程计算过程(e.g.,OS)(e.g.,OS)不仅仅是步骤个数不仅仅是步骤个数有限！有限！IIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. Sci. & Technol.,YBUrr算法的五个特性算法的五个特性【难点难点】uu 有穷性破坏的情形有穷性破坏的情形Concept of AlgorithmConcept of AlgorithmStep1:Step1:打印数字打印数字1 1Step2:Ste
12、p2:打印下一个自然数打印下一个自然数Step3:Step3:转转Step2Step2死循环死循环! ! IIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. Sci. & Technol.,YBUrr算法的五个特性算法的五个特性【难点难点】uu 确定性破坏的情形确定性破坏的情形Concept of AlgorithmConcept of AlgorithmStep1:Step1:输入一个数输入一个数Step2:Step2:如果该数如果该数很大很大就显示就显示1,1,否否则显示则显示0 0Step3:Ste
13、p3:算法结束算法结束不确定不确定! !IIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. Sci. & Technol.,YBUrr算法的五个特性算法的五个特性【难点难点】uu 可行性破坏的情形可行性破坏的情形Concept of AlgorithmConcept of AlgorithmStep1:Step1:输入一个数输入一个数Step2:Step2:求该数的求该数的倒数倒数Step3:Step3:输出结果输出结果对对0 0是无效运算是无效运算 ! !IIP Lab., Dept.of Comput
14、. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. Sci. & Technol.,YBUrr算法的五个特性算法的五个特性【难点难点】uu 没有输入（但应该有输入）的情形没有输入（但应该有输入）的情形Concept of AlgorithmConcept of AlgorithmStep1:Step1:比较比较两个数两个数，显示较大的，显示较大的数数Step2:Step2:算法结束算法结束没有输入没有输入! !IIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. S
15、ci. & Technol.,YBUrr算法的五个特性算法的五个特性【难点难点】uu 没有输出的情形没有输出的情形Concept of AlgorithmConcept of AlgorithmStep1:Step1:输入一个数输入一个数Step2:Step2:求大于该数的最小偶数求大于该数的最小偶数Step3:Step3:算法结束算法结束没有输出没有输出! !IIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. Sci. & Technol.,YBUrr从计算的本质看算法从计算的本质看算法* *l l 计
16、算：从一个已知的符号串计算：从一个已知的符号串【输入输入】开开始，按照一定的规则始，按照一定的规则【确定性确定性】改变符改变符号串号串【有效性有效性】，经过有限步骤，经过有限步骤【有穷有穷性性】，最后得到一个满足预先规定的符，最后得到一个满足预先规定的符号串号串【输出输出】，这种变换过程就是计算，这种变换过程就是计算l l 计算就是符号串的连续变换计算就是符号串的连续变换【算法的执算法的执行行】Concept of AlgorithmConcept of AlgorithmIIP Lab., Dept.of Comput. Sci. & Technol.,YBUIIP Lab., Dept.of Comput. Sci. & Technol.,YBU算法与程序算法与程序算法是思想，程序是算法是思想，程序是表示表示l l 算法是准确而完整地描述解决特定问题算法是准确而完整地描述解决特定问题方案方案的有限步骤，不能直接被计算机执的有限步骤，不能直接被计算机执行，但是计算机解决问题的基础行，但是计算机解决问题的基础l l 程序是把算法用计算机程序设计语言程序是把算法用计算机程序设计语言表表示
