圣诞前夜讲点比较具有圣诞感觉的算法，背包问题算法，这里我写了经典算法和贪心算法两种解决方法，因为时间不多，所以给出的数组是已经排序的，因为贪心算法可能要用得到，经典算法因为是一个一个比较，因此排序也就没有那么重要了，可能两种算法的最终运行效果一样的，朋友们调试的时候记得修改我给出的测试数组，今天实在太忙了，贪心使用的排序算法没有写，留着以后给大家讲排序算法的时候使用吧，圣诞快乐，诸位朋友们。
背包问题：就是现在有一个容量为PSIZE的背包，同时又有N件item，现在要求将这些item放入这个背包里面去，要求尽量放一定要求的item（比如按照大小的顺序），又要求放最多的item或者放的item权值之和要最大
首先大家祝福平安夜快乐啊，今天要发布的代码是一款C语言编写的模拟操作系统管理进程的程序调试环境TC，使用了PCB进行进程管理控制，建立三个基本的队列：等待、执行、阻塞进行模拟操作系统的进程管理，模拟进程的调度，模拟用户的创建、执行、阻塞、挂起、唤醒等操作
最近要准备准备操作系统考试，所以放一个程序跟大家分享
今天写点简单的，C语言求解八皇后问题，相信学过C语言的朋友一定知道这个经典问题吧，解法也是多种，目前主要有回溯，递推两种方法，今天讲回溯+递归的求法，效率可能不太高，不过直接易于理解
问题 ： 能不能在一个标准的国际象棋棋盘上放8个皇后，使她们相互之间不能互吃具体点就是，在一个8*8的棋盘上放皇后，皇后是所有方向上都可以移动的，现在要让她们不能互吃的话就要使得她们不会在同一条线上
具体解法：从第一行第一列的位置开始放棋子（假定列优先），然后记录其占用的行斜直线的编号，然后放第二个棋子，在排除前面所有棋子的所占的编号的情况下选择到有效位置，然后继续，直到放满8个棋子为止
一条学校的ACM演练题目，很让人郁闷
今天之所以想讲关于求质数的算法，完全跟这条题目有关，看到题目的朋友一定现在已经有了思路了吧，不过下面的讲解会让你很郁闷，hoho，带上你的思维，跟着我来
第一，分析题目 排除10000以内，就是求一个质数满足其的值等于两个质数的平方和就是要满足
K= A^2 + B^2 这个要求，其中A，B是质数，K当然是要求的质数，那好解法可以这样求一个质数，然后再求出另一个不同的，为什么不同，要是相同 K>2的话，K肯定不质数了，好然后再平方啊，再来相加，最后再验证所得的K是不质数了，结果出来，说实话，当你等待了N秒之后发现结构仍然没有出来之后的时候你会觉得自己的算法该优化了，其实我开始是这么想的，结果。。。
今天考试的题目是记不得了，等题目公开了再给大家分析，今天讲点经典的算法，求质数，相信很多人还是记得当年的穷举法了吧，就是不断的让每一个数除以一个小于他的数最大到sqrt(N)，然后得出结果,算法时间复杂度O(N^2)，优化过的算法O(N * sqrt(N))，经典的算法我就不讲了，初学者如果不懂的话，可以留言，或者跟我联系
今天继续昨天的话题，字符串匹配算法之BM算法，BM可以说是继KMP算法之后更加优秀的字符串匹配算了，BM 是大师Boyer-Moore的算法杰作， 所以称BM算法，相比KMP算法效率提高了不少，在空间上BM算法需要一个跟匹配字符集相同的辅助空间，已存放不同的匹配字符，比KMP要浪费不少，但是这也是BM的特色，可以在不同的字符集使用，两个字符集的话那就放一个字符集同大小的辅助空间就好，最复杂字符就很好了，目前大部分的高级语言比如C#都使用了BM及其改进算法(AC-BM算法)，相比KMP匹配两个中文字符出现的半角结果而言，我还是偏好BM ，虽然浪费空间，但是，实现接近低于线性的消耗，少了一个n以上的的匹配时间，这点也是客观的
今天做了个一个简单的字符对比程序，功能是实现从A串删除包含B最多的字符的操作，比如A=“aaaaabbbbbbabababa” B=“aaccbaab”，应当删除“aab”的，不是aa，相信知道搜索引擎的朋友肯定是知道的吧，这种算法主要用于去除页面中无效的关键字，来减少收录的计算消耗的一种方法，好了，具体算法明天拿出来吧，不过今天要讲的是两种比较常用的字符串匹配算法，KMP算法，索引法
KMP算法 是Knuth, Morris, Pratt三位前人提出的字符串快速匹配算法，简称KMP算法，典的算法了，还有以后发展的BM 和AB-BM算法，别急啊，这个下次再讲，最近是没时间写博客了，原理很简单，就是使用了额外的数值记录索引匹配的次数，然后根据这个结果进行结果计算的方法，不知道？可以参阅
http://www.chinaitpower.com/A/2003-01-04/45995.html
Recent Comments