goal00001111

2010年5月20日

迷宫类

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

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

2010年5月7日

三元组稀疏矩阵类

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

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

2010年4月16日

闲扯原码，补码和反码

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

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

2010年4月14日

稳定婚姻问题和延迟认可算法

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

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

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

2009年6月9日

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

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

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

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

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

我这里两种形式都给出。

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

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

2009年5月10日

我所理解的KMP算法

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

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

2009年1月20日

非有序全排列生成算法

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

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

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

2008年12月29日