区块链文章存档 >> blog.lidaren.com
Android-Charts技术交流QQ群现已开通,欢迎加入。群号:170987350

[算法]经典算法8皇后(N皇后)问题的解法,C语言实现

December 22nd, 2008 2 comments

今天写点简单的,C语言求解八皇后问题,相信学过C语言的朋友一定知道这个经典问题吧,解法也是多种,目前主要有回溯,递推两种方法,今天讲回溯+递归的求法,效率可能不太高,不过直接易于理解

问题 : 能不能在一个标准的国际象棋棋盘上放8个皇后,使她们相互之间不能互吃具体点就是,在一个8*8的棋盘上放皇后,皇后是所有方向上都可以移动的,现在要让她们不能互吃的话就要使得她们不会在同一条线上

具体解法:从第一行第一列的位置开始放棋子(假定列优先),然后记录其占用的行斜直线的编号,然后放第二个棋子,在排除前面所有棋子的所占的编号的情况下选择到有效位置,然后继续,直到放满8个棋子为止

Read more…

Categories: 算法研究 Tags:

求在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: , ,