Hanoi塔非递归算法的形式化推导和正确性验证

关于Hanoi塔问题的非递归算法已有大量的研究.运用薛锦云教授自创的PAR方法和循环不变式开发的新策略,形式化推导出逻辑结构清晰的Hanoi塔非递归算法及其循环不变式,并用Dijkstra最弱前置谓词法验证了该算法的正确性.充分体现了PAR方法的优越性、高效性和可靠性.     

一种形式化开发非递归算法的方法*

提出了一种简单、统一的形式化开发非递归算法的方法.该方法直接面向非递归算法,在形式化方法PAR的指导下,使用循环不变式的开发新策略,在得到求解递归问题的循环不变式的同时,能直接得到易读、高效且可靠的非递归算法,并通过一个具体实例进行了阐述.对使用形式化方法及循环不变式开发新策略开发非递归算法的方法作了较深入的实践和探讨.     

形式化开发非递归Koch曲线算法

形式化方法是构建可信软件的重要途径。Koch曲线是典型的分形图形。基于形式化方法PAR及循环不变式开发策略,开发了Koch曲线非递归算法,并对其进行了形式化的正确性证明。在得到求解Koch曲线算法的循环不变式的同时,直接得到易读、高效且可靠的非递归算法。对使用形式化方法及循环不变式开发策略开发分形程序非递归算法作了较深入的实践和探讨。     

后序遍历二叉树非递归算法的推导及形式化证明

开发涉及非线性数据结构算法程序的循环不变式一直是形式化方法的难点。本文使用PAR方法开发循环不变式的新策略,对后序遍历二叉树问题循环不变式的开发使用递归定义技术,得到了该问题循环不变式的简单精确的表达形式,简化了算法程序的推导和证明过程;利用PAR平台提供的抽象程序设计语言Ap1a中的数据抽象机制,使所得的算法程序结构简洁清晰且易于证明;最后,使用Dijkstra-Gries标准程序证明法形式证明了该问题的核心算法程序(只有4行代码),并使用PAR平台将Apla程序转换成正确的C++代码。实例的成功进一步说明PAR方法提供的循环不变式的开发技术对推导和证明非线性数据结构算法程序的有效性。     

若干算法程序的形式化推导与生成技术研究

PAR方法基于分划与递推、量词变换规则、循环不变式开发新策略和软件转换工具,实现了复杂算法问题的形式化开发.采用PAR方法形式化推导几个典型的算法问题.通过量词变换规则对程序规约进行形式化推导,可以得到具有数学引用透明性、易于形式化证明的求解算法问题的递推关系;并在此基础上,自然地导出循环不变式.在得到简短、易于理解、高可靠性的Apla算法程序之后,通过转换工具自动生成Java,C 等可执行程序.     

0-1背包问题的一种新解法

针对目前求解0-1 背包问题算法的优缺点,开发了一种新的非递归算法。从计算0-1 背包问题最优值的递归方程出发,使用形式推导技术及序列抽象数据类型。在开发出循环不变式的同时,归纳得到用抽象程序设计语言Apla描述的非递归算法,并形式化证明了其正确性,在相关工具及部件库的支持下进一步得到C++程序。理论分析和实验结果表明,该算法的时间耗费受背包容量变化的影响很小,是一种有效的方案。     

Hanoi塔问题的一种非递归算法

通过对 Hanoi塔问题的研究 ,给出了 Hanoi塔问题的非递归算法的思想和流程图 ,并用不允许递归调用的 BASIC语言实现了 Hanoi塔问题的非递归算法。该算法的优点在于可一次性求得总移动次数 ,但从程序结构看其编程思路较复杂 ,难于理解 ,算法的时间复杂性和空间复杂性与递归算法无异。     

循环不变式开发新策略及其应用

循环不变式体现了循环程序的本质特征,在算法程序的开发、证明和推导中具有十分重要的作用。而传统的循环不变式开发策略并没有很好地解决循环不变式开发难的问题。文章在阐述现有策略局限性的基础上,详细阐述了刻画循环不变式本质特征的新定义及基于此定义的开发循环不变式的新策略,并通过三个典型的实例,对开发新策略的具体应用作了比较深入的探索。     

用VB编写Hanoi塔问题动态演示程序

递归技术是算法设计过程中的一个重要技术,Hanoi塔问题是一个典型的适合用递归技术求解的问题。将Hanoi塔问题的递归执行过程利用编程方法动态演示出来,有助于人们结合Hanoi塔问题加深对递归技术的理解。     

用VB编写Hanoi塔问题动态演示程序

递归技术是算法设计过程中的一个重要技术,Hanoi塔问题是一个典型的适合用递归技术求解的问题.将Hanoi塔问题的递归执行过程利用编程方法动态演示出来,有助于人们结合Hanoi塔问题加深对递归技术的理解.     

Hanoi塔问题非递归的新算法

关于Hanoi塔问题的非递归算法,已有了大量的研究[1￣4]。实验表明,当圆盘数目较少时,现有的非递归算法的执行速度比递归算法要快一些,但是随着圆盘数目的增加,现有的非递归算法的执行速度会逐渐变得比递归算法慢。论文提出了一种基于压缩编码的非递归新算法,在压缩了存储空间的同时,提高了算法的执行速度。实验结果表明,对于任意圆盘数目n,论文所实现的非递归算法的执行速度比现有的递归算法和非递归算法都有成倍的提高。     

汉诺塔问题的层次迭代算法

汉诺（Hanoi）塔是程序算法设计的一个比较经典问题,目前已有大量的相关文献对其进行了研究。为进一步加快汉诺塔问题的求解速度,通过对汉诺塔问题抽象解树的分析,发现其可以划分为不同层次相同结构的子树,通过对子树层次化控制即可迭代出整个问题的解。基于此,提出了一种用已知子树分层次迭代汉诺塔问题的非递归算法。运行时间测试表明,该算法进一步提高了求解的速度。     

Hanoi塔问题一种非递归算法的C++实现

通过对汉诺问题的递归算法及结果的分析,创造性地借助二叉树的数据结构设计出非递归算法。给出了实现该算法的C++语言源程序。该算法并未真正在物理上生成所谓的二叉树,有别于常规对二叉树结构的使用。     

广义Hanoi塔问题的动态规划算法

基于动态规划算法思想，深入分析了广义Hanoi塔问题动态规划分割点的特征，给出动态规划分割点的简单计算公式，使得动态规划算法转化为一个非常简单的递归算法，由此可以迅速产生广义Hanoi塔问题的最优移动序列，从而彻底解决了广义Hanoi塔问题的最优移动序列问题．     

An optimal algorithm to implement the Hanoi towers with parallel moves

In 1992, Wu and Chen proposed a new variant of the tower of Hanoi problem allowing parallel moves, and derived the minimum number of disk moves. This paper proposes an optimal iterative algorithm to implement it.