算法设计与分析教案.pdf

《算法设计与分析教案.pdf》由会员分享，可在线阅读，更多相关《算法设计与分析教案.pdf（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、(完整 word 版)算法设计与分析教案_教案(新格式)BX09031、封面上海电机学院教学方案上海电机学院教学方案20112012 学年第 2 学期开课学院电子信息学院课程名称算法设计与分析教案授课教师 授课对象(专业）软件工程（班级）BX0903课程性质专业基础课（填公共基础课、专业基础课或专业课）考核方式考试总 学 时 64/16学分 3审核 _2012年 2月 10日(完整 word 版)算法设计与分析教案_教案(新格式)BX09032、第二页所用教材名称与作者:计算机常用算法与程序设计案例教程（高等学校计算机专业教材精选 算法与程序设计）杨克昌编著 清华大学出版社,2011。主要参考

2、教材:1.程序设计与算法语言-C+程序设计基础（21 世纪面向工程应用型计算机人才培养规划教材)作者：孔丽英，夏艳，徐勇等清华大学出版社 2011 年9 月;2。算法设计与分析（普通高校本科计算机专业特色教材精选算法与程序设计 作者：张军等编著清华大学出版社 2011 年 8 月。本课程与授课专业的关系、目的与要求:本课程的教学目的是使学生能够掌握算法的基本理论、技术和应用算法的基本方法。在算法研究和应用领域内，提高分析问题和解决问题的能力，同时为后续课程的学习和将来在实际工作中的应用打下扎实的基础.(完整 word 版)算法设计与分析教案_教案(新格式)BX09033、内容上海电机学院教案上

3、海电机学院教案周次周次_1_1_第第_1_1_次课次课学时学时_2_2 课时课时_ _授课时间授课时间 2 2 月月章节名称章节名称本次授课目的与要求本次授课目的与要求教学要求教学要求第 1 章 算法与程序设计概述1.了解算法概念、算法特征及算法的描述2.建立算法的复杂性概念3.掌握结构化程序设计的基本方法本次教学重点与难点本次教学重点与难点1.应用 c 语言描述算法2.掌握算法时间复杂度分析授课方法与手段授课方法与手段教学手段：教学手段：媒体课件与启发式相结合教学课时教学课时:2 课时(完整 word 版)算法设计与分析教案_教案(新格式)BX0903本次教学内容提要及时间分配（可加页本次教

4、学内容提要及时间分配（可加页)一一 新课引入新课引入(通过实际应用中最熟悉的各种算法实例,引出算法的概念）1.1 算法及其描述算法（algorithm)一个算法是对特定问题求解步骤的一种描述,它是指令的有限序列.此外，算法具有下列 5 个特征:输入（input):算法有零个或多个输入量;输出（output）：算法至少产生一个输出量；确定性（definiteness)：算法的每一条指令都有确切的定义，没有二义性；能行性（effectiveness):算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现;有穷性（finiteness）：算法必须总能在执行有限步之后终止。二二

5、 讲授新课讲授新课1。1。1算法定义算法是计算机解决问题的过程，是解决某一问题的运算序列。或者说算法是问题求解过程的运算描述.当面临某一问题时，需要找到用计算机解决这个问题的方法与步骤，算法就是解决这个问题的方法与步骤的描述。1.1.2算法描述(1)一个问题可以设计不同的算法来求解；同一个算法可以采用不同的形式来表述。（2)描述算法可以有：自然语言方式、流程图方式、伪代码方式、计算机语言表示方式与表格方式等。(3）当一个算法使用计算机程序设计语言描述时，就是程序.采用 C 语言与自然语言相结合来描述算法。例 11求两个整数 a，b 的最大公约数的欧几里德算法(1)数 a 除以 b 得余数 r;

6、若 r=0，则 b 为所求的最大公约数.（2）若 r0，以 b 为 a，r 为 b,继续(1).欧几里德算法具体描述如下：input（a,b)；/输入的简略表示r=a%b;while（r！=0）/实施辗转相除 a=b;b=r；r=ab;print（b）；/输出的简略表示(完整 word 版)算法设计与分析教案_教案(新格式)BX09031.2算法的复杂性分析算法的复杂性越高,所需的计算机资源越多。最重要的计算机资源是时间资源与空间资源。需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间复杂度。时间复杂度与空间复杂度集中反映算法的效率。1.2。1时间复杂度一个算法的时间复杂度是

7、指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句（运算)的多少。算法的时间复杂度通常用该算法执行的总语句(运算)的数量级决定。一条语句的数量级即执行它的频数,一个算法的数量级是指它所有语句执行频数之和。在分析算法时，隐藏细节的数学表示方法为大写字母“O”记法，它可以帮助我们简化算法复杂度计算的许多细节,提取主要成分.算法的执行频数的数量级直接决定算法的时间复杂度。1.2.2空间复杂度算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。一个程序运行所需的存储空间通常包括固定空间需求与可变空间需求两部分。（1）固定空间需求包括程序代码、常量与静态变量等所占的空间

8、。（2）可变空间需求包括局部作用域非静态变量所占用的空间、从堆空间中动态分配的空间与调用函数所需的系统栈空间等。1.3 算法与程序设计1.3。1 算法与程序（1）计算机的一切操作都是由程序控制的，离开了程序，计算机将一事无成.从(完整 word 版)算法设计与分析教案_教案(新格式)BX0903这个意义来说，计算机的本质是程序的机器，程序是计算机的灵魂。（2）算法是程序的核心。程序是某一算法用计算机程序设计语言的具体实现。一个程序应包括对数据的描述与对运算操作的描述两个方面的内容.数据结构+算法=程序数据结构是对数据的描述;算法是对运算操作的描述。1。3。2结构化程序设计任何简单或复杂的算法都

9、可以由顺序结构、选择结构和循环结构这三种基本结构组合而成。所以,顺序结构、选择结构和循环结构被称为程序设计的三种基本结构，也是结构化程序设计必须采用的结构。结构化程序设计的基本要点：（1）自顶向下，逐步求精(2）模块化设计（3）结构化编码逐步求精总是和自顶向下结合使用，将问题求解逐步具体化的过程，一般把逐步求精看作自顶向下设计的具体体现。模块化是结构化程序设计的重要原则。一个程序是由一个主控模块和若干子模块组成。主控模块用来完成某些公用操作及功能选择;而子模块用来完成某项特定的功能。作业布置作业布置1.分数分解算法描述,把真分数 a/b 分解为若干个分母为整数分子为“1”的埃及分数之和；2.据

10、例 12 的算法,写出求解 n 个“1组成的整数能被 2011 整除的程序。修改程序，求出 n 至少为多大时，n 个“1组成的整数能被 2013 整除?。课外复习、预习内容安排课外复习、预习内容安排预习第 2 章(完整 word 版)算法设计与分析教案_教案(新格式)BX0903主要参考文献资料主要参考文献资料程序设计与算法语言-C+程序设计基础（21 世纪面向工程应用型计算机人才培养规划教材）作者:孔丽英，夏艳，徐勇等清华大学出版社 2011 年9 月；教学后记教学后记学生对算法复杂度理解，理解不够深入，需要加强.备注备注(完整 word 版)算法设计与分析教案_教案(新格式)BX0903周

11、次周次_2_23_3_第第_2_2，3,4_3,4_次课次课学时学时_6_6 课时课时_ _授课时间授课时间 3 3 月月章节名称章节名称本次授课目的与要求本次授课目的与要求教学要求教学要求1.了解枚举算法的概念与枚举设计要领2.应用枚举求解统计求和与求最值等基本案例第 2 章 关系数据库本次教学重点与难点本次教学重点与难点1.对某些枚举算法进行改进与优化2.掌握枚举算法时间复杂度分析授课方法与手段授课方法与手段教学手段教学手段:媒体课件与启发式相结合教学课时：教学课时：6 课时(完整 word 版)算法设计与分析教案_教案(新格式)BX0903本次教学内容提要及时间分配（可加页本次教学内容提

12、要及时间分配（可加页)复习要点复习要点:算法概念、算法复杂度概念引入新课：引入新课：2 2。1 1 枚举概述枚举概述1。枚举的概念(1)枚举法（Enumerate）也称为列举法、穷举法,是蛮力策略的体现，又称为蛮力法.（2）枚举是一种简单而直接地解决问题的方法，其基本思想是逐一列举问题所涉及的所有情形。（3）应用枚举时应注意对问题所涉及的有限种情形进行一一列举，既不能重复，又不能遗漏。2。枚举的框架描述n=0;for（k=;k+)/控制枚举范围 if()/根据约束条件实施筛选 printf(m1 退出循环，赋值 c=i，所得 c 为 n 解区间的下限。继续在 s=m2 的条件循环中，根据递增变

13、量i 对 s 累加求和，直至出现sm2 退出循环，通过赋值 d=i1，所得 d 为 n 解区间的上限.注意,解的上限是 d=i-1,而不是 i。然后打印输出不等式的解区间c，d。2.52.5 求最值求最值整数的因数比案例提出：设整数 a 的小于其本身的因数之和为 s,定义 p(a)=s/a(完整 word 版)算法设计与分析教案_教案(新格式)BX0903为整数 a 的因数比。试求指定区间 x,y中整数的因数比最大值。枚举设计要点为了求整数 a 的因数和 s，显然 1 是因数.设置 k(2sqrt(a）循环枚举，如果 k 是 a 的因数，则 a/k 也是 a 的因数。显然 ka/k。如果 a=

14、bb，显然 k=b,a/k=b，此时 k=a/k。而因数 b 只有一个，所以此时必须从和 s 中减去一个 b,这样处理以避免重复.设置 max 存储因数比最大值。枚举区间内每一整数 a，求得其因数和 s。通过 s/a 与 max 比较求取因数比最大值。2 2。6 6 数组与数列数组与数列基于 2x+3y 的递推数列案例提出：已知集合 A 定义如下：（1）1A，2A（2）x，yA 且 xy=2x+3yA（3）再无其他数属于 A。试求集合 A 中元素从小到大排列序列的第 n 项。设置 a 数组存储序列各项,a(t)为序列的第 t 项。显然 a(1)=1,a(2）=2.设 t 为项数，在 tn 的条

15、件循环中，变量 k 从 2 开始递增 1 取值。若 k 可由已有的项 a(j），a（i)（ji）推得,即若 k 满足 k=2a（j）+3*a(i）或 k=2a（i)+3a(j），说明 k 是 a 数列中的一项，赋值给 a（t）。当项数 t 达到规定项数 n 时，则退出循环，打印输出 a（n)后结束。2.72.7数式探求数式探求完美综合式案例提出：把数字 1，2，。.,9 这 9 个数字分别填入以下含加、减、乘、除与乘方（）的综合运算式中的 9 个中+-=0要求数字 1,2,。.。，9 这 9 个数字在式中出现一次且只出现一次，且约定数字“1”不出现在乘、乘方的一位数中。枚举设计要点设置整数变量

16、，其中 ab 用 a 自乘 b 次实现.即要求的综合运算式为:ab+z/c-d*e=0设置 a,b,c,d,e 循环，对每一组 a，b，c,d,e，计算 z=(deab)*c，省略 z 循环。检测 z 是否为二位数。若 z 非二位数，则返回.对 6 个整数进行数字分离,设置 f 数组对分离的 9 个数字进行统计，f(x)即为数字 x(19)的个数。(完整 word 版)算法设计与分析教案_教案(新格式)BX0903若某 f（x）不为 1,标记 t=1，则返回。若所有 f（x)全为 1,保持标记 t=0，则输出。2.8 2.8趣味数阵趣味数阵自学,可选为课程设计题材.2 2。9 9 枚举应用小结

17、枚举应用小结应用枚举求解，在设计上比较简单，不存在太多难点，但决不可太随意。从本章诸案例的枚举设计求解可以看出，枚举思路的调整、枚举规律的归纳、枚举结构的设置与枚举参量的选择，都有一定的技巧运用,自然也存在许多改进与优化的空间.1.简化计算，调整思路求解案例，根据案例的具体实际确定枚举方案的过程中，简化计算流程，调整求解思路。2.观察归纳,寻求规律面对一个具体案例,通过反复的观察、比较、归纳、总结,找出一般规律，才能确立求解思路与算法。3。减少重复,优化结构在进行枚举设计时,优化枚举结构，减少重复操作，可望在降低枚举的时间复杂度方面收到好的成效.4.细化操作,精简参数枚举结构确定之后，根据案例

18、的具体实际确定合适的参数，是缩减无效操作，提高枚举效率的重要一环.作业布置作业布置1.解不等式,设n为正整数，解不等式,20101111 201111/211/21/311/21/n.2.分解质因数,对给定区间m,n的正整数分解质因数，每一整数表示为质因数从小到大顺序的乘积形式.如果被分解的数本身是素数，则注明为素数。3.特定数字组成的平方数,用数字 2,3，5,6,7，8,9 可组成多少个没有重复数字的 7 位平方数？4.四则运算式，把数字 1,2,。，9 这 9 个数字填入以下含加减乘除的综合运算式中的 9 个中，使得该式成立+=0，要求数字 1,2,。.,9 这 9 个数字在各式中都出现

19、一次且只出现一次，且约定数字“1”不出现在数式的一位数中(即排除各式中的各个 1 位数为 1 这一平凡情形）.5.最小连续 n 个合数，试求出最小的连续 n 个合数。（其中 n 是键盘输入的任意正整数。）(完整 word 版)算法设计与分析教案_教案(新格式)BX0903课外复习、预习内容安排课外复习、预习内容安排预习第 3 章主要参考文献资料主要参考文献资料程序设计与算法语言C+程序设计基础(21 世纪面向工程应用型计算机人才培养规划教材）作者：孔丽英，夏艳，徐勇等清华大学出版社 2011 年9 月；教学后记教学后记加强用枚举法解决问题的能力.备注备注(完整 word 版)算法设计与分析教案

20、_教案(新格式)BX0903周次周次_45_45_第第_5_5，6,7_6,7_次课次课学时学时_6_6 课时课时_ _授课时间授课时间 3 3 月月章节名称章节名称本次授课目的与要求本次授课目的与要求教学要求教学要求1、2、第 3 章 递 推了解递推算法的概念与各类递推设计要领应用递推算法求解典型的数列与数阵案例本次教学重点与难点本次教学重点与难点1、对某些实际问题设计多种递推算法2、对某些递推算法进行改进与优化授课方法与手段授课方法与手段教学手段：教学手段：媒体课件与启发式相结合教学课时：教学课时：6 课时(完整 word 版)算法设计与分析教案_教案(新格式)BX0903本次教学内容提要

21、及时间分配（可加页）本次教学内容提要及时间分配（可加页）复习要点：枚举概念、枚举算法的步骤引导授新（第 3 章 递推）3。1递推概述1.递推的概念(1）递推是利用问题本身所具有的递推关系求解问题的一种方法,是在命题归纳时，可以由 n k，,n 1 的情形推得 n 的情形.（2)递推算法的基本思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法充分利用了计算机的运算速度快和不知疲倦的特点，从头开始一步步地推出问题最终的结果。（3)一个有规律的序列的相邻位置上的项之间通常存在着一定的关系，可以借助已知的项，利用特定的关系逐项推算出它的后继项的值，直到找到所需的那一项为止.2。递推关系递

22、推算法的首要问题是得到相邻的数据项之间的关系,即递推关系.（1）递推关系是一种高效的数学模型，是递推应用的核心。(2）递推关系不仅在各数学分支中发挥着重要的作用,由它所体现出来的递推思想在各学科领域中更是显示出其独特的魅力.3。递推的实施步骤（1)确定递推变量递推变量可以是简单变量，也可以是一维或多维数组.（2)建立递推关系递推关系是递推的依据，是解决递推问题的关键。（3）确定初始（边界）条件根据问题最简单情形的数据确定递推变量的初始（边界）值，这是递推的基础。（4）对递推过程进行控制递推过程控制：递推在什么时候结束，满足什么条件结束。4。递推算法框架描述（1)简单顺推算法顺推即从前往后推,从

23、已求得的规模为 1，2，,i-1 的一系列解，推出问题规模为 i 的解，直至得到规模为 n 的解：f（1-i1）=；/根据递推关系实施顺推print（f(n)）；/输出 n 规模的解 f(n）(完整 word 版)算法设计与分析教案_教案(新格式)BX0903(2）简单逆推算法逆推即从后往前推，从已求得的规模为n,n1,，i+1 的一系列解，推出问题规模为 i 的解，直至得到规模为 1 的解：f（n-i+1）=初始值；for(k=i；k=1;k)f（k）=递推关系式；/实施逆推print（f（1）)；（3）较复杂的递推问题需设置多重循环递推.（4）多关系分级递推算法当递推关系包含两个或两个以上

24、关系式时,通常应用多关系分级递推算法求解.f（1：i1)=;/赋初始值for（k=i;k=n;k+）if(;/根据关系 1 递推 if(条件 m）f(k)=3）（2）确定初始条件f(1）=1；即 1=1f（2)=1；即 2=1+1f（3）=2；即 3=1+1+1；3=3应用递推求解，关键在于根据问题的具体实际进行归纳与探索，寻求与确定符合实际的递推关系，这既是重点，也是难点。作业布置作业布置1.递推求解 b 数列，已知 b 数列定义：b11,b2 2,bn 3bn1bn2(n 2),递推求b 数列的第 20 项与前 20 项之和。2.xyzM 2,3,5|x 0,y 0,z 0，多幂序列，设

25、x,y，z 为非负整数，试计算集合的元素由小到大排列的多幂序列第 n 项与前 n 项之和。3.粒子裂变，核反应堆中有和两种粒子,每秒钟内一个粒子可以裂变为3 个粒子，而一个粒子可以裂变为 1 个粒子和 2 个粒子。若在 t=0时刻的反应堆中只有一个粒子，求在 t 秒时反应堆裂变产生的粒子和粒子数。4.猴子吃桃。5.据例 3-1 中求裴波那契数列的第 40 项与前 40 项之和的递推算法与迭代算法,写出完整的程序，并比较其运行结果。课外复习、预习内容安排课外复习、预习内容安排预习第 4 章主要参考文献资料主要参考文献资料程序设计与算法语言C+程序设计基础（21 世纪面向工程应用型计算机人才培养规

26、划教材）作者：孔丽英,夏艳,徐勇等清华大学出版社 2011 年-9 月；教学后记教学后记加强对枚举算法举一反三的应用。备注备注(完整 word 版)算法设计与分析教案_教案(新格式)BX0903周次周次_67_67_第第_9_9，1010，11_11_次课次课学时学时 6 6 课时课时_ _授课时间授课时间 4 4 月月章节名称章节名称本次授课目的与要求本次授课目的与要求教学要求教学要求1、2、3、第 4 章 递归了解递归算法的概念与递归设计要领掌握应用递归算法求解排序与选择、实现排列组合等典型案例了解递归算法中的回溯过程本次教学重点与难点本次教学重点与难点递归关系与边界条件的探求与确定授课方

27、法与手段授课方法与手段教学手段：教学手段：媒体课件与启发式相结合教学课时：教学课时：6 课时(完整 word 版)算法设计与分析教案_教案(新格式)BX0903本次教学内容提要及时间分配（可加页）本次教学内容提要及时间分配（可加页）4.14.1递归概述递归概述1。递归的概念(1）递归（Recursion)是一个过程或函数在其定义中直接或间接调用自身的一种方法，就是利用系统堆栈，实现函数自身调用或相互调用的过程。在通往边界的过程中，都会把单步地址保存下来，再按照先进后出进行运算。(2）递归算法通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题,是分治策略的具体体现。(3)递归需要有递归

28、关系式与边界条件,递归过程有递归前进段和递归返回段。当边界条件不满足时,递归前进；当边界条件满足时，递归返回。2.递归方法基本步骤（1）根据实际构建递归关系（2）确定递归边界(3)编写递归函数（4)设计主函数调用递归函数3.举例说明例 41用递归法计算 n！计算整数 n 的阶乘 n！是一个典型的递归问题。使用递归方法来描述程序,十分简单且易于理解。（1）描述递归关系注意到,当 n1 时，n!=n(n 1)!,这就是一种递归关系.对于特定的 k!，它只与k 和(k 1)!有关。（2）确定递归边界递归边界为：n=1 时，n！=1。对于任意给定的 n,程序将最终求解到 1！。递归调用的实现主函数调用

29、 f(n)后即进入函数 f(n）执行。设执行本程序时输入为 n=5，即求 5!。在主函数中的调用语句即为 y=f(5），执行 f 函数，由于n=5，不等于1，故应执行g=n*f（n 1），即 g=5f(4)。该语句调用 f(4)，进行 4 次递归调用后,f 函数参数值变为 1,故不再继续递归调用而开始逐层返回主调函数。f（1)的函数返回值为 1，f（2)的返回值为 21=2，f(3）的返回值为 32=6，f(4)的返回值为 46=24，最后返回值 f（5)为 524=120。4 4。2 2排队购票排队购票案例提出:一场球赛开始前，售票工作正在紧张进行中。每张球票为50 元，有m+n 个人排队等

30、待购票，其中有 m 个人手持 50 元的钞票，另外 n 个人手持 100 元的钞票.求出(完整 word 版)算法设计与分析教案_教案(新格式)BX0903这 m+n 个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数。（约定：开始售票时售票处没有零钱，拿同样面值钞票的人对换位置为同一种排队。）递归设计要点令 f(m，n)表示有 m 个人手持 50 元的钞票，n 个人手持 100 元的钞票时共有的排除总数。分以下 3 种情况来讨论.（1)n=0 n=0 意味着排队购票的所有人手中拿的都是 50 元的钱币,注意到拿同样面值钞票的人对换位置为同一种排队，那么这 m 个人的排队总数为 1，即

31、 f（m,0）=1。（2）mn当 mn 时，即购票的人中持 50 元的人数小于持 100 元的钞票,即使把 m 张 50元的钞票都找出去，仍会出现找不开钱的局面，这时排队总数为0，即f（m,n）=0。（3）其它情况 1）第 m+n 个人手持 100 元的钞票，则在他之前的 m+n-1 个人中有 m 个人手持50 元的钞票,有 n1 个人手持 100 元的钞票,此种情况共有 f(m,n1)。2）第 m+n 个人手持 50 元的钞票，则在他之前的 m+n-1 个人中有 m1 个人手持 50 元的钞票，有 n 个人手持 100 元的钞票，此种情况共有 f（m1，n）。由加法原理得到 f(m，n）的递

32、归关系:f(m，n）=f（m,n-1）+f（m1，n)初始条件：当 mn 时,f（m，n)=0当 n=0 时,f(m，n)=14.34.3汉诺塔问题汉诺塔问题案例提出：汉诺塔（Hanoi）问题，又称河内塔问题。（1）有三根桩子 A、B、C。A 桩上有 n 个圆盘,最大的一个在底下，其余一个比一个小，依次叠上去。（2）每次移动一块圆盘，小盘的只能叠在大盘的上面。(3)把所有圆盘从 A 桩全部移到 C 桩上，（如图 4-1）。试求解 n 个圆盘 A 桩全部移到 C 桩上的移动次数，并展示 n 个圆盘的移动过程。4.34.3。1 1求移动次数求移动次数递归设计要点当 n=1 时，只一个盘,移动一次即

33、完成。当 n=2 时，首先把小盘从A 桩移到 B 桩；然后把大盘从A 桩移到 C 桩；最后把小盘从 B 桩移到 C 桩，移动 3 次完成。(完整 word 版)算法设计与分析教案_教案(新格式)BX0903设移动 n 个盘的汉诺塔需 g(n）次完成。分以下三个步骤:(1）先将上面 n-1 个盘借助 C 从 A 移到 B 上，需 g（n1）次;(2）然后将 A 桩上第 n 个盘子移到 C 桩上（1 次）；(3）最后将 B 桩上的 n1 个盘子借助 A 移到 C，需 g（n1)次。因而有递归关系:g（n）=2*g（n-1)+1初始条件(递归出口）：g（1）=14.34.3。2 2展示移动过程展示移

34、动过程递归设计要点设递归函数 hn（n,a,b,c)展示把 n 个盘从 A 桩借助 B 桩移到 C 桩的过程,函数mv(a,c)输出从 a 桩到 c 桩的过程：A-C。完成 hn（n，a，b,c）,当 n=1 时，即 mv（a,c）。当 n1 时,分以下三步：（1）将 A 上面的 n-1 个盘借助 C 移到 B，即 hn（n1,a,c,b）；（2)将 A 桩上第 n 个盘子移到 C 桩上，即 mv（a,c）；（3)将 B 的 n-1 个盘借助 A 移到 C，即 hn（n-1,b,a,c）。主程序 hn(m，1,2，3）带实参 m，1,2,3 调用 hn(n，a,b，c)，这里 m 为具体移动盘

35、子的个数.4.54.5速排序与选择速排序与选择1。逐项比较排序最简单的排序是把存放在数组的 n 个数据逐个比较，必要时进行数据交换。n 项逐项比较排序进行升序排序的算法描述如下：for(i=1；i=n-1;i+)for（j=i+1;j=n；j+）if(ri rj)t=ri；ri=rj;rj=t;逐项比较排序的时间复杂度为 O（n2）。2。快速排序快速排序思路快速排序又称为分区交换排序，其基本思想是分治,即分而治之：在待排序的 n个数据 r1，2，,n中任取一个数（例如 r1）作为基准，把其余n1 个数据分为两个区，小于基准的数放在左边，大于基准的数放在右边。这样分成的两个区实际上是待排序数据的

36、两个子列。然后对这两个子列分别重复上述分区过程，直到所有子列只有一个元素，即所有元素排到位后，输出排序结果.快速排序的时间复杂度分析(完整 word 版)算法设计与分析教案_教案(新格式)BX09033.分区交换选择1）选择问题在一个无序序列 r(1）,r(2),r（n）中，寻找第 k 小元素的问题称为选择。这里第 k 小元素是序列按升序排列后的第 k 个元素.特别地，当 k=n/2 时，即寻找位于 n 个元素中的中间元素，称为中值问题。2)选择问题的分区交换设计参照上述分区交换的快速排序算法，在待选择的 n 个数据 r1，2,n中任取一个数（例如r1）作为基准，把其余n-1 个数据分为两个区

37、，小于基准的数放在左边，大于基准的数放在右边，基准定位在 s，则(1)若 s=k，基准数即为所寻求的第 k 小元素。（2)若 sk，可知左边小于该基准数的个数s1k,则在左边的子区继续分区.(3）若 sk，可知所寻求的第 k 小元素在右边子区，则在右边的子区继续分区.依此（2）（3）继续，直到出现（1）结束，输出结果.3)快速选择的时间复杂度分析4.64.6 排列组合的实现排列组合的实现排列组合是组合数学的基础，从 n 个不同元素中任取 m 个，约定 1mn,按任意一种次序排成一列，称为排列，其排列种数记为 A（n,m）.从 n 个不同元素中任取 m 个(约定 1mn)成一组,称为一个组合，其

38、组合种数记为 C（n,m）。计算 A(n，m）与C（n,m)只要简单进行乘运算即可，要具体展现出排列的每一列与组合的每一组,决非轻而易举。本节应用递归设计来具体实现排列与组合。4 4。6 6。1 1实现排列实现排列 A(nA(n，m)m)(完整 word 版)算法设计与分析教案_教案(新格式)BX09031.递归设计要点递归函数 p（k)的变量 k 从 1 开始取值。当 km 时，第 k 个数 a(k)取 i(1n)，并标志量 u=0.（1）若 a(k）与其前面已取的数 a(j)（jk）比较，出现a（k)=a(j），即第 k个数取 i 不成功，标志量 u=1.（2）若a（k）与所有前面已取的a

39、（j）比较，没有一个相等，则第k 个数取 i成功，标志量保持 u=0，然后判断：1）若 k=m，即已取了 m 个数，输出这 m 个数即为一个排列,a（k）继续从 i+1开始，在余下的数中取一个数。直到全部取完，则返回上一次调用p（k)处，即回溯到 p(k-1），第 k1 个数继续往下取值.2）若 k=aj”即可实现从 n 个不同元素中取 m 个（约定 1mn）的组合 C(n，m)。这样修改实现组合的取值次数、判别次数均与实现排列相同，做了大量无效操作，效率太低。1.实现组合递归设计约定组合中的组成元素递增排序，实现 a 数组取值的 i 循环设置为:for(i=ak1+1；i1），设计求 n!的

40、递归函数，调用该函数求s 111!11.2!n!2.递归求解 b 数列，已知 b 数列定义:b11,b2 2,bn 3bn1 2bn2(n 2)，建立b 数列的递归函数，求 b 数列的第 n 项与前 n 项之和。3.应用递归设计输出杨辉三角.4.试应用递归设计构造并输出任意指定逆转 mn 矩阵.课外复习、预习内容安排课外复习、预习内容安排预习第 5 章主要参考文献资料主要参考文献资料程序设计与算法语言C+程序设计基础(21 世纪面向工程应用型计算机人才培养规划教材）作者：孔丽英，夏艳，徐勇等清华大学出版社 2011 年-9 月；(完整 word 版)算法设计与分析教案_教案(新格式)BX090

41、3教学后记教学后记搞清递推和递归的区别，设计递归算法的具体应用,需要加强实践.备注备注(完整 word 版)算法设计与分析教案_教案(新格式)BX0903周次周次_89_89_第第_12_12，13,14_13,14_次课次课学时学时_6_6 课时课时_ _授课时间授课时间 4 4章节名称章节名称本次授课目的与要求本次授课目的与要求教学要求教学要求1、了解回溯算法的概念与回溯设计要领2、掌握应用回溯算法求解桥本分数式、素数环、数码串珠以及情侣拍照等典型案例3、掌握 n n皇后问题第 5 章 回溯本次教学重点与难点本次教学重点与难点理解回溯法“向前走,碰壁回头的实现授课方法与手段授课方法与手段教

42、学手段：教学手段：媒体课件与启发式相结合教学课时：教学课时：6 课时(完整 word 版)算法设计与分析教案_教案(新格式)BX0903本次教学内容提要及时间分配（可加页）本次教学内容提要及时间分配（可加页）5.15.1 回溯概述回溯概述1。回溯的概念（1)回溯法（Back track method）有“通用解题法”之美称，是一种比枚举“聪明”的效率更高的搜索技术。（2）回溯法是一种试探求解的方法：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若试探成功,即得到解；若试探失败，就逐步往回退，换其他路线再往前试探.(3)回溯法可以形象地概括为“向前走，碰壁回头”，若再往前走

43、不可能得到解，就回溯,退一步另找线路，这样可省去大量的无效操作，提高搜索效率。2。回溯实现回溯法的试探搜索，是一种组织得井井有条的、能避免一些不必要搜索的枚举式搜索。回溯法在问题的解空间树中,从根结点出发搜索解空间树，搜索至解空间树的任意一点，先判断该结点是否包含问题的解；如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其父结点回溯;否则，进入该子树,继续搜索.从解的角度理解，回溯法将问题的候选解按某种顺序进行枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。若当前候选解除了不满足问题规模要求外，满足所有其他要求时,

44、继续扩大当前候选解的规模，并继续试探.如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解。3。回溯剖析与描述（1）回溯求解的问题 P：对于已知的由 n 元组（x1,x2，xn）组成的一个状态空间 E=(x1,x2，xn)xisi，i=1,2，n，给定关于 n 元组中的约束集 D，要求E 中满足 D的全部约束条件的所有 n 元组.对于约束集 D 具有完备性的问题 P，一旦检测断定某个 j 元组(x1,x2，xj）违反 D 中仅涉及 x1，x2,xj 的一个约束，就可以肯定，以(x1，x2，,xj）为前缀的任何 n 元组(x1，x2,xj，xj+1,，xn)都不会是问题 P

45、的解,因而就不必去搜索它们，省略了对部分元素（xj+1，xn)的操作与测试.（2)回溯描述对于一般含参量 m,n 的搜索问题，输入正整数 n，m,（nm）i=1；ai=元素初值;while（1)for（g=1,k=i-1；k=1;k-）if（)g=0;/检测约束条件，不满足则返回 if(g&约束条件 2)printf（a1：m);/输出解(完整 word 版)算法设计与分析教案_教案(新格式)BX0903 if（in&g)i+;ai=&i1）i-;/向前回溯 if(ai=n&i=1）break;/退出循环,结束 else ai=ai+1;4皇后问题的回溯举例如何在 44 的方格棋盘上放置 4

46、个皇后,使它们互不攻击：5.皇后问题回溯描述i=1;ai=1;while（1）g=1;for(k=i1;k=1;k-）if（ai=ak abs（ai-ak）=ik）g=0；/检测约束条件，不满足则返回 if（g i=4）printf(a1：4）;/输出一个解 if（i4&g）i+；ai=1；continue;while(ai=4 i1)i;/向前回溯 if(ai=4&i=1）break；/退出循环结束探索 else ai=ai+1；5 5。2 2 桥本分数式桥本分数式案例提出:日本数学家桥本吉彦教授于1993年10月在我国山东举行的中日美三国数学教育研讨会上提出以下填数趣题:把 1，2,，9这

47、 9 个数字填入下式的 9 个方格中（数字不得重复），使下面分数等式成立:+=桥本教授当即给出了一个解答。这一填数趣题的解是否唯一？如果不唯一究竟(完整 word 版)算法设计与分析教案_教案(新格式)BX0903有多少个解？试求出所有解答（等式左边两个分数交换次序只算一个解答)。回溯设计要点设置 a 数组，式中每一位置用一个数组元素表示：为避免解重复，设 a（1)1 时 a(i）增 1 继续，至 a(i）=s-n+i 时回溯。变量 s 与 n 的值从键盘输入。运行程序时，选择 s 是从 n（n1)+1 开始，逐减取值输入，最先所得解为对应 n 的 s 最大值。然后再从这些解中选取没有相同整数

48、的解。5 5。4 4 逐位整除数探索逐位整除数探索5.45.4。1 1高逐位整除数：高逐位整除数：案例提出:n 位高逐位整除数：从其高位开始，高 1 位能被 1 整除（显然),高 2 位能被 2 整除,，整个 n 位数能被 n 整除。例如 10245 就是一个 5 位高逐位整除数。对于指定的正整数 n，共有多少个不同的 n 位高逐位整除数？存在 n 位高逐位整除数的 n 是否有最大值？试探索指定的 n 位高逐位整除数，输出所有 n 位高逐位整除数.1.回溯设计要点设置 a，数组，存放求解的高逐位整除数的各位,a1存储最高位数字，a2存储次高位数字，an存储 n 位数的个位数字。(完整 word

49、 版)算法设计与分析教案_教案(新格式)BX0903在 a 数组中，数组元素 a1从 1 开始取值，显然能被 1 整除;a2从 0 开始取值，存放第 2 位数,前 2 位即 a1*10+a2能被 2 整除；。为了判别已取 i 位数能否被 i 整除，设置 j 循环：for(r=0,j=1；j=i；j+）r=r*10+aj；r=r%i；（1）若 r=0,即该 i 位数能被 i 整除,取标志量 t=0；此时有两个选择：若已取了 n 位，则输出一个 n 位逐位整除数；最后一位增 1 后继续.若不未到 n 位,则 i=i+1 继续探索下一位。（2）若 r0，即前 i 位数不能被 i 整除，取标志量 t=

50、1。此时 a i=ai+1，即第 i 位增 1 后继续.若增值至 ai9，则 ai=0 即该位清“0后,i=i1 回溯到前一位。直到第 1 位增值超过 9 后，退出循环结束。该算法可探索并输出所有 n 位逐位整除数，用 s 统计解的个数.若 s=0，说明没有找到 n 位逐位整除数,输出“无解。5.55.5环序列环序列素数和环:案例提出:把前 n 个正整数摆成一个环，如果环中所有相邻的两个数之和都是一个素数，该环称为一个 n 项素数和环。对于指定的 n,构造输出所有不同的素数和环。1.回溯设计 要点设置 a 数组在前 n 个正整数中取值.约定第 1 个数 a1=1。设置 b 数组标记奇素数。对指