循环赛日程表的递归和非递解

介绍了算法设计技术分治法的应用。使用分治法实现了循环赛日程表的递归和非递归解,并作了较为详细的说明,供《算法设计与分析》课程教学参考。     

分治递归算法的解题能力

为了培养学习编程的逆向思维，运用分治思想的递归算法提高解决问题的能力，理解分治和递归的关系，掌握递归算法解决问题的条件和原理是十分必要的。从提出问题、分析问题、抽象问题的特征、解决问题和分析递归算法的局限性的过程，运用比较法比较迭代与递归之间的关系，结合具体问题，对理解递归算法解决问题给出了有效的方法。用分治的递归方法求解问题，其结构简单，可读性强，但是递归算法理解起来有一定难度，研究了递归算法的特征、递归与分治之间的关系、递归与迭代之间的关系，根据时间和空间复杂度，给出了递归算法的深度建议。实践的结果证明，采用这样的方式，能够帮助读者理解逆向思维和分治思想的本质，提升运用递归算法解决生活和学习中的问题的能力。     

分治算法的探讨及应用

考虑到分治法是算法设计中的主要算法且具有广泛的应用性,本文对分治法的基本思想、基本步骤、适用条件及其应用进行探讨。最后,结合几个典型的例子,对分治法进行算法分析和算法设计,并侧重分析了分治算法的时间复杂性。     

最大团问题的加权分治算法

分支降阶是目前广泛用于求解组合优化领域中难题的技术之一,该技术的核心思想是将原问题分支成若干个子问题,并递归求解这些子问题。加权分治技术是算法设计和时间复杂度分析中的一种新技术。设计一个基于分支降阶的递归算法求解最大团问题。运用常规技术对该算法进行时间复杂度分析,得出其时间复杂度为[O(1.380np(n)),]其中[p(n)]表示问题规模数[n]的多项式函数。运用加权分治技术对原算法进行时间复杂度分析,将该算法的时间复杂度由原来的[O(1.380np(n))]降为[O(1.325np(n))]。研究结果表明运用加权分治技术能够得到较为精确的时间复杂度。     

递归技术在采用回溯法求解的问题上的应用

本文讨论了对采用回溯法求解的问题设计递归算法程序的方法，同时，对几个较典型的问题，给出了采用回溯法求解时的递归算法程序。     

基于二叉树的递归程序算法实现策略

递归是一种重要的程序设计方法,但在教学过程中一直是个难点。本文从方法论的角度对递归程序设计进行系统的阐述,介绍了递归程序设计的一般步骤和方法,以及如何通过分治和回溯等策略进行递归程序设计。     

基于分治和递归策略的排序算法及实现

对关键字数量远少于记录数量的排序问题进行了研究,提出了基于分治和递归策略的有效算法。经与选择排序算法比较,该算法在各种情况下的交换次数均明显少于经典的选择排序算法。     

一个算法演示课件的制作

为了更加清楚了解递归和分治算法的执行情况,使用该算法具体分析了棋盘覆盖问题,然后利用VisualC 制作演示课件直观显示算法的执行步骤,在实际教学中取得了很好的效果。     

全排列递归算法在算法教学中的重要性

全排列递归算法简洁,清晰,可读性强。针对该算法在递归算法的设计以及回溯法中的应用．讨论了全排列递归算法在算法教学中的重要作用。     

基于数据结构的程序递归算法设计

递归是一种重要的程序设计方法,但在教学过程中一直是个难点.本文从方法论的角度对递归程序设计进行系统的阐述,介绍了递归程序设计的一般步骤和方法,以及如何通过分治和回溯等策略进行递归程序设计.     

面向漏洞挖掘的基于符号分治区的测试用例生成技术

在漏洞挖掘中,符号执行技术是一种常用的测试用例生成技术。但当软件中包含加解密、校验和检验等复杂数学运算函数时,使用符号执行技术生成测试用例存在无法有效求解约束表达式的问题,导致漏洞挖掘效率低下。针对该问题,文章结合分治算法的思想提出基于符号分治区的测试用例生成技术。首先通过静态分析技术识别软件中的加解密、校验和检验等函数;然后以程序中的加解密、校验和检验函数为分界点对软件进行分区,符号执行引擎每执行到软件的一个分治区,就在本区引入一个新的符号变元进行约束构建,在约束求解时从软件最后一个分治区开始递归求解。基于该方法,文章在符号执行平台S2E上实现了漏洞挖掘原型系统Divide,并与现有的符号执行生成测试用例技术进行对比实验。实验结果表明,文章方法能够快速、有效地生成测试用例,提高漏洞挖掘的效率。     

求解对称带状广义特征值问题的扩展分治算法

提出了分布式环境下计算对称带状广义特征值问题的一种扩展分治算法，给出了特征值分割定理及其证明．算法在扩展分治的基础上，利用二分压缩结合广义Rayleigh商迭代计算广义特征对．理论分析和数值实验表明，对于窄带宽大规模的广义特征值问题，该分治算法明显优于LAPACK软件包．结合并行性好的多分法，在分布式环境下获得了很好的并行效果．     

空间叠加分析中的分而治之算法研究与应用

土地利用现状数据由CAD格式转换为GIS格式后需重新为图斑对象设置土地分类编码属性,为了提高海量空间数据情况下自动赋值的效率,研究了将分而治之算法应用于海量数据空间叠加分析以提高效率的方法。研究表明,对于所有需通过空间叠加分析来确定不同图层空间对象间的空间关系的问题,均可以采用分而治之方法来降低时间复杂度。在最小化分割的情况下,基于四叉树空间索引,分而治之算法可以使此类应用的时间复杂度降低为O（n lb n）。实际应用验证了该方法在海量空间数据处理中的效率和实用价值。     

油井管道问题的分治解法

分治算法是解决许多实际问题的重要而有效的方法。该文首先对油井的管道问题进行了分析,然后提出一种基于分治策略的解决方案,并给出了其实现算法,最后对所提出算法的复杂度进行了分析。     

A linear space algorithm for the LCS problem

Summary The LCS problem is to determine the longest common subsequence (LCS) of two strings. A new linear-space algorithm to solve the LCS problem is presented. The only other algorithm with linear-space complexity is by Hirschberg and has runtime complexity O(mn). Our algorithm, based on the divide and conquer technique, has runtime complexity O(n(m-p)), where p is the length of the LCS.     

子集和问题的O(1.414n)链数DNA计算机算法

随着DNA计算机研究的不断深入,如何克服DNA生物计算中穷举法的极限已成为DNA计算研究的重要内容之一.为设计可扩展的子集和问题DNA计算机算法,文中将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,通过设计DNA并行搜索器,提出一种求解子集和问题的DNA计算机模型和算法.与已有文献结论的对比分析表明:文中算法在保持多项式生物操作复杂性的条件下,将穷举算法中的DNA分子链数从O(2n)减少至O(1.414n),其中n为子集和问题的维数.因此,文中算法理论上在试管级生化反应条件下能将可破解子集和公钥的维数从60提高到120.     

背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2^n/4)^1-ε个并行处理机单元,0≤ε≤1,O(2^n/2)个存储单元,在O(2^n/4(2^n/4)^ε)时间内求解n维背包问题,算法的成本为O(2^n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.     

求马步图Hamilton圈的最优算法

本文对骑士巡游问题进行了研究 ,提出了求棋盘马步图的 Hamilton圈的“分治 -回溯 -合并”算法 ,其时间复杂度是 O(n2 )。分析表明该算法是求棋盘马步图一条 Hamilton圈的最优算法 ,对VLSI的布线问题具有一定的应用价值     

一种改进的构建凸包的分治算法

本文为构建离散点的凸包提出了一种改进的分治算法，它在查找每一个凸包顶点的同时，通过去除若干非凸包顶点来迅速减小问题的规模。本文对该算法的正确性给出了严格的证明。