算法及其描述.ppt

计算机常用算法与程序设计案例教程杨克昌请用 PowerPoint 2003 播放课堂讲授: 课堂讲授: 学时安排: 36 (讲授)+ 18 (上机) ( 可根据实际教学计划进行调整) 学时安排: 36 (讲授)+ 18 (上机) ( 可根据实际教学计划进行调整) 各常用算法的概念与设计要点。重点讲授应用算法设计求解基本的典型案例,并通过相关程序,引导设计变通。在基本案例引导下自学相关联案例求解。小组讨论与基本案例相关的拓展与引申案例求解,为“课程设计”作准备。上机实践: 上机实践: 学习建议: 学习建议: 学会归纳、总结和提炼; 自觉调整学习状态: 培养案例求解兴趣自觉完成布置的作业加深对算法应用的理解善于变通、拓展与改进注重算法设计,提高解决实际案例的能力。上机环境: VC++ 上机通过每章指定的案例求解程序与习题按要求填写实验报告?教学要求?了解算法概念、算法特征及算法的描述?建立算法的复杂性概念?掌握结构化程序设计的基本方法?本章重点?应用 c 语言描述算法?掌握算法时间复杂度分析第 1 章第第 1 1 章章算法与程序设计概述 算法及其描述算法是程序设计的基础,是计算机科学的核心。算法是程序设计的基础,是计算机科学的核心。 算法定义算法定义算法是计算机解决问题的过程,是解决某一算法是计算机解决问题的过程,是解决某一问题的运算序列。或者说算法是问题的运算序列。或者说算法是问题求解过问题求解过程的运算描述程的运算描述。。当面临某一问题时,需要找到用计算机解决当面临某一问题时,需要找到用计算机解决这个问题的方法与步骤,算法就是这个问题的方法与步骤,算法就是解决这个解决这个问题的方法与步骤的描述问题的方法与步骤的描述。。 1. 算法的三要素??算法由操作、控制结构与数据结构算法由操作、控制结构与数据结构三者组成。三者组成。(1) (1) 操作:算术运算,关系运算,逻辑运操作:算术运算,关系运算,逻辑运算;输入、输出、赋值等操作。算;输入、输出、赋值等操作。(2) (2) 控制结构:顺序结构,选择结构,循环控制结构:顺序结构,选择结构,循环结构,模块调用。结构,模块调用。(3) (3) 数据结构:数据之间的逻辑关系。数据结构:数据之间的逻辑关系。 2. 算法的基本特征??一个算法由有限条可完全机械地执一个算法由有限条可完全机械地执行的、有确定结果的指令组成,具行的、有确定结果的指令组成,具有以下特性: 有以下特性: ??(1) (1) 确定性确定性??(2) (2) 可行性可行性??(3) (3) 有穷性有穷性??(4) (4) 算法有零个或多个输入算法有零个或多个输入??(5) (5) 算法有一个或多个输出算法有一个或多个输出 算法描述( (1 1)一个问题可以设计不同的算法来求解; )一个问题可以设计不同的算法来求解; 同一个算法可以采用不同的形式来表述。同一个算法可以采用不同的形式来表述。( (2 2)描述算法可以有: )描述算法可以有: 自然语言方式、流程自然语言方式、流程图方式、伪代码方式、计算机语言表示方图方式、伪代码方式、计算机语言表示方式与表格方式式与表格方式等等。。( (3 3)当一个算法使用计算机程序设计语言描)当一个算法使用计算机程序设计语言描述时,就是程序。述时,就是程序。本书采用本书采用 C C语言与自然语言相结合来描述算语言与自然语言相结合来描述算法。法。例例 1-1 1-1 求两个整数求两个整数 a,b a,b 的最大公约的最大公约数的欧几里德算法数的欧几里德算法??(1) (1) 数数 a a 除以除以 b b 得余数得余数 r r;若;若 r=0 r=0 ,则,则 b b为为所求的最大公约数。所求的最大公约数。??(2) (2) 若若 r r≠≠0 0,以,以 b b为为a a, ,r r为为b b,继续,继续(1). (1). ??欧几里德算法具体描述如下: 欧几里德算法具体描述如下: ??input(a,b) input(a,b) ; ; // // 输入的简略表示输入的简略表示??r=a%b; r=a%b; ??while(r!=0) while(r!=0) // // 实施辗转相除实施辗转相除?? { a=b; b=r; r=a%b; } { a=b; b=r; r=a%b; } ??print(b); print(b); // // 输出的简略表示输出的简略表示例 1-2 由由n n个个1 1组成的整数能被组成的整数能被 2011