2010年5月20日

     摘要: 1。建立迷宫(外围建筑围墙),可选择人工创建迷宫或计算机随机创建迷宫,还可修改迷宫
2。设置入口和出口。
3。寻找最短路径,分别采用了广度搜索,深度搜索(包括递归和非递归形式)
4。若找到可行路径,打印路径,否则报告错误。  阅读全文

posted @ 2010-05-20 15:37 梦想飞扬 阅读(1301) | 评论 (0)编辑 收藏

2010年5月7日

     摘要: 三元组稀疏矩阵类:实现了矩阵的转置,加法和乘法运算  阅读全文

posted @ 2010-05-07 09:58 梦想飞扬 阅读(2722) | 评论 (0)编辑 收藏

2010年4月16日

     摘要: 人类习惯使用十进制数进行数值计算,而计算机则采用二进制,所以为了让计算机帮助人类计算,首先要把十进制数转换为二进制数。本文以最简单的8位定点整数为例,分析了计算机存储和计算数值的方法。  阅读全文

posted @ 2010-04-16 08:41 梦想飞扬 阅读(1282) | 评论 (2)编辑 收藏

2010年4月14日

     摘要: 摘要:延迟认可算法(Gale-Shapley算法)是解决稳定婚姻问题的经典算法,本文用C++来实现Gale-Shapley算法。文章详细介绍了Gale-Shapley算法的原理和编码思路,给出了一个直接从原理出发的原始算法及其改进版本,并对两个版本进行了比较分析。

关键词:稳定婚姻问题 延迟认可算法 二维数组 以空间换时间
  阅读全文

posted @ 2010-04-14 09:41 梦想飞扬 阅读(2395) | 评论 (1)编辑 收藏

2009年6月9日

     摘要: 引子:这篇文章以前写过,最近复习排序算法,觉得以前的代码还可以改进,因此有了此文。

归并排序算法以O(NlogN)最坏情形运行时间运行,而所使用的比较次数几乎是最优的。

该算法中最基本的操作是合并两个已排序的表,这只需要线性的时间,但同时需要分配一个临时数组来暂存数据。

归并排序算法可以用递归的形式实现,形式简洁易懂。如果N=1,则只有一个元素需要排序,我们可以什么都不做;否则,递归地将前半部分数据和后半部分数据各自归并排序,然后合并这两个部分。

归并排序算法也可以用非递归的形式实现,稍微难理解一点。它刚好是递归分治算法的逆向思维形式,在使用递归分治算法时,程序员只需考虑将一个大问题分成若干个形式相同的小问题,和解的边界条件,具体如何解决这些小问题是由计算机自动完成的;而非递归形式要求程序员从最基本的情况出发,即从解决小问题出发,一步步扩展到大问题。

我这里两种形式都给出。

另外,很多人在写递归形式的归并排序算法时,临时数组是在MergeSort函数中分配的,这使得在  阅读全文

posted @ 2009-06-09 08:25 梦想飞扬 阅读(7449) | 评论 (4)编辑 收藏

2009年5月10日

     摘要: 通过分析简单字符串模式匹配算法的缺陷,引导读者观察模式串P和目标串T已比较相等字符的关系,自然而然的引入了高效的KMP算法,并对KMP算法的难点——失效函数进行重点突破,先后比较了三种失效函数的区别和联系,提供详细的代码及算法分析。最后得出结论:这样我们就学习了三种失效函数的表示方法,虽然它们对应的KMP算法代码略有不同,但其本质是一样的,就是避免回溯目标串T的下标i,并使得模式串P的下标j回溯到正确位置。同样的,不管你用什么代码来实现求解失效函数的算法,其本质都是模式串内部的模式匹配,采用递推的方式,寻找最大的相同子串。  阅读全文

posted @ 2009-05-10 21:59 梦想飞扬 阅读(2705) | 评论 (2)编辑 收藏

2009年1月20日

     摘要: 我曾经写过一篇《有序全排列生成算法》,介绍了五种生成有序全排列的方法,在该文的末尾,我计划再写一篇姊妹篇《非有序全排列生成算法》,由于各种原因,一直迟迟未动笔,前几天学习数据结构“栈”的时候,碰到一个有趣的问题“列车出栈序列”,其中有一种解法需要用到非有序全排列,所以决定先写好本文,再总结该问题。

生成非有序全排列的算法很多,有普通递归算法,循环移位法,邻位对换法,需要中介数的递增进位排列生成算法,递减进位排列生成算法和循环左移排列生成算法等。  阅读全文

posted @ 2009-01-20 16:08 梦想飞扬 阅读(3154) | 评论 (2)编辑 收藏

2008年12月29日

     摘要: 向量旋转算法:将具有n个元素的向量a向左旋转r个位置。
例如 :将字符串"abcdefghij"旋转成"defghjabc",其中n=10,r=3。
其实就是将 AB 转换成 BA 的过程,这里A ="abc", B="defghij"。
本文总共采用了四种方法来解决向量旋转问题  阅读全文

posted @ 2008-12-29 12:36 梦想飞扬 阅读(596) | 评论 (0)编辑 收藏

2008年12月24日

     摘要: 实现了普通的查找和合并的算法,也实现了压缩路径和按大小求并高效算法,并对两者进行了测试比较。
有关算法的分析讨论详见拙作《一种简单而有趣的数据结构--并查集》  阅读全文

posted @ 2008-12-24 13:41 梦想飞扬 阅读(1125) | 评论 (0)编辑 收藏

2008年12月16日

     摘要: 曼树将字符串destCode进行译码,得到目标字符串objCode,比较objCode和sourceCode,发现完全一样!编码译码成功!最后销毁有序二叉树和赫夫曼树。
本程序的一个亮点是使用了二叉堆来存储需要合并的赫夫曼树结点,这样在求最小值时时间复杂度可以降低到log(n)。  阅读全文

posted @ 2008-12-16 22:17 梦想飞扬 阅读(2237) | 评论 (5)编辑 收藏

仅列出标题  下一页