An iterative algorithm for the cyclic Towers of Hanoi problem

In the cyclic Towers of Hanoi problem, the discs may only move in a clockwise direction from a source peg to a specified peg subject to the usual restrictions of the standard problem. An iterative solution to the modified problem is presented. A number of observations that lead to the construction of an iterative algorithm is also discussed.     

The towers of Hanoi revisited: Moving the rings by counting the moves

A non-recursive algorithm, distinct from the one already in the literature, is presented for solving the n-ring Towers of Hanoi problem in the minimum 2ⁿ?1 moves. In addition, a simple relation is found between the binary representation of k and the position of the rings after k moves, allowing either to be obtained from the other in O(n) operations. Thus the position of the rings can be effectively stored in a work of n bits.     

On finding optimal covers

After a statement of the general problem underlying Quine's methods of simplifying logical expressions, a few examples, and a survey of various approaches to the problem, attention is focussed on the question of how to branch when the straightforward simplication rules give no further progress. An algorithm is suggested that takes advantage of the freedom of choice at the branching step in order to split the given problem into several smaller problems. As the difficulty of the problem grows exponentially with its size, this results in a great saving of effort. Both the hand and computer versions of the algorithm are described since they differ appreciably. The pattern recognition example used to illustrate the paper is chosen as typical of the wide variety of practical questions in which the above general problem arises.     

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.     

A generalization of the cyclic towers of hanoi: an iterative solution

In the cyclic Towers of Hanoi problem, discs are allowed to move in a clockwise direction only subject to the usual constraints of the standard problem. A generalization to the cyclic problem is proposed, which relaxes from the original one tower of discs to not more than three towers as an initial configuration. An iterative solution to the generalized problem is presented; several fundamental and crucial observations are also discussed.     

用VB设计汉诺塔动画游戏

汉诺塔问题是程序设计教学中关于递归调用的经典案例。该文介绍了用VB设计汉诺塔动画游戏程序的基本过程,其中重点介绍了用VB的自定义数据类型和图形处理技术设计游戏步点状态记录和动画效果的方法。     

A tree-covering problem arising in integrity of tree-structured data

We introduce and solve a problem motivated by integrity verification in third-party data distribution: Given an undirected tree, find a minimum-cardinality set of simple paths that cover all the tree edges and, secondarily, have smallest total path lengths. We give a linear time algorithm for this problem.     

校园软件开发平台的选择与应用

在软件开发平台的选择与应用过程中,我们本着平台的开发性、分布性、平台无关性原则,根据我院的具体情况,通过对目前两种主流平台：J2EE和.NET的比较分析,体系结构和应用平台的无缝集成,开发成本及易开发性的思考与研究,最终选择了.NET作为开发平台.使用Microsoft全新的集成开发环境Visual Studio.NET,采用ASP.NET、Web Service、ADO.NET和XML等技术进行系统开发.     

The worst-case chip problem

In the system level, adaptive fault diagnosis problem we must determine which components (chips) in a system are defective, assuming the majority of them are good. Chips are tested as follows: Take two chips, say x and y, and have x report whether y is good or bad. If x is good, the answer is correct, but if x is bad, the answer is unreliable. One way to identify all defective chips is to identify a single good chip which can then be used to diagnose the other chips; the chip problem is to identify a single good chip. We show that the chip problem is closely related to a modified majority problem in the worst case and use this fact to obtain upper and lower bounds on algorithms for the chip problem.     

The reverse greedy algorithm for the metric k-median problem

The Reverse Greedy algorithm (RGreedy) for the k-median problem works as follows. It starts by placing facilities on all nodes. At each step, it removes a facility to minimize the total distance to the remaining facilities. It stops when k facilities remain. We prove that, if the distance function is metric, then the approximation ratio of RGreedy is between Ω(logn/loglogn) and O(logn).     

基于Java的汉诺塔教学演示程序

借助计算机系统的单步执行、动态演示等功能,设计并开发了基于Java的汉诺塔教学演示程序,通过该程序可使学习者观测到解决该问题的动态全过程。     

An in-place algorithm for Klee's measure problem in two dimensions

We present the first in-place algorithm for solving Klee's measure problem for a set of n axis-parallel rectangles in the plane. Our algorithm runs in O(n3/2logn) time and uses O(1) extra words in addition to the space needed for representing the input. The algorithm is surprisingly simple and thus very likely to yield an implementation that could be of practical interest. As a byproduct, we develop an optimal algorithm for solving Klee's measure problem for a set of n intervals; this algorithm runs in optimal time O(nlogn) and uses O(1) extra space.     

A simple approximation algorithm for the weighted matching problem

We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259-269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time.     

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

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