博文
(转)Prime Numbers, Factorization and Eule(2007-03-11 23:51:00)
摘要：Prime numbers and their properties were extensively studied by the ancient Greek mathematicians. Thousands of years later, we commonly use the different properties of integers that they discovered to solve problems. In this article we’ll review some definitions, well-known theorems, and number properties, and look at some problems associated with them.
A prime number is a positive integer, which is divisible on 1 and itself. The other integers, greater than 1, are composite. Coprime integers are a set of integers that have no common divisor other than 1 or -1.
The fundamental theorem of arithmetic:Any positive integer can be divided in primes in essentially only one way. The phrase 'essentially one way' means that we do not consider the order of the factors important.
One is neither a prime nor composite number. One is not composite because it doesn’t have two distinct divisors. If one is prime, then number 6, for example, has two different representations as a product of prime nu......
hash function(2006-09-29 22:02:00)
摘要：经典字符串中出现的hash函数
（转载自http://www.ccw.com.cn/htm/app/aprog/01_8_22_3.asp）
1． PHP中出现的字符串Hash函数
static unsigned long str_hash_function (char *arKey , unsigned int nKeyLength) {
int h=0;
int g;
char *arEnd=arKey+nKeyLength;
while (arKey<arEnd) {
h=(h<<4)+*arKey++;
if ((g=(h&0xF0000000))) {
h=h^(g>>24);
h=h^g;
}
}
return h;
}
2． OpenSSL中出现的字符串Hash函数
unsigned long str_hash_function (char *str) {
int i , l;
unsigned long ret=0;
unsigned short *s;
if (str==NULL) return (0);
l=(strlen(str)+1)/2;
s=(unsigned short *) str;
for (i=0;i<l;i++) {
ret^=(s[i]<<(i&oxof));
return ret;
}
unsinged long str_hash_function2 (const char *str) {
unsigned long ret=0;
long n;
unsigned long v;
int r;
if ((c==NULL)||(*c==’\0’)......
Bellman-Ford算法(2006-09-05 22:16:00)
摘要：该算法用来求边上权值为任意值的单源最短路径问题
伪代码如下：
void bellman_ford(int v)
{
for 1 to n
initialize dist[i][v]; //此时只经过一条边
for 2 to n-1 (i) //经过的边数不大于i条时
for 1 to n (j) //对于每一个目标顶点
for 1 to n (k) //经过该顶点时，与当前最小值比较，并更新当前值
if edge[k][j] > 0 && dist[k] > edge[k][j]+dist[j]
更新当前值
}//
......
LIS(2006-08-20 21:04:00)
摘要：#include <iostream>using namespace std;
#define MAXNUM 1000
char c[MAXNUM];char b[MAXNUM+1];
void solve(){ int i,first,last,mid,len; len = 1; i = 1; b[1] = c[0]; while (c[i]) { first = 1; last = len+1; while (first < last) { mid = (first+last)>>1; if (b[mid] < c[i])first = mid+1; else last = mid; ......
Josephus问题的数学方法(转)(2006-08-20 11:02:00)
摘要： 无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。为了讨论方便，先把问题稍微改变一下，并不影响原意：问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）: k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。现在我们把他们的编号做一下转换：k --> 0k+1 --> 1k+2 --> 2......k-2 --> n-2k-1 --> n-1变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]递推公式f[1]=0;f[i]=(f[i-1]+m)%i; (i>1)有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1由于是逐级递推，不需要保存每个f[i]，程序也是异常简单：＃i nclude <stdio.h>main(){&......
费马最後定理（转）(2006-08-19 20:13:00)
摘要：被公认执世界报纸牛耳地位地位的纽约时报於1993年6月24日在其一版头题刊登了一则有关数学难题得以解决的消息，那则消息的标题是「在陈年数学困局中，终於有人呼叫『我找到了』」。时报一版的开始文章中还附了一张留着长发、穿着中古世纪欧洲学袍的男人照片。这个古意盎然的男人，就是法国的数学家费马（Pierre de Fermat）（费马小传请参考附录）。费马是十七世纪最卓越的数学家之一，他在数学许多领域中都有极大的贡献，因为他的本行是专业的律师，为了表彰他的数学造诣，世人冠以「业余王子」之美称，在三百六十多年前的某一天，费马正在阅读一本古希腊数学家戴奥芬多斯的数学书时，突然心血来潮在书页的空白处，写下一个看起来很简单的定理这个定理的内容是有关一个方程式 x2 + y2 =z2的正整数解的问题，当n=2时就是我们所熟知的毕氏定理（中国古代又称勾股弦定理）：x2 + y2 =z2，此处z表一直角形之斜边而x、y为其之两股，也就是一个直角三角形之斜边的平方等於它的两股的平方和，这个方程式当然有整数解（其实有很多），例如：x=3、y=4、z=5；x=6、y=8、z=10；x=5、y=12、z=13…等等。
费马声称当n>2时，就找不到满足xn +yn = zn的整数解，例如：方程式x3 +y3=z3就无法找到整数解。
当时费马并没有说明原因，他只是留下这个叙述并且也说他已经发现这个定理的证明妙法，只是书页的空白处不够无法写下。始作俑者的费马也因此留下了千古的难题，三百多年来无数的数学家尝试要去解决这个难题却都徒劳无功。这个号称世纪难题的费马最後定理也就成了数学界的心头大患，极欲解之而後快。
十九世纪时法国的法兰西斯数学院曾经在一八一五年和一八六０年两度悬赏金质奖章和三百法郎给任何解决此一难题的人，可惜都没有人能够领到奖赏。德国的数学家佛尔夫斯克尔（P‧Wolfskehl）在1908年提供十万马克，给能够证明费马最後定理是正确的人，有效期间为100年。其间由於经济大萧条的原因，此笔奖额已贬值至七千五百马克，虽然如此仍然吸引不少的「数学痴」。
二十世纪电脑发展以後，许多数学家用电脑计算可以证明这个定理当n为很大时......
最小生成树(2006-08-17 15:23:00)
摘要：public static void prim(int n,float [][]c){ float []lowcost = new float[n+1]; int []closest = new int[n+1]; boolean []s = new boolen[n+1]; s[1] = true; for (int i = 2; i <= n; i++) { lowcost = c[1][i]; closest[i] = 1; s[i] = false; } for (int i=1; i < n; i++) { float min = Float.MAX_VALUE; int j = i; for (int k = 2; k <= n; k++) { &n......
随机排序算法(2006-08-07 16:01:00)
摘要：void InterChange(int a[],int i,int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
int partition(int a[],int p,int q)
{
int v = a[p],i = p,j = q;
do{
do i++;
while (a[i] < v);
do j--;
while (a[j] > v);
if (i < j)InterChange(a,i,j);
}while (i < j);
a[m] = a[j];a[j] = v;
return j;
}
void RQuickSort(int a[],int p,int q)
{
if (p < q)
{
if (q-p > 5)InterChange(a,rand()%(q-p)+p,p);
int j = partition(a,p,q);
RQuickSort(p,j);
RQuickSort(j,q);
}
}
PS：随机排序算法的时间复杂度也是O(nlogn),但算法的平均性能是很好的。在解POJ1186题时，用分治＋二分查找算法，要用到排序，排序的对象最多有33万个，如果用qsort或sort可能会超时，但我用上面的RQuickSort就AC了。由此可见，当对象数目很多时，RQuickSort的性能要比qsort,sort要好。......
集合的全排列(2006-07-19 16:37:00)
摘要： 设R={r1,r2,r3,....,rn}是要进行排列的n个元素，Ri=R - {ri}.集合X中元素的全排列 记为perm(X).(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀ri,得到的排列。 R的全排列可归纳如下定义如下： 当n=1时，perm(R)=perm(r),其中r是集合R中的唯一元素。 当n>1时，perm(R)的全排列可由(r1)perm(R1),(r2)perm(R2),....,(rn)perm(Rn)构成。 依此定义，可产生计算集合R的全排列的算法如下： public static void perm(Object []list,int k,int m) { //产生list[k,m]的所有排列 if (k == m) { //单元素序列 for (int i = 0; i <= m; i++) System.out.print(list[i]); System.out.println(); } else&n......
（转）初识A*算法(2006-06-25 00:58:00)
摘要： 写这篇文章的初衷是应一个网友的要求，当然我也发现现在有关人工智能的中文站点实在太少，我在这里抛砖引玉，希望大家都来热心的参与。
还是说正题，我先拿A*算法开刀，是因为A*在游戏中有它很典型的用法，是人工智能在游戏中的代表。
A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，我看还是先说说何谓启发式算法。
一、何谓启发式搜索算法
在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一条解题的过程可以从求解的开始到问题的结果（好象并不通俗哦）。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。
常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。
前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。
启发中的估价是用估价函数表示的，如：
f(n) = g(n) + h(n)
其中f(n)是节点n的估价函数，g(n)实在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n)&......