博文
[math]GIMPS如何搜索梅森数？(2007-03-30 22:37:00)
摘要：本页面讨论用于高效地搜索梅森素数的数学和计算机算法的一些知识。由于相对于数学家，我更多地是计算机程序员，因此我将不深入到太多的数学细节中，而是设法提供链接代替。
生成一个列表(Forming a list)
很容易证明，如果 2P-1 是素数，则 P 也一定是素数。因此，搜索梅森素数的第一步就是生成一个用于测试的素数指数列表。
试验分解因子(Trial Factoring)
下一步是通过寻找小因子来排除一些指数。有一个非常高效的算法判断一个数是否能整除 2P-1。例如，让我们看一下 47 是否能够整除 223-1。把指数 23 转换成二进制数，我们得到 10111。从 1 开始，重复以下步骤：平方，删除指数的最左边二进位，如果该位是 1，则将平方后得到的值乘以 2，然后计算其除以 47 后的余数。 删除最左 如果需要就 除以47
平方 边二进位 乘以 2 的余数
------------ ------- ------------- ------
1*1 = 1 1 0111 1*2 = 2 2
2*2 = 4 0 111 no 4
4*4 = 16 1 11 16*2 = 32 32
32*32 = 1024 1 1 1024*2 = 2048 27
27*27 = 729 1 729*2 = 1458 1
因此，223 = 1 mod 47。两边同时减 1，223-1 = 0 mod 47。因此我们知道 47 是一个因子，从而 223-1 不是素数。
可以证明梅森数有一个非常好的性质：2P-1 的任何因子 q 必定是 2kP+1 的形式，并且 q 除以 8 的余数一定是 1 或者 7。最后，一个高效的程序可以利用任何可能的因子 q 必须是素数这一事实。
GIMPS 程序的分解因子代码使用修正的厄拉托森斯(Eratosthenes)筛法，利用一个......
人工智能(2007-03-30 22:30:00)
摘要：
八数码问题—A*搜索
先把问题简化一下吧：
在控制台显示这样一个矩阵
[1][2][3]
[8] [4]
[7][6][5]
手动把它打乱，然后让程序将其复原。
和野人传教士问题类似，这也是一个对解空间进行搜索的问题，而且更为简单，这次采用可以缩减扩展节点的规模的A*启发式搜索算法。取节点深度为g(x)，错位的数字数为h(x)，由于问题很简单，所以与有序搜索算法类似，算法框图：
评价函数封装在类里，所以没显示在框图中。
ElemType类包括了对于状态节点所需的所有操作：显然的，用一个一维数组maze[9]保存这九个位置的数，评价函数evaluate()函 数返回当前状态的评价值，对节点进行操作的运算符">>"，判断是否是最终节点的isSuccess()，以及打乱初始节点的顺序的 disrupt()等等。
#include <iostream>
#include <conio.h>
#include <windows.h> //显示矩阵时需要延时，这里有Sleep()函数。
using namespace std;
//接收键盘时使用
const enum Input { UP = 0x048, DOWN = 0x050, LEFT = 0x04b, RIGHT = 0x04d, ENTER = 0xd };
//扩展时判断方向使用
const int U = 0;
const int D = 1;
const int L = 2;
const int R = 3;
class ElemType {
private:
int depth; //当前节点的深度（就是距离初始节点有多远）
int numWrong(); //有多少错位的数字
public:
int maze[9]; &n......
用C语言实现八数码问题 (2007-03-30 22:28:00)
摘要：
#include<stdio.h>
#include<conio.h>
int n,m;
typedef struct Node
{
char matrix[10];/*存储矩阵*/
char operate;/*存储不可以进行的操作，L代表不能左移R代表不能右移U代表不能上移D代表不能下移*/
char extend;/*是否可以扩展，Y代表可以，N代表不可以*/
int father;/*指向产生自身的父结点*/
}Node;
char start[10]={"83426517 "};/*此处没有必要初始化*/
char end[10]={"1238 4765"};/*此处没有必要初始化*/
Node base[4000];
int result[100];/*存放结果的base数组下标号，逆序存放*/
int match()/*判断是否为目标*/
{
int i;
for(i=0;i<9;i++)
{
if(base[n-1].matrix[i]!=end[i])
{
return 0;
}
}
return 1;
}
void show()/*显示矩阵的内容*/
{
int i=1;
while(m>=0)
{
int mm=result[m];
clrscr();
printf("\n\n\n http://www.zhensoft.com ZHEN SHI LEI\t\tStep %d",i);
printf("\n\n\n\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[0],base[mm].matrix[1],base[mm].matrix[2]);
&nbs......
A*算法求八数码问题总结 (2007-03-30 22:25:00)
摘要：
A*算法求八数码问题总结
最近在PKU的ACM上做了八数码问题，将经验总结以下：
（1） 用A*算法， 估价函数选“Hamilton距离”比选用“在错误方各内的数字数目”强很多。
（2）A*算法的关键是要能够使“找到耗费最小的节点”和“判断是否子节点已经存在”的算法的效率尽可能高，为此，网上不少资料建议采用Binary Heap或Hash table等数据结构，然而单独使用任何一种数据结构，都有一定的缺陷，将Heap和Hash联合起来使用，应该可以提高不少效率。具体如下：
1。建一张Hash表，存放没一个节点的具体信息，如当前状态、父节点在表中的位置等。
2。open表中存放着一些节点，这些节点不同于Hash表中的节点，可以将它理解为是Hash表中节点的索引，它只包含节点的估价和节点在Hash表中的位置，这些节点按估价排列成堆（Heap）。
3。没必要再建一个closed表。
这样，程序的流程就可以写成：
初始化Hash表和open表；
将根节点放入Hash表和open表；
found = false;
while(open表不空) {
从open表中得到耗费最低的节点的索引cur; // O(1)
从open表中删除耗费最低的节点; // O(logN)
for 每个cur的子节点now do {
if ( now 是目标节点 ) {
打印输出;
&n......
求素数问题(2007-03-30 12:10:00)
摘要：求素数问题
求素数问题（很典型的问题）
以下是求解素数的三种方法，大家可以按照算法写出程序代码。
【1】求10000以内的所有素数。
素数是除了1和它本身之外再不能被其他数整除的自然数。由于找不到一个通项公式来表示所有的素数，所以对于数学家来说，素数一直是一个未解之谜。像著名的哥德巴赫猜想、孪生素数猜想，几百年来不知吸引了世界上多少优秀的数学家。尽管他们苦心钻研，呕心沥血，但至今仍然未见分晓。
自从有了计算机之后，人们借助于计算机的威力，已经找到了2216091以内的所有素数。
求素数的方法有很多种，最简单的方法是根据素数的定义来求。对于一个自然数N，用大于1小于N的各个自然数都去除一下N，如果都除不尽，则N为素数，否则N为合数。
但是，如果用素数定义的方法来编制计算机程序，它的效率一定是非常低的，其中有许多地方都值得改进。
第一，对于一个自然数N，只要能被一个非1非自身的数整除，它就肯定不是素数，所以不
必再用其他的数去除。
第二，对于N来说，只需用小于N的素数去除就可以了。例如，如果N能被15整除，实际
上就能被3和5整除，如果N不能被3和5整除，那么N也决不会被15整除。
第三，对于N来说，不必用从2到N一1的所有素数去除，只需用小于等于√N(根号N)的所有素数去除就可以了。这一点可以用反证法来证明：
如果N是合数，则一定存在大于1小于N的整数d1和d2，使得N=d1×d2。
如果d1和d2均大于√N，则有：N＝d1×d2>√N×√N＝N。
而这是不可能的，所以，d1和d2中必有一个小于或等于√N。
基于上述分析，设计算法如下：
(1)用2，3，5，7逐个试除N的方法求出100以内的所有素数。
(2)用100以内的所有素数逐个试除的方法求出10000以内的素数。
首先，将2，3，5，7分别存放在a[1]、a[2]、a[3]、a[4]中，以后每求出一个素数，只要不大于100，就依次存放在A数组中的一个单元中。当我们求100—10000之间的素数时，可依次用a[1]－a[2]的素数去试除N，这个范围内的素数可以不保存，直接打印。
【2】用筛法求素数。
简单介绍一下厄拉多塞筛法。厄拉多塞是一......
求素数法(2007-03-30 12:10:00)
摘要：
求素数法
求素数法
素数是大于１的整数，除了它本身和１以外，不能被正整数所整除.也称作“质数”.
在欧几里得的《几何原本》中，给出了素数的定义为只能被单位量除尽的数。另外还给出了算术基本定理，即如果Ａ是素数Ｐ、Ｑ…的乘积，那么将Ａ分解成素数乘积的方法是惟一的。在《几何原本》中，已经得出素数的个有选举权是无限的。
与欧几里得同时代的数学家埃拉托色尼首先给出了求素数的方法，现在人们称之为“埃拉托尼筛子”。他求素数的方法如下。
他首先从２开始，写出自然数：２，３，４，５，６，７，８，９…１００，然后，把其中的一切合数划去，划掉合数的原则是，在这一列数中，第一个数２满足素数的定义，把它保留下来。随后把能被２整除的数都划去，因为它们都是合数。接着在数２后的没有被划去的第一个数是３，因为它只被１和它本身整除，所以它是一个合数，把它也划去。剩下没有被划去的第一个有选举权是５，它只能被这和它本身整除，所以它也是一个素数。如此连续不断地划下去，最后剩下的数都是素数。
为什么把这种方法叫做“厄拉多塞筛子”呢？因为厄拉多塞在求素数时，把自然数写在一块白蜡的木板上，并逐个在写着合数的位置上刺一个孔，这样白蜡板上被刺了很多的小孔，好像一个筛子。把所有的合数“筛掉”剩下的就都是素数。
用“厄拉多塞筛子”可得到１００以内的２５个素数：２，３，５，７，１１，１３，１７，１９，２３，２９，３１，３７，４１，４３，４７，５３，５９，６１，６７，７１，７３，７９，８３，８９，９７。
后来由于素数没有多少用处，所以数学家们就把求素数的方法“束之高阁”。直到１７世纪解析几何与微积分兴起后，许多数学家又开始对整数论进行探讨，所以对素数的研究又提到了议事的日程上，而且取得很大进展。
从厄拉多塞筛子可以得到一个复杂的公式，如果已知小于√Ｎ的素数，它能确定小于Ｎ的素数的数目，１８７０年德国人梅塞尔对此作了改进，成功地证明了１０ 8的素数是５７６１４５５个。１８９３年丹麦人贝特森证明了10 9的素数是５０８０７４７８个，１９５９年，美国数学家莱麦成功地证明了10 ９的开绿灯数应该是５０８４７５３４个，并且得到了１０ 10的素数是４......
二十世纪数学家排名(前100位): (2007-03-30 12:09:00)
摘要：二十世纪数学家排名(前100位):
点击数：8 发布日期：2007-3-29 23:04:00
【收藏】 【评论】 【打印】 【编程爱好者论坛】 【关闭】
二十世纪数学家排名(前100位):
1,A.N.Kolmogorov
2,H.Poincare
3,D.Hilbert
4,A.E,Nother
5,von Neumann
6,H.weyl
7,A.Weil
8,I.M.Gelfand
9,Wiener
10,Alxsandrff
11,Ledesque
12,Shafarevich
13,V.I.Arnold
14,Dedekind
15,Markov
16,Klein
17,E.Artin
18,Jordan
19,Siegel
20,Sobolev
21,J.P.Serre
22,Gorthenideck
23,Whiteny
24,E.Cartan
25,Thom
26,Milnor
27,Hadamand
28,Godel
29,Landau
30,Hecke
31,陈省身
32,Zermelo
33,Puntrijagin
34,H.Cartan
35,Hopf
36,小平邦彦
37,Cantor
38,Chx......