[算法]五子棋核心算法【转】

dskongenius 发表于 2008/11/10 10:39:26

转自 http://hi.baidu.com/tolly2008/blog/item/dd0eae098073d0266b60fb40.html　     五子棋核心算法 2007-06-27 14:26

 [算法]写了一个最长公共字符串算法，关于里面一个死循环的体会

dskongenius 发表于 2008/11/9 22:42:21

vc9.0下面编译通过，写了半个小时，调试了四个小时，原来递归时产生了一个死循环，后来终于找到错误所在，看来以前没有理解递归的真正用法。 #include <iostream>
#include <string> using namespace std; //此结构体用于存储两个字符串的相交点,第一个整数为公共字符在第一个串的位置，第二个整数为同样的公共字符在第二个串中的位置
struct disjoint
{
 int x;
 int y;
}; //比较三个整数，返回最大的整数
int max(int a,int b,int c)
{
 int maxNum=a;
 if(maxNum<b)
&n

 [算法]五子棋算法探讨【转】

dskongenius 发表于 2008/11/8 21:09:01

　　转自 http://dev.gameres.com/Program/Abstract/WuZi.htm    

阅读全文(1661) | 回复(0) | 编辑 | 精华 | 删除

 [算法]用遗传算法解决旅行商问题【转】

dskongenius 发表于 2008/6/2 12:27:00

　 用遗传算法解决旅行商问题(附源代码) 本文程序所有源代码已在《用遗传算法解决旅行商问题开源(全部源代码)》中开源。

阅读全文(2612) | 回复(1) | 编辑 | 精华 | 删除

 [算法]算法的时间复杂度

dskongenius 发表于 2007/12/20 22:58:59

定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数 T(n)称为这一算法的“时间复杂性”。

当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。

此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。

“大O记法”：在这种描述中使用的基本参数是 n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有

阅读全文(1640) | 回复(0) | 编辑 | 精华 | 删除

 [算法]Fibonacci数列的求解法

dskongenius 发表于 2007/12/20 22:52:47

　 题目:古典题目,有一对兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。假设所有的兔子都不死，问每个月的兔子总数为多少。对应的数列就是斐波那契(Fibonacci)数列。
斐波那契数列为：0、1、1、2、3、……，即：
      fib(0)=0;
      fib(1)=1;
      fib(n)=fib(n-1)+fib(n-2)      （当n>1时）。

1.递归算法：最好理解的算法,与定义公式十分吻合，和人的思路相当接近,对应的数学描述很清晰，容易编程；计算过程存在大量重复的运算，时间复杂度达到了O(2^n)，使用的内存空间也随着函数调用栈的增长而增长。这显然不适于实用的程序。
      unsigne

阅读全文(2189) | 回复(0) | 编辑 | 精华 | 删除

 [算法]Fibonacci数列

dskongenius 发表于 2007/12/20 22:38:07

快速Fibonacci数算法(Fib_Quick)
在非递归的Fibonacci程序中，在算f(n)的时候最多不超过n-2个加法，请编写一个更快的程序，或许可以用乘法。如果每一个乘法用m单位时间，每一个加法用p单位时间，于是非递归的写法因为最多有n-2个加法，因此最多用(n-2)×p的时间。请问，改良程序要用多少时间？假设只考虑加法和乘法。

解答：
考虑：
f(n) = f(n-1) + f(n-2) = 1×f(n-1) + 1×f(n-2)
f(n-1) = f(n-1) = 1×f(n-1) + 0×f(n-2)
可以用矩阵乘法来表示两个式子：
|f(n)   | = | 1 1 | ×|f(n-1)|
|f(n-1)|  

阅读全文(1677) | 回复(0) | 编辑 | 精华 | 删除

 [算法]判断点是否在多边形内的算法

dskongenius 发表于 2007/12/20 1:08:09

判断点是否在多边形内的算法如下。
以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，
考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多
边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多边形的
交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如果L和多边形的顶点相交，有些情况下交点只能计算一个
，有些情况下交点不应被计算（你自己画个图就明白了）；如果L和多边形的一条边重合，
这条边应该被忽略不计。为了统一起见，我们在计算射线L和多边形的交点的时候，1。对于
多边形的水平边不作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是其所属的边
上纵坐标较大的顶点，则计数，否则忽略；3。对于P在多边形边上的情形，直接可判断P属
于多边行。由此得出算法的伪代码如下：

1. count ← 0;
2. 以P为端点，作从右向左的射线L; 
3, for 多边形的每条边s<

阅读全文(2367) | 回复(0) | 编辑 | 精华 | 删除

 [算法]关于算法学习的入门书本

dskongenius 发表于 2007/12/20 0:30:49

关于算法学习的入门书本

1. [CLRS]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliffor
d Stein. Introduction to Algorithms. The MIT Press and McGraw-Hill, second edition, 2001. 国内有高教版影印。也有中文版。这本书一出来就取代了做了20年的经典教材[AHU]。提供了初级到中级课程的材料，而且chapter notes指引了进一步阅读的方向。四个作者都极猛。

2. [KT]Jon Kleinberg and Eva Tardos, Algorithm Design, Addison-Wesley, 2005.国
内有清华影印版。
观点很新的书。两个作者都在Cornell教了好多年的算法课，而且在纯理论之外都有所侧重
。习题非常之精彩，而且大部分都是Cornell这些年的作业或者习题。

清华Yao的课就是用上面两本教材，课文是[CLRS]，[K

阅读全文(1905) | 回复(0) | 编辑 | 精华 | 删除

 [算法][转]李开复－算法的力量

dskongenius 发表于 2007/12/5 15:24:39

算法是计算机科学领域最重要的基石之一，但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解，认为学计算机就是学各种编程语言，或者认为，学习最新的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。在“开复学生网”上，有位同学生动地把这些基础课程比拟为“内功”，把新的语言、技术、标准比拟为“外功”。整天赶时髦的人最后只懂得招式，没有功力，是不可能成为高手的。
算法与我
当我在1980年转入计算机科学系时，还没有多少人的专业方向是计算机科学。有许多其他系的人嘲笑我们说：“知道为什么只有你们系要加一个‘科学’，而没有‘物理科学系’或‘化学科学系’吗？因为人家是真的科学，不需要画蛇添足，而你们自己心虚，生怕不‘科学’，才这样欲盖弥彰。”其实，这点他们彻底弄错了。真正学懂计算机的人（不只是“编程匠”）都对数学有相当

阅读全文(1460) | 回复(0) | 编辑 | 精华 | 删除