博文
Miller-Rabin算法(转)(2007-03-22 23:42:00)
摘要：一.费马小定里 if n is prime and (a,n) equals one ,then a^(n-1) = 1 (mod n)
费马小定理只是个必要条件,符合费马小定理而非素数的数叫做Carmichael.
前3个Carmichael数是561,1105,1729。
Carmichael数是非常少的。
在1~100000000范围内的整数中，只有255个Carmichael数。
为此又有二次探测定理,以确保该数为素数:
二.二次探测定理
二次探测定理 如果p是一个素数，0<x<p,则方程x^2≡1(mod p)的解为x=1,p-1
根据以上两个定理,如到Miller-Rabin算法的一般步骤:
0、先计算出m、j，使得n-1=m*2^j，其中m是正奇数，j是非负整数
1、随机取一个b，2<=b
2、计算v=b^m mod n
3、如果v==1，通过测试，返回
4、令i=1
5、如果v=n-1，通过测试，返回
6、如果i==j，非素数，结束
7、v=v^2 mod n，i=i+1
8、循环到5
说明:
Miller-Rabin是随机算法
得到的结果的正确率为 75%,所以应该多次调用该函数,使正确概率提高为
1-(1/4)^p
//功能实现
#include <stdio.h>#include <stdlib.h>#include <algorithm>#include <functional>
typedef __int64 lltype;const int MAX_COUNT = 6;//测试次数lltype allFactor[65], nFactor;//质因分解结果(刚返回的时候是无序的)void fFindFactor(const lltype &num);//主函数(num > 1)
lltype pollard_rho(const lltype &c, const lltype &num);bool miller_rabin(const lltype &n, int count);//miller-rabinbool fWitNess(const lltype &a......
(转)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......
类设计者的核查表(2007-03-09 00:10:00)
摘要：摘自<<c++沉思录>>
1.你的类需要一个构造函数吗？
2.你的数据成员是私有的吗？
3.你的类需要一个无参的构造函数吗？
4.是不是每个构造函数初始化所有的数据成员？
5.类需要析构函数吗？
6.类需要一个虚析构函数吗？
7.你的类需要复制构造函数吗？
8.你的类需要一个赋值操作符吗？
9.你的赋值操作符能正确地将对象赋给对象本身吗？
10.你的类需要定义关系操作符吗？
11.删除数组时你记住了用delete[]吗？
12.记得在复制构造函数和赋值操作符的参数类型中加上const
了吗？
13.如果函数有引用参数，它们应该是const引用吗？
14.记得适当地声明成员函数为const的了吗？......
杂类集(2007-02-03 21:17:00)
摘要： Great Common Divisor最大公约数
n1.Euclid算法
重复gcd(a,b) = gcd(a,b mod a)至b mod a等于0 ，
gcd(b,0)=b, b最后的取值为a,b初值的最大公约数
2.stein算法
1.
1.如果A=0，B是最大公约数，算法结束
2. 如果B=0，A是最大公约数，算法结束
3. 设置A1 = A、B1=B和C1 = 1
4. 如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(乘2整数左移一位，除2整数右移一位即可)
5.
5.如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (显然，2不可能为任何奇数的约数)
6.
6.如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (同上J)
7. 如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn
8. n++，转4
注：、Cn为两数最大公约数
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
给定两个任意正整数n和任一质数p,求将n!表示成算术基本定理的形式的时候，p的指数．
count=0;
while(n)
{
count+=n/p;
n/=p;
}
cout<<count<<endl;
......
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’)......
计算几何算法概览(转)(2006-09-06 21:28:00)
摘要：
怒火之袍
计算几何算法概览
一、引言
计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。
二、目录
本文整理的计算几何基本概念和常用算法包括如下内容：
矢量的概念
矢量加减法
矢量叉积
折线段的拐向判断
判断点是否在线段上
判断两线段是否相交
判断线段和直线是否相交
判断矩形是否包含点
判断线段、折线、多边形是否在矩形中
判断矩形是否在矩形中
判断圆是否在矩形中
判断点是否在多边形中
判断线段是否在多边形内
判断折线是否在多边形内
判断多边形是否在多边形内
判断矩形是否在多边形内
判断圆是否在多边形内
判断点是否在圆内
判断线段、折线、矩形、多边形是否在圆内
判断圆是否在圆内
计算点到线段的最近点
计算点到折线、矩形、多边形的最近点
计算点到圆的最近距离及交点坐标
计算两条共线的线段的交点
计算线段或直线与线段的交点
求线段或直线与折线、矩形、多边形的交点
求线段或直线与圆的交点
凸包的概念
凸包的求法
三、算法介绍
矢量的概念：
如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。
矢量加减法：
设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为： P - Q = ( x1 -......
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为很大时......