一条学校的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以上的的匹配时间，这点也是客观的
今天晚间上网转了转，看到了，几条来自微软（Microsoft）的几条笔试试题，主要是针对微软学生中心的实习机会的，诸位如果想到微软实习的话，可以考虑自己做做看，感觉上对初学者比较困难，本人目前是没时间写代码了，最近忙者考试，诸位如果有想法的话，直接留言，或者可以跟我联系吧，
第一题
一个整数数列，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现
。0是例外，可以反复出现。
请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相
邻。
今天做了个一个简单的字符对比程序，功能是实现从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
[算法]数据结构中关于货郎担路径问题的常用解法，边界路径问题相信诸位学习过高级算法数据结构的朋友肯定是知道“货郎担问题”是很经典的图算法问题货郎担问题可以总结出4种不同的解法，主要有回溯、贪心、动态规划以下提供的算法是使用的动态规划方法，结合边界路径问题提出的算法C语言实现，调试TC平台，动规算法
代码：
Read more…
相信知道除法的作用的人都知道除法怎么来计算吧，不过计算机计算除法的方法可能优点浪费资源了以下是使用位计算转换除法的过程，相信知道游戏编程的朋友对这个应该不陌生吧
原理：假如要实现A/B,B如果是2的整数次方的话，那就不用说的，直接位移了运算如果是0，这个就不要问我了A/0等于多少我也不知道。
代码：
Read more…
Recent Comments