starfish-CSDN博客

原创利用对手论证法证明中位数问题的比较次数下界

5个数通过6次比较求中位数的方法如下：5个数之间的大小关系构成的一个树形图T。T中的一个结点代表一个数，而一条边代表它所关联的两个数的大小关系，T的根就是中位数。显然T中的一条边要由一次比赛来确定。在下面的图中，如果x大于y，则节点x在节点y的上方且x和y有一条边相连。另外，*表示一般的数，o表示下一次即将进行比较的两个数。第1步，先任取两个数比较，结果为： * | * o o

2002-07-06 23:28:00 3420

原创 COMPUTING MACHINERY AND INTELLIGENCE -- BY A.M.TURING

COMPUTING MACHINERY AND INTELLIGENCE BY A.M.TURING1 The Imitation Game I PROPOSE to consider the question, Can machines think? This should begin with definitions of the meaning of the terms m

2002-03-25 08:50:00 3621

A* 算法求解最短路径--------------------------------------------------------------------------------　　近来不少的朋友问我关于 A* 算法的问题, 目的是写一个搜索最短路径的程序. 这个在鼠标控制精灵运动的游戏中(不算智冠出的那些用鼠标充当键盘方向键的弱智 RPG) 大量使用,尤其是即时战略类的. 但是我个人认为 A

2002-03-22 17:41:00 3236

原创关于goto语句

在60年代末和70年代，关于goto语句的争论是比较激烈的。主张从高级语言中去掉goto语句的人认为：goto语句是对程序结构影响最大的一种有害语句；他们的主要理由是：goto语句使程序的静态结构和程序的动态执行之间有很大的差别，这样使程序难以阅读，难以查错。对一个程序来说，人们最关心的是他运行的正确与否，去掉goto语句后，可以直接从程序结构上反映程序的运行过程。这样，不仅使程序的结构清晰、

2002-03-22 17:40:00 2661

原创关于hash

简单来说，hash就是找到一种数据内容和数据存放地址之间的映射关系。比如，由若干字符串要存放到一个哈西表中，希望能够在O(1)的时间内在表中定位某个特定的字符串，我们可以用数组来实现哈西表，找到某种函数sting -> integer，记为 p = f(s)，其中p是一个整数，s是一个字符串，p就是字符串s在数组中的下标。这样如果需要在数组中定位s，只要直接根据函数p=f(s)就可以计算s的位置。

2002-03-22 17:40:00 1822 1

原创数据结构FAQ

1.何谓数据结构?数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。数据结构是信息的一种组织方式，其目的是为了提高算法的效率

2002-03-22 17:40:00 1496

原创带？和＊的正则表达式的匹配

规定x[i]表示字符串x的第i个字符，注意，这里的下标从1开始。定义一个函数Match[i, j]，表示特征串x的长度为i的前缀与字符串的s的长度为j的前缀是否匹配。经过分析可以写出如下的递归公式：Match[i,j] = Match[i-1, j-1], if x[i] = ? = Match[i-1, 1..j]中任何一个等于true, if x[i]=*

2002-03-22 17:40:00 1351

原创关于Huffman 压缩

关于Huffman 压缩0.原理 Huffman编码是一种可变长编码方式，是由美国数学家David Huffman创立的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffman算法的最根本的原则是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的

2002-03-22 17:40:00 2555 2

原创差错检测和纠正

差错检测和纠正物理过程所引起的差错，在某些介质中通常是突发的而不是单个的。网络设计者已经研究出两种基本的策略来处理差错。一种方法是在每一个要发送的数据块上附加足够的冗余信息，使接收方能够推导出已发出的字符应该是什么。另一种方法是只加足够的冗余位，使接收方知道差错发生，但不知道是什么样的差错，然后要求接收方重新进行传输。前者的策略是使用纠错码(error-correcting code)

2002-03-22 17:40:00 2408

原创 NP问题和NPC问题

什么叫做NP问题，什么叫做NPC问题? 首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。算法的复杂性是指解决问题的一个具体的算法的执行时间，这是算法的性质；问题的复杂性是指这个问题本身的复杂程度，是问题的性质。比如对于排序问题，如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是O(nlgn)，但是排序算法有很多，冒泡法

2002-03-22 17:40:00 3736 5

原创修道士过河问题

设有m个野人，n个修道士,（m≤n）船上可坐c个人。1. c=1，无解；2. c=2，对较小的M,N有解，对于较大的M,N无解，比如m=n=4，c=2无解；3. c=3，情况同上；4. c>3，分情况讨论如下：(1) m=n，此时可以按照下面的方案设计（下面S表示野人savage，R表示修道士religious， B表示船boat, ||表示河）方案一：m S || (m-c)S |

2002-03-22 17:40:00 2371

原创具有障碍物的欧几里德最短路径问题

这个问题是计算几何学中的一个经典课题：具有障碍物的欧几里德最短路径问题(ESP0)ESPO可以描述如下:给定平面中两点s和t，及多边形障碍物集Ω={ω1,ω2,...,ωk}，要求由s至t并避开所有障碍物的最短路径。平面中的ESPO问题在多项式时间内可以求解，而E^3中具有多面体障碍物时确定最短路径长度的问题是NP难的。一个简单的算法如下：由s到t的最短路径是一条折线链，该链的顶点是多

2002-03-22 17:40:00 4406

原创狼追兔子问题的解答

这道题的数论解法这道题在许多教科书上都有，一般是用循环线性表来模拟狼的行动，找到安全的洞。但是，对于n很大的情况，一来线性表要占用很大的空间，二来循环搜索要花费很多时间，因此这种算法效率很低。下面我们利用数论知识设计一种高效算法。不妨让兔子躲在1号洞，因为如果狼能从0号洞到1号洞，则它一定能够从1号洞到2号,3号,..n-1号洞，兔子无论躲在哪里都难逃厄运。换而言之，若有安全的洞，1号洞必然是

2002-03-22 17:40:00 3185

原创量水问题

[量水问题]：有三个分别装有a升水，b升水，c升水的量筒，其中a,b互质，c>b>a>0，现在c筒装满水，问能否在c筒中量出d升水(c>d>0)。若可以，给出方案。解答：所谓模数方程，就是模线性方程，即形如 ax ≡ b (mod c) 形式的方程，其中a,b,c是常数，x是自变量，这个方程表示ax mod c = b mod c，即ax和b模c同余。这个量水问题，用模数方程解比较方便，具

2002-03-22 17:40:00 3896

原创微软面试题之数字谜题

设有两个自然数m,n，2〈=mS：我知道你不知道这两个数是什么，但我也不知道。P：现在我知道这两个数了。S：现在我也知道这两个数了。由这些条件，试确定m，n。因为S知道两数之和，却由此推断P不知道两个数，所以说两数之和s一定不能拆分成两个素数的和，即m,n不可能都是素数，且m,n中不会有大于50的素数，否则的话m*n可以唯一分解，P知道了m,n的积就一定可以知道m,n了。P从S的言语中能

2002-03-22 17:38:00 1450

原创回溯法解决喝酒问题

回溯法解决喝酒问题先介绍一下回溯法的理论：可用回溯法解决的问题P，通常能够表达为：对于已知的、由n元组(x1,x2,……，xn)组成的一个状态空间 E={(x1,x2,……，xn) | xi ∈Si, i=1,2,..,n}，给定关于n元组中的分量的一个约束集D，要求E中满足D的全部约束的所有n元组。其中Si是分量xi的定义域且|Si|有限，i=1,2,...n。我们称E中满足D的全部

2002-03-22 17:38:00 1747

原创优先队列

下面是数组实现的二叉堆，其中MAX_SIZE是数组的最大长度；ElementType是其中元素的类型；Priority(x: ElementType) 是一个函数，返回值是元素x的优先级，当然也可以用一个Priority数组来保存每个元素的优先级(在这个打字员问题中就应该用一个数组来保存每个元素的优先级，在这个问题中优先级就是从初始密码转换到该密码所需的操作的数目)。type Priority

2002-03-22 17:38:00 1139

原创遗传算法

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质

2002-03-22 17:38:00 6188

原创砝码称重问题

定理：由m个数构成的由小到大排列的数列{a(1),a(2),...a(m)}，设A(k)=∑a(i)，其中i从1到k，则a(1) = 1且a(j+1) 是该数列作为砝码序列可称量{0,1,..,Am}范围内的任意整数重量的充要条件。特别的，上式取等号时，该序列是唯一可能的砝码序列，并且有a(j) = 3^(j-1)，对于j=1,2,..,m推论：重量为n的物体要分成m份重量为整数的物

2002-03-22 17:38:00 1655

原创海盗分金块问题

数学的逻辑有时会导致看来十分怪异的结论。一般的规则是，如果逻辑推理没有漏洞，那么结论就必定站得住脚，即使它与你的直觉矛盾。 1998年9月，加利福尼亚州帕洛阿尔托的Stephen M. Omohundro寄给我一道难题，它恰好就属于这一类。这难题已经流传了至少十年，但是Omohundro对它作了改动，使它的逻辑问题变得分外复杂了。先来看看此难题原先的形状。10名海盗抢得了窖藏的100块金子，并

2002-03-22 17:37:00 1748

原创 VB编程中的一些经验

VB编程中的一些经验1. 假设VB中有如下的变量声明： dim s1, s2 as string则s1是一个variant型变量，而s2是一个string型变量如果想要声明两个string变量s1和s2应该用： dim s1 as string, s2 as string2. VB中的对象是自动回收的，类似java在一个过程中sub Foo() dim obj as new Object

2002-03-22 17:37:00 969

原创 Delphi 6 SOAP 源码中的BUG修正

Delphi 6 SOAP 源码中的BUG修正最近我正在用delphi 6 做一个关于SOAP的项目，调试程序的时候跟踪源码发现了delphi 6的源码中的一些bug :( 在 delphi/source/soap 目录下面的XSBuiltIns.pas 文件中，第438行如下：procedure TXSDate.XSToNative(Value: WideString);va

2001-12-09 15:39:00 1317

starfish的专栏