2022年随机数生成原理实现方法不同编程语言的随机数函数 .pdf

1-0： Microsoft VC+ 产生随机数的原理：Srand ( )和 Rand( )函数。它本质上是利用线性同余法，y=ax+b(mod m) 。其中 a， b，m 都是常数。因此rand 的产生决定于x， x 被称为 Seed。Seed需要程序中设定，一般情况下取系统时间作为种子。它产生的随机数之间的相关性很小，取值范围是032767（int） ，即双字节（ 16 位数），若用 unsigned int 双字节是 65535，四字节是4294967295，一般可以满足要求。1-1： 线性同余法 ：其中 M 是模数， A 是乘数， C 是增量，为初始值，当C=0 时，称此算法为乘同余法；若C0，则称算法为混合同余法，当 C 取不为零的适当数值时，有一些优点， 但优点并不突出，故常取 C=0。模 M 大小是发生器周期长短的主要标志，常见有M 为素数，取A 为 M 的原根，则周期T=M-1 。例如：a=1220703125 a=32719 （程序中用此组数）a=16807 代码：void main( ) const int n=100; double a=32719,m=1,fn+1,gn,seed; m=pow(2,31); cout 设置 m 值为m-1endl; cout 输入种子 seed; f0=seed; for(int i=1;i=n;i+) /线性同余法生成随机数 fi=fmod(a*fi-1),(m-1); gi-1=fi/(m-1); cout.setf(ios:fixed);cout.precision(6); /设置输出精度couti tgi-1endl; 结果分析：统计数据的平均值为：0.485653 统计数据的方差为：0.320576 1-2：人字映射递推公式就是有名的混沌映射中的“人字映射”或称“帐篷映射”，它的非周期轨道点的分布密度函数：人字映射与线性同余法结合，可产生统计性质优良的均匀随机数。for(int i=1;i=n;i+) /线性同余法生成随机数 fi=fmod(a*fi-1),m); if(fi=m/2) /与人字映射结合生成随机数 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 28 页 - - - - - - - - - fi=2*fi; else fi=2*(m-fi)+1; 1-3：平方取中法冯?诺伊曼1946 年前后，由冯?诺伊曼提出，他的办法是去前面的随机数的平方，并抽取中部的数字。例如要生成10 位数字，而且先前的值是5772156649，平方后得到33317792380594909201，所以下一个数是7923805949。for(j=1;j=n;j+) ij=ij-1*ij-1; ij=ij/pow(10,5); ij=fmod(ij,pow(10,10); gj=ij/pow(10,10); cout.setf(ios:fixed);cout.precision(6); /设置输出精度coutjtgjendl; 二：任意分布随机数的生成利用 (0，1)均匀分布的随机数可以产生任意分布的随机数。主要的方法有反函数法，舍选法， 离散逼近法， 极限近似法和随机变量函数法等。这里主要讨论了反函数法，当然对于具体分布函数可以采用不同的方法。设随机变量X 具有分布函数F(X) ，则对一个给定的分布函数值，X 的值为其中 inv 表示反函数。现假设r 是(0，1)均匀分布的随机变量R 的一个值，已知R 的分布函数为因此，如果r 是 R 的一个值，则X 具有概率也就是说如果(r1,r2,.,rn) 是 R 的一组值，则相应可得到的一组值具有分布。从而，如果我们已知分布函数的反函数，我们就可以从(0， 1)分布的均匀分布随机数得到所需分布的随机数了。1-4：指数分布：指数分布的分布函数为: x0 时 ,F(x)=0 ； ,F(x)=1-exp 利用上面所述反函数法，可以求得: x= ln(1-y) ，这里不妨取常数为 1. for(int j=0;jn;j+) i=rand()%100;/ 产生从 0-32767 的任意一个值aj=double(i)/double(100); aj=-log(aj);/ 常数大于0，这里取1 、 、 、 、 、 、 、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 28 页 - - - - - - - - - 1-5：正态分布：正态分布的概率密度是：正态分布的分布函数是：对于正态分布， 利用反函数的方法来获取正态分布序列显然是很麻烦的，牵涉到很复杂的积分微分运算，同时为了方便，我们取，即标准正态分布。因此这里介绍了两种算法：第一种：Box 和 Muller 在 1958 年给出了由均匀分布的随机变量生成正态分布的随机变量的算法。设U1, U2 是区间(0, 1)上均匀分布的随机变量，且相互独立。令X1=sqrt(-2*log(U1) * cos(2*PI*U2); X2=sqrt(-2*log(U1) * sin(2*PI*U2); 那么 X1, X2 服从 N(0,1) 分布，且相互独立。p=rand()%100;/ 产生从 0-32767 的任意一个值bj=double(p)/double(100); aj=sqrt(-2*log(aj)*cos(2*3.1415926*bj); 第二种：近似生成标准正态分布，独立同分布的多个随机变量和的分布趋近于正态分布,取 k 个均匀分布的 (0,1) 随机变量，,，则它们的和近似服从正态分布。实践中 ,取 k=12,(因为 D( )=1/12), 则新的随机变量y=x1+x2+.+x12-6 ，可以求出数学期望E(y)=0, 方差 D(y)=12*1/12=1 ，因此可以近似描述标准正态分布这几天再看数据结构和算法，中间遇到了生成不重复的随机数的问题我先想到的一个算法是这样的：Generator(vector& vec, const int num) srand(time(NULL); vector v; int size = num; for(int i = 1; i = num; +i) v.push_back(i); for(int i = 0; i num; +i) vector:iterator it = v.begin(); int n = rand() % (size-); it += n; vec.push_back(*it); v.erase(it); 但是由于vector 删除效率很低， 所以这个算法在10W 的时候已经不可接受了，需要 17 秒左右，后来在网上看到有朋友提出了另一种算法，感觉不错，于是又测试了一下名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 28 页 - - - - - - - - - void Gen(vector& vec, const int num) srand(time(NULL); for(int i = 0; i num; +i) vec.push_back(i+1); for(int i = 0; i num; +i) swap(vec.at(i), vec.at(rand() % num); 这个算法是线性的，在10W 的时候还可以，需要1.7 秒左右，可是100W 的时候就要17 秒左右了。想问一下，有没有更高效的生成算法？_ 回复：问一个关于随机数生成算法的问题lz 应该把要求说的具体点一定要 vector? _ 回复：问一个关于随机数生成算法的问题同意楼上的。要生成不重复的随机数，楼主可以自己写一个随机数生成程序啊，为什么一定要用rand()函数？楼主如果真的对随机数感兴趣，建议楼主看一看Knuth 的计算机程序设计艺术第二卷。可以用线性同余法:A(n+1)=(a*A(n)+c)%M 生成取遍 1 至 M-1 的所有整数， 前提是参数a,c,M选取合适。_ 回复：问一个关于随机数生成算法的问题STL 主要目标是提供一个通用高速的算法，如果对一个专用的功能而且追求很高的效率，最好使用最原始数据类型和直接手写的算法。下面给出我刚刚写好的一个程序，在VC6 下编译通过，当n=100 万时，仅需0.78 秒。/ csdn_5398401.cpp : Defines the entry point for the console application. #include stdafx.h #include memory.h #include stdlib.h #include windows.h typedef unsigned char BYTE; typedef unsigned long DWORD; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 28 页 - - - - - - - - - void test(int n) int i,c; DWORD idx; DWORD *pBuff; BYTE *pMask; BYTE maskArr=1,2,4,8,16,32,64,128; /- c=(n+7)/8; pMask=new BYTEc; pBuff=new DWORDn; memset(pMask,0,sizeof(BYTE)*c); memset(pBuff,0,sizeof(DWORD)*n); for (i=1;in;) idx=(rand() x=0, if ( ( pMaskidx / 8 & maskArridx % 8) =0) / pBuffx 没有存储过任何数 pMaskidx / 8 |= maskArridx % 8;/ 置 1 pBuffidx=i; i+; /- delete pMask; delete pBuff; int main(int argc, char* argv) DWORD t=GetTickCount(); test(1000000); t=GetTickCount()-t; printf(It take %d msn,t); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 28 页 - - - - - - - - - Java 中随机数生成的几种方法java 产生随机数的几种方式在 j2se 里我们可以使用Math.random() 方法来产生一个随机数，这个产生的随机数是0-1之间的一个double，我们可以把他乘以一定的数，比如说乘以100，他就是个100 以内的随机，这个在j2me 中没有。在 java.util 这个包里面提供了一个Random 的类，我们可以新建一个Random 的对象来产生随机数，他可以产生随机整数、随机float、随机double，随机long，这个也是我们在 j2me 的程序里经常用的一个取随机数的方法。在我们的System 类中有一个currentTimeMillis() 方法，这个方法返回一个从1970 年 1月 1 号 0 点 0 分 0 秒到目前的一个毫秒数，返回类型是long，我们可以拿他作为一个随机数，我们可以拿他对一些数取模，就可以把他限制在一个范围之内啦其实在 Random 的默认构造方法里也是使用上面第三种方法进行随机数的产生的对于方法二中的Random 类有以下说明：java.util.Random 类有两种方式构建方式：带种子和不带种子不带种子：此种方式将会返回随机的数字，每次运行结果不一样public class RandomTest public static void main(String args) java.util.Random r=new java.util.Random(); for(int i=0;i10;i+) System.out.println(r.nextInt(); 带种子：此种方式，无论程序运行多少次，返回结果都是一样的public static void main(String args) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 28 页 - - - - - - - - - java.util.Random r=new java.util.Random(10); for(int i=0;i10;i+) System.out.println(r.nextInt(); 两种方式的差别在于(1) 首先请打开Java Doc，我们会看到Random 类的说明：此类的实例用于生成伪随机数流，此类使用48 位的种子， 该种子可以使用线性同余公式对其进行修改（请参阅Donald Knuth 的 The Art of Computer Programming, Volume 2 ，第3.2.1 节） 。如果用相同的种子创建两个Random 实例，则对每个实例进行相同的方法调用序列，它们将生成并返回相同的数字序列。为了保证实现这种特性，我们为类Random 指定了特定的算法。为了Java 代码的完全可移植性，Java 实现必须让类Random 使用此处所示的所有算法。但是允许Random 类的子类使用其他算法，只要其符合所有方法的常规协定即可。Java Doc 对 Random 类已经解释得非常明白，我们的测试也验证了这一点。(2) 如果没有提供种子数， Random 实例 的种子 数将是当前时间 的毫秒 数，可 以通过System.currentTimeMillis() 来获得当前时间的毫秒数。打开JDK 的源代码，我们可以非常明确地看到这一点。/* * Creates a new random number generator. Its seed is initialized to * a value based on the current time: * Random() this(System.currentTimeMillis(); java.lang.System#currentTimeMillis() */ public Random() this(System.currentTimeMillis(); 另外：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 28 页 - - - - - - - - - random 对象的 nextInt(),nextInt(int n) 方法的说明：int nextInt() 返回下一个伪随机数，它是此随机数生成器的序列中均匀分布的int 值。int nextInt(int n) 返回一个伪随机数，它是从此随机数生成器的序列中取出的、在 0 （包括） 和指定值（不包括）之间均匀分布的int 值。C+中随机数生成方法标准库 （被包含于 中）提供两个帮助生成伪随机数的函数：函数一： int rand(void)；从 srand (seed) 中指定的 seed 开始，返回一个 seed, RAND_MAX （0 x7fff ） )间的随机整数。函数二： void srand(unsigned seed)；参数 seed 是 rand() 的种子，用来初始化rand() 的起始值。可以认为rand() 在每次被调用的时候，它会查看：1） 如果用户在此之前调用过srand(seed)，给 seed 指定了一个值，那么它会自动调用srand(seed)一次来初始化它的起始值。2） 如果用户在此之前没有调用过srand(seed)，它会自动调用srand(1)一次。根据上面的第一点我们可以得出：1） 如果希望rand（）在每次程序运行时产生的值都不一样，必须给 srand(seed) 中的 seed一个变值，这个变值必须在每次程序运行时都不一样（比如到目前为止流逝的时间）。2） 否则，如果给seed 指定的是一个定值，那么每次程序运行时rand（）产生的值都会一样，虽然这个值会是seed, RAND_MAX（0 x7fff ） )之间的一个随机取得的值。3） 如果在调用rand() 之前没有调用过srand(seed) ， 效果将和调用了srand(1) 再调用 rand()一样（ 1 也是一个定值）。举几个例子，假设我们要取得06 之间的随机整数（不含6 本身）：例一，不指定seed ：for(int i=0;i10;i+) ran_num=rand() % 6; coutran_num ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 28 页 - - - - - - - - - 每次运行都将输出：5 5 4 4 5 4 0 0 4 2 例二，指定seed 为定值 1：srand(1); for(int i=0;i10;i+) ran_num=rand() % 6; coutran_num ; 每次运行都将输出：5 5 4 4 5 4 0 0 4 2 跟例子一的结果完全一样。例三，指定seed 为定值 6：srand(6); for(int i=0;i10;i+) ran_num=rand() % 6; coutran_num ; 每次运行都将输出：4 1 5 1 4 3 4 4 2 2 随机值也是在 0,6 ）之间，随得的值跟srand(1) 不同，但是每次运行的结果都相同。例四，指定seed 为当前系统流逝了的时间（单位为秒）：time_t time(0)：#include /,srand(unsigned)time(0); for(int i=0;i10;i+) ran_num=rand() % 6; coutran_num ; 第一次运行时输出：0 1 5 4 5 0 2 3 4 2 第二次： 3 2 3 0 3 5 5 2 2 3 总之，每次运行结果将不一样，因为每次启动程序的时刻都不同（间隔须大于1 秒？见下） 。关于 time_t time(0)：time_t 被定义为长整型， 它返回从1970 年 1 月 1 日零时零分零秒到目前为止所经过的时间，单位为秒。比如假设输出：couttime(0); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 28 页 - - - - - - - - - 值约为 1169174701 ，约等于37（年）乘 365（天）乘24（小时）乘3600 （秒） （月日没算）。另外，关于ran_num = rand() % 6，将 rand() 的返回值与6 求模是必须的， 这样才能确保目的随机数落在0,6)之间， 否则 rand()的返回值本身可能是很巨大的。一个通用的公式是：要取得 a,b) 之间的随机整数，使用（rand() % (b-a) ）+ a （结果值将含a 不含 b）。在 a 为 0 的情况下，简写为rand() % b 。最后，关于伪随机浮点数：用 rand() / double(RAND_MAX)可以取得01 之间的浮点数（注意，不同于整型时候的公式，是除以，不是求模），举例：double ran_numf=0.0; srand(unsigned)time(0); for(int i=0;i10;i+) ran_numf = rand() / (double)(RAND_MAX);coutran_numf ; 运行结果为： 0.716636 ，0.457725 ，等 10 个 01 之间的浮点数，每次结果都不同。如果想取更大范围的随机浮点数，比如110，可以将rand() /(double)(RAND_MAX) 改为rand() /(double)(RAND_MAX/10) 运行结果为： 7.19362 ，6.45775 ，等 10 个 110 之间的浮点数，每次结果都不同。至于 100 ，1000 的情况，如此类推。C+ 中 常 用rand() 函 数 生 成 随 机 数 ， 但 严 格 意 义 上 来 讲 生 成 的 只 是 伪 随 机 数（pseudo-random integral number） 。生成随机数时需要我们指定一个种子，如果在程序内循环，那么下一次生成随机数时调用上一次的结果作为种子。但如果分两次执行程序，那么由于种子相同，生成的“ 随机数 ” 也是相同的。在工程应用时， 我们一般将系统当前时间(Unix 时间 )作为种子， 这样生成的随机数更接近于实际意义上的随机数。给一下例程如下：#include #include #include using namespace std; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 28 页 - - - - - - - - - int main() double random(double,double); srand(unsigned(time(0); for(int icnt = 0; icnt != 10; +icnt) cout No. icnt+1 : int(random(0,10) endl; return 0; double random(double start, double end) return start+(end-start)*rand()/(RAND_MAX + 1.0); /* 运行结果* No.1: 3 * No.2: 9 * No.3: 0 * No.4: 9 * No.5: 5 * No.6: 6 * No.7: 9 * No.8: 2 * No.9: 9 * No.10: 6 */ 利用这种方法能不能得到完全意义上的随机数呢？似乎9 有点多哦？却没有1,4,7？！我们来做一个概率实验，生成 1000 万个随机数， 看 0-9 这 10 个数出现的频率是不是大致相同的。程序如下：#include #include #include #include using namespace std; int main() double random(double,double); int a10 = 0; const int Gen_max = 10000000; srand(unsigned(time(0); for(int icnt = 0; icnt != Gen_max; +icnt) switch(int(random(0,10) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 28 页 - - - - - - - - - case 0: a0+; break; case 1: a1+; break; case 2: a2+; break; case 3: a3+; break; case 4: a4+; break; case 5: a5+; break; case 6: a6+; break; case 7: a7+; break; case 8: a8+; break; case 9: a9+; break; default: cerr Error! endl; exit(-1); for(int icnt = 0; icnt != 10; +icnt) cout icnt : setw(6) setiosflags(ios:fixed) setprecision(2) double(aicnt)/Gen_max*100 % endl; return 0; double random(double start, double end) return start+(end-start)*rand()/(RAND_MAX + 1.0); /* 运行结果* 0: 10.01% * 1: 9.99% * 2: 9.99% * 3: 9.99% * 4: 9.98% * 5: 10.01% * 6: 10.02% * 7: 10.01% * 8: 10.01% * 9: 9.99% */ 可知用这种方法得到的随机数是满足统计规律的。用 C 语言产生随机数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 28 页 - - - - - - - - - 在 C 语言中 ,rand()函数可以用来产生随机数，但是这不是真真意义上的随机数，是一个伪随机数， 是根据一个数， 我们可以称它为种子，为基准以某个递推公式推算出来的一系数，当这系列数很大的时候，就符合正态公布，从而相当于产生了随机数，但这不是真正的随机数，当计算机正常开机后，这个种子的值是定了的，除非你破坏了系统，为了改变这个种子的值， C 提供了 srand()函数，它的原形是void srand( int a) 。可能大家都知道C 语言中的随机函数random，可是 random 函数并不是ANSI C 标准，所以说， random 函数不能在gcc,vc 等编译器下编译通过。rand()会返回一随机数值，范围在 0 至 RAND_MAX 间。返回 0 至 RAND_MAX之间的随机数值， RAND_MAX定义在 stdlib.h， (其值至少为32767)我运算的结果是一个不定的数，要看你定义的变量类型，int 整形的话就是32767。在调用此函数产生随机数前，必须先利用 srand()设好随机数种子，如果未设随机数种子，rand()在调用时会自动设随机数种子为1。一般用 for 语句来设置种子的个数。具体见下面的例子。一 如何产生不可预见的随机序列呢利用 srand(unsigned int)(time(NULL)是一种方法，因为每一次运行程序的时间是不同的。在 C 语言里所提供的随机数发生器的用法：现在的C 编译器都提供了一个基于ANSI标准的伪随机数发生器函数，用来生成随机数。它们就是rand()和 srand()函数。这二个函数的工作过程如下：1) 首先给 srand()提供一个种子，它是一个unsigned int 类型，其取值范围从065535；2) 然后调用rand()，它会根据提供给srand()的种子值返回一个随机数(在 0 到 32767 之间 ) 3) 根据需要多次调用rand()，从而不间断地得到新的随机数；4) 无论什么时候，都可以给srand()提供一个新的种子，从而进一步“ 随机化 ”rand() 的输出结果。下面是 032767 之间的随机数程序：#include #include #include /使用当前时钟做种子void main( void ) int i; srand( (unsigned)time( NULL ) ); /初始化随机数for( i = 0; i 10;i+ ) /打印出 10 个随机数printf( %dn, rand() ); 根据上面的程序可以很容易得到01 之间的随机数：#include #include #include main( ) int i; srand( (unsigned)time( NULL ) ); for( i = 0; i 10;i+ ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 28 页 - - - - - - - - - printf( %5.2fn, rand()/32767.0); 而产生 1100 之间的随机数可以这样写：#include #include #include main( ) int i; srand( (unsigned)time( NULL ) ); for( i = 0; i 10;i+ ) printf( %dn, rand()%100+1); come from http:/ : rand 功能: 随机数发生器用法: void rand(void); 程序例 : #include #include int main(void) int i; printf(Ten random numbers from 0 to 99nn); for(i=0; i10; i+) printf(%dn, rand() % 100); return 0; 函数名 : random 功能: 随机数发生器用法: int random(int num); 程序例 : #include #include #include /* prints a random number in the range 0 to 99 */ int main(void) randomize(); printf(Random number in the 0-99 range: %dn, random (100); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 28 页 - - - - - - - - - 函数名 : randomize 这个比较好！功能: 初始化随机数发生器用法: void randomize(void); 程序例 : #include #include #include int main(void) int i; randomize(); printf(Ten random numbers from 0 to 99nn); for(i=0; i10; i+) printf(%dn, rand() % 100); return 0; 在计算机常用算法中有介绍随机数的生成算法三 如何产生设定范围内的随机数由于 rand 产生的随机数从0 到 rand_max，而 rand_max 是一个很大的数，那么如何产生从XY 的数呢？从 X 到 Y，有 YX1 个数，所以要产生从X 到 Y 的数，只需要这样写：k=rand()%(Y-X+1)+X; 这样，就可以产生你想要的任何范围内的随机数了。四，产生不重复的随机数1） #include #include #include #include swap(int *pm,int *pn) /*必须用指针进行交换*/ int temp; temp=*pm; *pm=*pn; *pn=temp; int main(void) int i,a513; /*int *pa,*pb;*/ srand( (unsigned)time( NULL ) ); /*定义这个可以产生不同的随机数*/ for(i=1; i=1; i-) /* pa=&ai; pb=&arand()%i+1;*/ swap(&ai, &arand()%i+1); /* 加一是从一到i 的随机，就不会包含0*/ /*不用再定义指针，这样结论是一样的*/ printf(n) ; for(i=1; i=64; i+) printf(%4d,ai ); getch(); /*wintc 的输出 */ 2） #include #include #include int main(void) int a100=0; int i,m; for(i=1; i=99; +i) printf(%4d,ai ); srand( (unsigned)time( NULL ) ); for(i=1; i=99; i+) while(am=rand()%100+1); am = i; for(i=1; i=99; +i) printf(%4d,ai ); getch(); / Snake.cpp : 定义控制台应用程序的入口点。/This program is used to collect the most mark and output the routine. /by nwpu043814 /date:20100509 #include stdafx.h #include #include #include using namespace std; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 28 页 - - - - - - - - - /this struct represents an location. typedef struct int x; int y; Pair; class Grid private : Grid(const Grid& g); public: Pair * m_data; const int m_width; /grid width const int m_height; /grid height int * m_adjacent; /memory array /constructor with width and height of the grid. Grid(int x, int y):m_width(x), m_height(y) m_data = new Pairx*y; memset(m_data, 0, x*y *sizeof(Pair); m_adjacent = new intx*y; memset(m_adjacent, -1, x*y *sizeof(int); /free resource Grid() delete m_data; delete m_adjacent; int Bin2One(int x, int y) return y*m_width + x; Pair One2Bin(int index) Pair p; p.x = index % m_width; p.y = index / m_width; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 28 页 - - - - - - - - - return p; /this method is used to get or set the item of the grid. int & item(int x, int y) return m_datax+ y*m_width.x; /dynamic program main method, it recursively select the next location from the adjacents according to the priority. int getCap(const Pair &