01软件基础徐士良第一章 算法_40学时.ppt

第一章第一章 算法算法计算机软件技术基础计算机软件技术基础2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法21.1 集合的基本概念集合的基本概念1、集合的基本概念：、集合的基本概念：所谓集合，就是指若干个或无所谓集合，就是指若干个或无穷多个具有相同属性的元（元素）的集体。穷多个具有相同属性的元（元素）的集体。集合的两个表示方法：集合的两个表示方法：列举法：列举法：将此集合中的元素全部列举出来，或者将此集合中的元素全部列举出来，或者列出若干项但能根据规律可知其所有的元素，这列出若干项但能根据规律可知其所有的元素，这就是就是列举法列举法；性质叙述法：用性质叙述法表示一个集合是将集性质叙述法：用性质叙述法表示一个集合是将集合中的元素所具有的属性出来。合中的元素所具有的属性出来。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法31.1 算法的基本概念算法的基本概念2、集合的基本运算：、集合的基本运算：两个集合的并两个集合的并两个集合的交两个集合的交两个集合的差两个集合的差2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法41.1 算法的基本概念算法的基本概念2、集合的基本性质：、集合的基本性质：结合律结合律分配律分配律：2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法51.1 算法的基本概念算法的基本概念3、映射、映射设设A、B是两个非空集合，根据一定的法则，对于每是两个非空集合，根据一定的法则，对于每个个 ,在在B中都有唯一确定的元素中都有唯一确定的元素y与之对应，称与之对应，称f是是定义在定义在A上而在上而在B中取值的映射，记为中取值的映射，记为f:A-B,并将并将x与与y的关系记为的关系记为y=f(x)。其中，其中，x称为自变元，称为自变元，y称为称为f作用下作用下x的像。的像。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法61.1 算法的基本概念算法的基本概念2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法7第一章第一章 算法算法1.1 算法的基本概念算法的基本概念1.2 算法设计基本方法算法设计基本方法1.3 算法的复杂度分析算法的复杂度分析什么是算法；什么是算法；算法的基本算法的基本特征。特征。1.列举法；列举法；2.递推法；递推法；3.递递归法；归法；4.减半减半递推法；递推法；5.回回溯法。溯法。算法的算法的时间复时间复杂度。杂度。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法81.1 算法的基本概念算法的基本概念用计算机解决一个实际问题，首先要进行程序设用计算机解决一个实际问题，首先要进行程序设计。通常，计。通常，程序设计主要包括两个方面：程序设计主要包括两个方面：1.行为特性行为特性的设计的设计：要求将解决实际问题的每个细要求将解决实际问题的每个细节准确地加以定义，并且还应当将全部解题过程节准确地加以定义，并且还应当将全部解题过程完整地描述出来，这一过程即是完整地描述出来，这一过程即是算法的设计算法的设计；2.结构特性结构特性的设计：的设计：指确定适合的指确定适合的数据结构数据结构。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法91.1 算法的概念算法的概念定义：定义：“算法算法”是指解题方案的准确而完整的描是指解题方案的准确而完整的描述。述。算法可解算法可解：对于一个问题，如果可以通过一个计对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果。间而得到正确的结果。程序与算法的区别程序与算法的区别：程序可以作为算法一种描述，程序可以作为算法一种描述，但程序通常还需考虑很多与方法和分析无关的细但程序通常还需考虑很多与方法和分析无关的细节问题，因为在编写程序时要受到计算机系统运节问题，因为在编写程序时要受到计算机系统运行环境的限制。行环境的限制。结论结论：通常，程序设计不可能优于算法的设计。：通常，程序设计不可能优于算法的设计。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法101.1.1 算法的基本特征算法的基本特征1.能（可）行性能（可）行性(effectiveness)算法中的每一个步骤必须能够实现。算法中的每一个步骤必须能够实现。算法执行的结果要能够达到预期的目的。算法执行的结果要能够达到预期的目的。例如例如：三个量的和，如果采用不同的运算顺序，就会得到三个量的和，如果采用不同的运算顺序，就会得到不同的结果：不同的结果：数据存储数据存储的实际范围的实际范围2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法112.确定性确定性(definiteness)算法中每一个步骤都必须是有明确定义的，不允算法中每一个步骤都必须是有明确定义的，不允许有许有模棱两可的解释模棱两可的解释，也不允许有，也不允许有多义性多义性。反映了反映了算法算法与与数学公式数学公式的明显差别：的明显差别：针对某种特殊情况，数学公式是正确的，但按针对某种特殊情况，数学公式是正确的，但按此数学公式设计的计算过程可能会使计算机系此数学公式设计的计算过程可能会使计算机系统无所适从。统无所适从。因为没有考虑异常情况的出现。因为没有考虑异常情况的出现。举例举例：“输入一个输入一个x，若若x比比1大很多，则输出大很多，则输出数字数字1，否则输出数字，否则输出数字0。”2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法123.有穷性有穷性(finiteness)算法必须能在有限的时间内做完，即算法必须算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。能在执行有限个步骤之后终止。举例举例：一个数的一个数的无穷级数无穷级数表示只是一个计算公表示只是一个计算公式，而根据精度要求确定的计算过程才是有穷式，而根据精度要求确定的计算过程才是有穷的算法。的算法。另一种定义：另一种定义：合理的执行时间。合理的执行时间。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法13补充补充：无穷级数无穷级数无穷级数无穷级数是研究有次序的可数无穷个数或者函是研究有次序的可数无穷个数或者函数的和的收敛性及和的数值的方法。数的和的收敛性及和的数值的方法。举例举例：假定有一个无穷数列：假定有一个无穷数列：u1，u2，u3，.，un，.其前其前n项的和为：项的和为：Sn=u1+u2+u3+.+un由此得出另一个新无穷数列：由此得出另一个新无穷数列：S1，S2，S3，Sn，.当当n无限增加时，无限增加时，Sn趋向一个极限；趋向一个极限；如果极限存在，这个无穷数列就叫做是如果极限存在，这个无穷数列就叫做是收敛的无收敛的无穷级数穷级数，如果极限不存在，这个数列就是，如果极限不存在，这个数列就是发散的发散的。只有收敛的无穷级数存在一个和只有收敛的无穷级数存在一个和S。S=u1+u2+u3+.+un+.2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法144.拥有足够的情报拥有足够的情报一个算法是否有效还取决于为算法所提供的情报一个算法是否有效还取决于为算法所提供的情报是否足够。是否足够。通常，算法中的各种运算总是要施加到各个运算通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种对象上，而这些运算对象又可能具有某种初始状初始状态，这是算法执行的态，这是算法执行的起点起点或是或是依据依据。因此，一个算法执行的结果总是与因此，一个算法执行的结果总是与输入的初始数输入的初始数据据有关，不同的有关，不同的输入输入会有不同的会有不同的输出输出。当提供的。当提供的情报情报不够时，算法并不是有效的。不够时，算法并不是有效的。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法15结论结论算法是一组严谨地定义运算顺序的规则，并且算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。将在有限的次数下终止。算法是对特定问题求解步骤的一种描述，它是算法是对特定问题求解步骤的一种描述，它是指令的有限序列。指令的有限序列。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法161.1.2 算法的基本要素算法的基本要素算法通常由两种基本要素组成：一是算法通常由两种基本要素组成：一是对数据对象对数据对象的运算和操作的运算和操作；二是；二是算法的控制结构算法的控制结构。1.算法中对数据的运算和操作算法中对数据的运算和操作算术运算：算术运算：加、减、乘、除、加、减、乘、除、整除整除、取余取余等运算；等运算；逻辑运算：逻辑运算：“与与”、“或或”、“非非”等运算；等运算；关关系系运运算算：“大大于于”、“小小于于”、“等等于于”、“不不等于等于”等运算。等运算。数据传输：数据传输：赋值、输入、输出等操作。赋值、输入、输出等操作。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法172.算法的控制结构算法的控制结构定义：定义：算法中各操作之间的执行顺序。算法中各操作之间的执行顺序。描述算法的工具：传统流程图；描述算法的工具：传统流程图；N-S结构化流程结构化流程图；算法描述语言。图；算法描述语言。三种基本控制结构：三种基本控制结构：顺序顺序、选择选择、循环循环。ABABCTFACTF2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法181.2 算法设计的基本方法算法设计的基本方法计算机解题的过程实际上是在实施某种算法，这计算机解题的过程实际上是在实施某种算法，这种算法通常称为种算法通常称为计算机算法计算机算法，与人工处理的算法，与人工处理的算法不同。不同。举例举例：2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法19算法设计的基本方法算法设计的基本方法人工处理的步骤：人工处理的步骤：1.找出被积函数找出被积函数f(x)的源函数的源函数F(x);2.利用牛顿利用牛顿-莱布尼兹公式计算莱布尼兹公式计算 。计算机处理方式：计算机处理方式：采用采用数值积分法数值积分法，根据实际被，根据实际被积函数的类型以及精度要求选择相应的算法。积函数的类型以及精度要求选择相应的算法。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法20列举法列举法基本思想：基本思想：根据提出的问题，列举所有可能的情根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。哪些是不需要的。列举法常用于解决列举法常用于解决“是否存在是否存在”或或“有多少种有多少种可能可能”等类型的问题，等类型的问题，例如例如求解不定方程的问求解不定方程的问题。题。特点：特点：算法比较简单，但当列举的可能情况较多算法比较简单，但当列举的可能情况较多时，执行列举算法的工作量将会很大。时，执行列举算法的工作量将会很大。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法21举例举例：百鸡百钱问题百鸡百钱问题例例1.1：设每只母鸡值设每只母鸡值3元，每只公鸡值元，每只公鸡值2元，两元，两只小鸡值只小鸡值1元。现要用元。现要用100元钱买元钱买100只鸡，设只鸡，设计买鸡方案。计买鸡方案。（百鸡百钱问题）（百鸡百钱问题）假设买母鸡假设买母鸡i只，公鸡只，公鸡j只，小鸡只，小鸡k只。只。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法22最粗略的列举算法如下：最粗略的列举算法如下：算法算法：求解百鸡百钱问题。求解百鸡百钱问题。for i0 to 100 do for j0 to 100 do for k0 to 100 do m=i j k n=3i 2j 0.5k if(m100)and(n100)then output i，j，k returni表示购买的母鸡个只数表示购买的母鸡个只数j表示购买的公鸡个只数表示购买的公鸡个只数k表示购买的小鸡个只数表示购买的小鸡个只数计算购买鸡的总数计算购买鸡的总数m以及总价格以及总价格n2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法23i=0i100j=0j100Tk=0k100T计算鸡的总只数计算鸡的总只数m和购买鸡的总价格和购买鸡的总价格nm=100&n=100输出输出m和和nTk+j+i+TFF结束结束F1013F2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法24改进算法改进算法：求解百鸡百钱问题。求解百鸡百钱问题。for i0 to 33 do for j0 to 501.5i do k=100ij if (3i2j0.5k 100)then output i，j，k return总循环次数为：总循环次数为：运行结果如下：运行结果如下：02 30 6802 30 6805 25 7005 25 7008 20 7208 20 7211 15 7411 15 7414 10 7614 10 7617 5 7817 5 7820 0 8020 0 802022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法25递推递推基本思想：基本思想：从已知的初始条件出发，逐次推出从已知的初始条件出发，逐次推出所要求的各所要求的各中间结果中间结果和和最后结果最后结果。补充举例补充举例：计算下列定积分计算下列定积分递推算法在数值计算中极为常见，递推算法在数值计算中极为常见，但对于数值型的递推算法必须要注但对于数值型的递推算法必须要注意数值计算的稳定性问题。意数值计算的稳定性问题。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法26对上式稍作分析，可以发现相邻两个积分之间对上式稍作分析，可以发现相邻两个积分之间存在以下关系：存在以下关系：从而得到递推公式：从而得到递推公式：2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法27利用利用牛顿牛顿-莱布尼兹公式莱布尼兹公式可以计算出积分可以计算出积分I0的值：的值：从而得到从而得到21个积分的递推算法个积分的递推算法如下：如下：近似值就意近似值就意味着有误差味着有误差假定初始值假定初始值（情报）的（情报）的误差为误差为2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法28表表1.1 第一种递推公式得到的结果第一种递推公式得到的结果2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法29实际上，根据关系式实际上，根据关系式还可以得到另一个递推公式还可以得到另一个递推公式2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法30如果要使用递推公式如果要使用递推公式(1.5)时，需要确定时，需要确定初始值初始值I20。有如下不等式：有如下不等式：可以得到：可以得到：最后可得：最后可得：当当n=21时，有时，有由于由于 很接近，因此可用它们的平很接近，因此可用它们的平均值作为均值作为I20的近似值，即的近似值，即近似值就意近似值就意味着有误差味着有误差2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法31根据之前的推论，可以得到第二种根据之前的推论，可以得到第二种21个积分的个积分的递推算法递推算法：假定初始值假定初始值（情报）的（情报）的误差为误差为2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法32表表1.2 第二种递推公式得到的结果第二种递推公式得到的结果递推算法在数值计算中极为常见，递推算法在数值计算中极为常见，但对于数值型的递推算法必须要注但对于数值型的递推算法必须要注意数值计算的稳定性问题。意数值计算的稳定性问题。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法33递归递归基本思想：基本思想：将一个复杂的问题归结为若干个较将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题，这个过程可以一直做再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。下去，直到最简单的问题为止。补充举例补充举例：求解求解Hanoi塔问题。塔问题。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法34补充举例补充举例：求解求解Hanoi（汉诺）塔问题。汉诺）塔问题。设有三个塔座分别为设有三个塔座分别为X、Y、Z。现有现有n个直径各不相个直径各不相同的圆盘，且按直径同的圆盘，且按直径从小到大从小到大用自然数编号为用自然数编号为1，2，n。开始时，此开始时，此n个圆盘依个圆盘依下大上小的顺序下大上小的顺序放放在塔盘在塔盘X上。先要根据下列原则将上。先要根据下列原则将X塔座塔座上的这上的这n个个圆盘移动到圆盘移动到Z塔座塔座上：上：1.每次只允许移动一个圆盘（从一个塔座到另一个塔每次只允许移动一个圆盘（从一个塔座到另一个塔座）；座）；2.移动时可用移动时可用Y塔座作为中间塔座；塔座作为中间塔座；3.在移动过程中，任何一个塔座上均不允许出现大压在移动过程中，任何一个塔座上均不允许出现大压小的情况发生。小的情况发生。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法35图示图示 Hanoi塔问题塔问题XYZ起始塔柱起始塔柱 中间塔柱中间塔柱 目的塔柱目的塔柱1.每次只允许移动一个圆盘（从一个每次只允许移动一个圆盘（从一个塔座到另一个塔座）；塔座到另一个塔座）；2.移动时可用移动时可用Y塔座作为中间塔座；塔座作为中间塔座；3.在移动过程中，任何一个塔座上均在移动过程中，任何一个塔座上均不允许出现大压小的情况发生。不允许出现大压小的情况发生。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法36三阶三阶Hanoi塔问题塔问题分析：分析：起始塔座起始塔座X上有三个圆盘，所以该问题上有三个圆盘，所以该问题被称为三阶被称为三阶Hanoi塔问题。塔问题。塔座塔座X塔座塔座Y塔座塔座Z321需要完成：需要完成：Hanoi(3,X,Y,Z)；其中，参数其中，参数1表示一共需要移动表示一共需要移动几个圆盘；参数几个圆盘；参数2表示起始塔座；表示起始塔座；参数参数3表示中间塔座；参数表示中间塔座；参数4表表示目的塔座。示目的塔座。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法37三阶三阶Hanoi塔问题塔问题分析：分析：完成完成Hanoi(3,X,Y,Z)的工作可以分解成如的工作可以分解成如下三个步骤：下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和和Hanoi(2,Y,X,Z)。塔座塔座X塔座塔座Y塔座塔座Z321需要先完成：需要先完成：Hanoi(2,X,Z,Y)；该工作又可分解成：该工作又可分解成：Hanoi(1,X,Y,Z)；MOVE(X,2,Y)；Hanoi(1,Z,X,Y)。完成完成Hanoi(1,X,Y,Z)；工作等价于工作等价于MOVE(X,1,Z)。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法38三阶三阶Hanoi塔问题塔问题塔座塔座X塔座塔座Y塔座塔座Z321分析：分析：完成完成Hanoi(3,X,Y,Z)的工作可以分解成如的工作可以分解成如下三个步骤：下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和和Hanoi(2,Y,X,Z)。需要先完成：需要先完成：Hanoi(2,X,Z,Y)；该工作又可分解成：该工作又可分解成：Hanoi(1,X,Y,Z)；MOVE(X,2,Y)；Hanoi(1,Z,X,Y)。完成完成MOVE(X,2,Y)。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法39三阶三阶Hanoi塔问题塔问题塔座塔座X塔座塔座Y塔座塔座Z321分析：分析：完成完成Hanoi(3,X,Y,Z)的工作可以分解成如的工作可以分解成如下三个步骤：下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和和Hanoi(2,Y,X,Z)。需要先完成：需要先完成：Hanoi(2,X,Z,Y)；该工作又可分解成：该工作又可分解成：Hanoi(1,X,Y,Z)；MOVE(X,2,Y)；Hanoi(1,Z,X,Y)。完成完成Hanoi(1,Z,X,Y)；工作等价于工作等价于MOVE(Z,1,Y)。Hanoi(2,X,Z,Y)Hanoi(2,X,Z,Y)完成完成完成完成!2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法40三阶三阶Hanoi塔问题塔问题分析：分析：完成完成Hanoi(3,X,Y,Z)的工作可以分解成如的工作可以分解成如下三个步骤：下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和和Hanoi(2,Y,X,Z)。塔座塔座X塔座塔座Y塔座塔座Z321完成：完成：MOVE(X,3,Z)；接下来需要完成：接下来需要完成：Hanoi(2,Y,X,Z)。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法41三阶三阶Hanoi塔问题塔问题分析：分析：完成完成Hanoi(3,X,Y,Z)的工作可以分解成如的工作可以分解成如下三个步骤：下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和和Hanoi(2,Y,X,Z)。塔座塔座X塔座塔座Y塔座塔座Z321最后完成：最后完成：Hanoi(2,Y,X,Z)；该工作又可分解成：该工作又可分解成：Hanoi(1,Y,Z,X)；MOVE(Y,2,Z)；Hanoi(1,X,Y,Z)。完成完成Hanoi(1,Y,Z,X)；其工作等价于其工作等价于MOVE(Y,1,X)。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法42三阶三阶Hanoi塔问题塔问题分析：分析：完成完成Hanoi(3,X,Y,Z)的工作可以分解成如的工作可以分解成如下三个步骤：下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和和Hanoi(2,Y,X,Z)。塔座塔座X塔座塔座Y塔座塔座Z312最后完成：最后完成：Hanoi(2,Y,X,Z)；该工作又可分解成：该工作又可分解成：Hanoi(1,Y,Z,X)；MOVE(Y,2,Z)；Hanoi(1,X,Y,Z)。完成完成MOVE(Y,2,Z)。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法43三阶三阶Hanoi塔问题塔问题分析：分析：完成完成Hanoi(3,X,Y,Z)的工作可以分解成如的工作可以分解成如下三个步骤：下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和和Hanoi(2,Y,X,Z)。塔座塔座X塔座塔座Y塔座塔座Z321最后完成：最后完成：Hanoi(2,Y,X,Z)；该工作又可分解成：该工作又可分解成：Hanoi(1,Y,Z,X)；MOVE(Y,2,Z)；Hanoi(1,X,Y,Z)。完成完成Hanoi(1,X,Y,Z)；其工作等价于其工作等价于MOVE(X,1,Z)。Hanoi(2,Y,X,Z)Hanoi(2,Y,X,Z)完成完成完成完成!Hanoi(3,X,Y,Z)Hanoi(3,X,Y,Z)完成完成完成完成!2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法44总结总结：三阶三阶Hanoi塔问题塔问题将一个复杂的问题将一个复杂的问题（三阶（三阶Hanoi塔问题）塔问题）归结为若干个较简归结为若干个较简单的问题单的问题（二阶（二阶Hanoi塔问题）塔问题）；然后将这些较简单的每一个问题然后将这些较简单的每一个问题（二阶（二阶Hanoi塔问题）塔问题）再归再归结为更简单的问题，直到最简单的问题结为更简单的问题，直到最简单的问题（一阶（一阶Hanoi塔问题）塔问题）为止。为止。塔座塔座X塔座塔座Y塔座塔座Z3212022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法45再分析：再分析：n阶阶Hanoi塔问题塔问题求解的步骤求解的步骤：1.如果如果n=1，则可直接将这一个圆盘移动到目的柱则可直接将这一个圆盘移动到目的柱上，过程结束。如果上，过程结束。如果n1，则进行则进行步骤步骤2。2.设法将设法将起始柱起始柱的上面的上面n-1个圆盘（编号个圆盘（编号1到到n-1）按按移动原则移动到移动原则移动到中间柱中间柱上。上。3.将将起始柱起始柱上的最后一个圆盘（编号为上的最后一个圆盘（编号为n）移到移到目目的柱的柱上。上。4.设法将设法将中间柱中间柱上的上的n-1圆盘按移动原则移到圆盘按移动原则移到目的柱目的柱上。上。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法46步骤步骤2与与步骤步骤4实际上还是实际上还是Hanoi塔问题，只不过其塔问题，只不过其规模小一些而已。规模小一些而已。如果最原始的问题为如果最原始的问题为n阶阶Hanoi塔问题，且表示为塔问题，且表示为Hanoi(n,X,Y,Z)则则步骤步骤2与与步骤步骤4为为n-1阶阶Hanoi塔问题分别表示为：塔问题分别表示为：Hanoi(n-1,X,Z,Y)Hanoi(n-1,Y,X,Z)其中第一个参数表示问题的阶数，第二、三、四个其中第一个参数表示问题的阶数，第二、三、四个参数分别表示参数分别表示起始柱起始柱、中间柱中间柱与与目的柱目的柱。将将X塔座上的塔座上的n号圆盘移到号圆盘移到Z塔座上塔座上Move(X,n,Z)2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法47补充举例之补充举例之算法算法：求解求解n阶阶Hanoi塔问题。塔问题。Hanoi(n,X,Y,Z)IF n=1 THEN move(X,1,Z)ELSE Hanoi(n-1,X,Z,Y)move(X,n,Z)Hanoi(n-1,Y,X,Z)RETURN函数在执行过程中函数在执行过程中调用自身的方法叫调用自身的方法叫递归调用递归调用。递归的边界递归的边界2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法48另一个简单的例子另一个简单的例子例例1.2：编编写写一一个个过过程程，对对于于输输入入的的参参数数n，依依次打印输出自然数次打印输出自然数1到到n。（非递归算法）非递归算法）PROCEDURE WRT(n)FOR k1 TO n DO OUTPUT k RETURN2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法49输出自然数输出自然数1到到n的的递归算法递归算法。PROCEDURE WRT1(n)IF (n0)THEN WRT1(n1)OUTPUT n RETURNWRT1(3)WRT1(2)WRT1(1)WRT1(0)OUTPUT 2OUTPUT 1OUTPUT 3递归的边界递归的边界 1232022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法50总结总结一个典型的一个典型的递归算法：自己调用自己递归算法：自己调用自己。直接递归：直接递归：如果一个算法如果一个算法P显式地调用自己。显式地调用自己。间接递归：间接递归：如果算法如果算法P调用另一个算法调用另一个算法Q，而而算法算法Q又调用算法又调用算法P。递归算法与递推算法的区别递归算法与递推算法的区别：两者的实现方法是：两者的实现方法是大不一样的。大不一样的。递推是从初始条件出发，逐次推出所需求的结递推是从初始条件出发，逐次推出所需求的结果；果；而递归则是从算法本身达到而递归则是从算法本身达到递归边界递归边界。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法51减半递推减半递推所谓所谓“减半减半”，是指将问题的规模减半，而问题，是指将问题的规模减半，而问题的性质不变。的性质不变。所谓所谓“递推递推”，是指重复，是指重复“减半减半”的过程。的过程。将实际问题的规模逐渐减少，可明显地降低解决将实际问题的规模逐渐减少，可明显地降低解决问题的复杂程度。这种方法称为问题的复杂程度。这种方法称为分治法分治法，即对问，即对问题分而治之。题分而治之。工程上常用的分治法是工程上常用的分治法是减半递推技术减半递推技术，这个技术，这个技术在快速算法的研究中有很重要的使用价值。在快速算法的研究中有很重要的使用价值。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法52举例举例例例1.3：二分法求方程二分法求方程f(x)在在a,b的根的根设方程设方程f(x)=0在区间在区间a,b内内有且只有一个实根有且只有一个实根，则函数则函数f(x)在区间的两个端点处的函数值必异在区间的两个端点处的函数值必异号，即号，即2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法531.首先取给定区间的首先取给定区间的中点中点c(ab)/2。2.然后判断然后判断f(c)是否为是否为0。若若f(c)0,则说明则说明c即为所求的根，即为所求的根，求解过程结束求解过程结束；如果如果f(c)0,则根据以下原则将原区间减半；则根据以下原则将原区间减半；若若f(a)f(c)0，则取原区间的前半部分；则取原区间的前半部分；若若f(b)f(c)0，则取原区间的后半部分。则取原区间的后半部分。3.最后判断减半后的区间长度是否已经很小：最后判断减半后的区间长度是否已经很小：若若|ab|，则则过过程程结结束束，取取(ab)/2为为根根的的近近似值似值；若若|ab|，则重复上述的减半过程。则重复上述的减半过程。所能接受的误差所能接受的误差2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法54算法算法1.3 二分法求方程的根二分法求方程的根输入：根所在区间输入：根所在区间a,b，精度要求精度要求输出：满足精度要求的根的近似值输出：满足精度要求的根的近似值c f0f(a)WHILE|b-a|DO c(a+b)/2;f1f(c)IF f1=0 THEN OUTPUT c RETURN IF f0f10 THEN ac ELSE bc c(a+b)/2 OUTPUT c RETURNf0f(a)|b-a|c(a+b)/2;f1f(c)f1=0OUTPUT c结束结束得出准确根得出准确根f0f10得出近似根得出近似根acbcTTFFTF2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法55总结总结对于有些实际问题，可以设计出直观的减半递推对于有些实际问题，可以设计出直观的减半递推算法，经过逐次的减半递推，直接得到所需求的算法，经过逐次的减半递推，直接得到所需求的结果，如结果，如例例1.3：二分法求方程的根二分法求方程的根。对于另外一些问题，对于另外一些问题，根据减半递推技术设计出的根据减半递推技术设计出的算法是递归算法算法是递归算法，在执行过程中只能靠算法本身，在执行过程中只能靠算法本身到达到达递归边界递归边界。如。如例子例子：两个两个n阶矩阵相乘的快速阶矩阵相乘的快速方法方法就是递归算法（斯特拉森（就是递归算法（斯特拉森（Strassen）算法）。算法）。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法56回溯法回溯法通过对问题的分析，找出一个解决问题的线索，通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试然后沿着这个线索逐步试探，对于每一步的试探，若探，若试探成功试探成功，就得到问题的解，若，就得到问题的解，若试探失试探失败败，就逐步回退，换别的路线再进行试探。，就逐步回退，换别的路线再进行试探。例例1.4 求解皇后问题。求解皇后问题。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法57例例1.4 求解皇后问题。求解皇后问题。由由n2个方块排成个方块排成n行行n列的正方形称为列的正方形称为“n元棋盘元棋盘”。如果两个皇后位于棋盘上的如果两个皇后位于棋盘上的同一行同一行或或同一列同一列或或同一同一对角线对角线上，则称它们为上，则称它们为互相攻击互相攻击。现要求找使。现要求找使n元元棋盘上的棋盘上的n个皇后互不攻击的所有布局。个皇后互不攻击的所有布局。分析分析：假设棋盘上的每一行放置一个皇后，分别用自然假设棋盘上的每一行放置一个皇后，分别用自然数进行编号为数进行编号为1，2，n。首先，将问题归结为在首先，将问题归结为在n元棋盘的每一行上安置元棋盘的每一行上安置一个皇后，并假设第一个皇后，并假设第i个皇后被安置在第个皇后被安置在第i行上。行上。定义一个长度为定义一个长度为n的一维数组的一维数组q，其中每一个元素其中每一个元素qi（i=1，2，n）用于在安置皇后过程中随用于在安置皇后过程中随时记录时记录第第i行上的皇后所在行上的皇后所在列号列号。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法58此时，在安置每一行上的皇后时，只需考虑此时，在安置每一行上的皇后时，只需考虑每两个皇后不能在同一列或者同一对角线上每两个皇后不能在同一列或者同一对角线上即可。容易验证，即可。容易验证，第第i行上的皇后和第行上的皇后和第j行上行上的皇后正好在同一列上的的皇后正好在同一列上的充要条件充要条件为：为：qi qj=0正好在某一对角线上的正好在某一对角线上的充要条件充要条件为：为：|qi qj|-|i-j|=0在初始时，将每一行的皇后均放在第一列，在初始时，将每一行的皇后均放在第一列，即即初始状态为：初始状态为：qi=1,i=1,2,3,n。2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法59然后从第一行（即然后从第一行（即i=1）开始进行以下过程：开始进行以下过程：设前设前i-1行行的皇后已经布局好，即它们互不行行的皇后已经布局好，即它们互不攻击攻击。现考虑安排第。现考虑安排第i行上的皇后位置，使行上的皇后位置，使之与前之与前i-1行上的皇后也互不攻击。行上的皇后也互不攻击。为了实现这一点，需要从第为了实现这一点，需要从第i行皇后的当前行皇后的当前位置开始位置开始向右搜索向右搜索：2022/12/20计算机软件技术基础计算机软件技术基础 第一章第一章 算法算法601.若若qin，则需检查第则需检查第i行皇后与行皇后与前前i-1行的皇后行的皇后是是否互不攻击。若无攻击，则考虑安排下一行皇后否互不攻击。若无攻击，则考虑安排下一行皇后的位置；若有攻击，则将第的位置；若有攻击，则将第i行皇后右移一个位置，行皇后右移一个位置，重新进行这个过程。重新进行这个过程。2.若若qin，则说明在前则说明在前i-1行皇后的当前布局下，第行皇后的当前布局下，第i行皇后无法安置。此时，将第行皇后无法安置。此时，将第i行皇后重新放在第行皇后重新放在第一列，且回退一行，一列，且回退一行，考虑第考虑第i-1行皇后与前行皇后与前i-2行皇行皇后均互不攻击的下一个位置后均互不攻击的下一个位置。在这种情况下，如。在这种情况下，如果已经退到第果已经退到第0行（行（n元棋盘不存在第元棋盘不存在第0行），则行），则过过程结束程结束。3.若当前安置好的皇后是在最后一行（即第若当前安置好的皇后是在最后一行（即第n行），行），则说明已