Android-Charts技术交流QQ群现已开通,欢迎加入。群号:170987350
Android-Charts技术社区网站http://faq.android-charts.com/

求在10000范围内的所有质数,要求其的值等于两个质数的平方和

December 21st, 2008 No comments

一条学校的ACM演练题目,很让人郁闷

今天之所以想讲关于求质数的算法,完全跟这条题目有关,看到题目的朋友一定现在已经有了思路了吧,不过下面的讲解会让你很郁闷,hoho,带上你的思维,跟着我来

第一,分析题目 排除10000以内,就是求一个质数满足其的值等于两个质数的平方和就是要满足

K= A^2 + B^2 这个要求,其中A,B是质数,K当然是要求的质数,那好解法可以这样求一个质数,然后再求出另一个不同的,为什么不同,要是相同 K>2的话,K肯定不质数了,好然后再平方啊,再来相加,最后再验证所得的K是不质数了,结果出来,说实话,当你等待了N秒之后发现结构仍然没有出来之后的时候你会觉得自己的算法该优化了,其实我开始是这么想的,结果。。。

Read more…

Categories: 算法研究 Tags:

[算法]用两种求质数的算法(穷举法,筛选法),C语言实现

December 21st, 2008 1 comment

今天考试的题目是记不得了,等题目公开了再给大家分析,今天讲点经典的算法,求质数,相信很多人还是记得当年的穷举法了吧,就是不断的让每一个数除以一个小于他的数最大到sqrt(N),然后得出结果,算法时间复杂度O(N^2),优化过的算法O(N * sqrt(N)),经典的算法我就不讲了,初学者如果不懂的话,可以留言,或者跟我联系

Read more…

Categories: 算法研究 Tags: , ,

[算法]字符串匹配算法之BM算法,C语言实现

December 20th, 2008 2 comments

今天继续昨天的话题,字符串匹配算法之BM算法,BM可以说是继KMP算法之后更加优秀的字符串匹配算了,BM 是大师Boyer-Moore的算法杰作, 所以称BM算法,相比KMP算法效率提高了不少,在空间上BM算法需要一个跟匹配字符集相同的辅助空间,已存放不同的匹配字符,比KMP要浪费不少,但是这也是BM的特色,可以在不同的字符集使用,两个字符集的话那就放一个字符集同大小的辅助空间就好,最复杂字符就很好了,目前大部分的高级语言比如C#都使用了BM及其改进算法(AC-BM算法),相比KMP匹配两个中文字符出现的半角结果而言,我还是偏好BM ,虽然浪费空间,但是,实现接近低于线性的消耗,少了一个n以上的的匹配时间,这点也是客观的

Read more…

分享几条来自微软(Microsoft)的算法设计笔试试题

December 19th, 2008 4 comments

今天晚间上网转了转,看到了,几条来自微软(Microsoft)的几条笔试试题,主要是针对微软学生中心的实习机会的,诸位如果想到微软实习的话,可以考虑自己做做看,感觉上对初学者比较困难,本人目前是没时间写代码了,最近忙者考试,诸位如果有想法的话,直接留言,或者可以跟我联系吧,

第一题
一个整数数列,元素取值可能是0~65535中的任意一个数,相同数值不会重复出现
。0是例外,可以反复出现。
请设计一个算法,当你从该数列中随意选取5个数值,判断这5个数值是否连续相
邻。

Read more…

Categories: 算法研究 Tags:

[算法]两种字符串匹配算法(索引法,KMP算法)对比,C语言实现

December 19th, 2008 No comments

今天做了个一个简单的字符对比程序,功能是实现从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

Read more…

Categories: 算法研究 Tags: ,

[SQL]两条学校索迪杯软件大赛预赛试卷SQL语句考试试题

December 18th, 2008 4 comments

今天参加了学校的索迪杯预赛考试,结果看到试卷上的日文就懵了,考这玩意要考日文?就跟美国GRE考试要考《论语》一样,反正很变态!!不过还有两条比较经典的SQL题目值得跟大家分享,适合SQL的初学者学习,好像俺也就是算个初学者吧,好了,看题目。

第一题 用SQL判断今年或者某一年是否是闰年
说明:SQL?闰年?两者好像没多大关系吧,跟考试考日文一样,真佩服考官了,不过详细用过SQL server2000的朋友肯定知道NOW()这个函数,我一开始也是这么想的,可是now()包含太多的无用信息了,而且处理比较麻烦,于是又想到另一个函数GETDATE(),目前在MSSQL2000可用,其他的不太清楚,可以参阅用户手册,GETDATE()的返回信息是今天的日期。

Read more…

Categories: 语言编程 Tags: , ,

[算法]数据结构中关于货郎担路径问题的常用解法,边界路径问题

December 17th, 2008 6 comments

[算法]数据结构中关于货郎担路径问题的常用解法,边界路径问题相信诸位学习过高级算法数据结构的朋友肯定是知道“货郎担问题”是很经典的图算法问题货郎担问题可以总结出4种不同的解法,主要有回溯、贪心、动态规划以下提供的算法是使用的动态规划方法,结合边界路径问题提出的算法C语言实现,调试TC平台,动规算法

代码:
Read more…