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

1-0：Microsoft VC++产生随机数的原理：

Srand ( )和Rand( )函数。它本质上是利用线性同余法，y=ax+b(mod m)。其中a，b，m都是常数。因此rand的产生决定于x，x被称为Seed。Seed需要程序中设定，一般情况下取系统时间作为种子。它产生的随机数之间的相关性很小，取值范围是0—32767（int），即双字节（16位数），若用unsigned int 双字节是65535，四字节是4294967295，一般可以满足要求。

1-1： 线性同余法：

其中M是模数，A是乘数，C是增量，为初始值，当C=0时，称此算法为乘同余法；若C≠0，则称算法为混合同余法，当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,f[n+1],g[n],seed; m=pow(2,31);

cout<<\设置m值为 \cout<<\输入种子\ //输入种子

cin>>seed; f[0]=seed;

for(int i=1;i<=n;i++) //线性同余法生成随机数 {

f[i]=fmod((a*f[i-1]),(m-1));

g[i-1]=f[i]/(m-1);

cout.setf(ios::fixed);cout.precision(6); //设置输出精度 cout<

结果分析：统计数据的平均值为：0.485653 统计数据的方差为：0.320576

1-2：人字映射 递推公式

就是有名的混沌映射中的“人字映射”或称“帐篷映射”，它的非周期轨道点的分布密度函数：人字映射与线性同余法结合，可产生统计性质优良的均匀随机数。 for(int i=1;i<=n;i++) //线性同余法生成随机数 {

f[i]=fmod((a*f[i-1]),m);

if(f[i]<=m/2) //与人字映射结合生成随机数 {

f[i]=2*f[i]; } else {

f[i]=2*(m-f[i])+1; }

1-3：平方取中法——冯?诺伊曼

1946年前后，由冯?诺伊曼提出，他的办法是去前面的随机数的平方，并抽取中部的数字。例如要生成10位数字，而且先前的值是5772156649，平方后得到33317792380594909201，所以下一个数是7923805949。 for(j=1;j<=n;j++) {

i[j]=i[j-1]*i[j-1]; i[j]=i[j]/pow(10,5);

i[j]=fmod(i[j],pow(10,10)); g[j]=i[j]/pow(10,10);

cout.setf(ios::fixed);cout.precision(6); //设置输出精度

cout<

二：任意分布随机数的生成

利用(0，1)均匀分布的随机数可以产生任意分布的随机数。主要的方法有反函数法，舍选法，离散逼近法，极限近似法和随机变量函数法等。这里主要讨论了反函数法，当然对于具体分布函数可以采用不同的方法。

设随机变量X具有分布函数F(X)，则对一个给定的分布函数值，X的值为

其中inv表示反函数。现假设r是(0，1)均匀分布的随机变量R的一个值，已知R的分布函数为

因此，如果r是R的一个值，则X具有概率

也就是说如果 (r1,r2,...,rn)是R的一组值，则相应可得到的一组值

具有分布。从而，如果我们已知分布函数的反函数，我们就可以从(0，1)分布的均匀分布随机数得到所需分布的随机数了。 1-4：指数分布：

指数分布的分布函数为: x<0时,F(x)=0 ； ,F(x)=1-exp

利用上面所述反函数法，可以求得: x= ln(1-y)，这里不妨取常数 为1. for(int j=0;j

{

i=rand()0;//产生从0-32767的任意一个值 a[j]=double(i)/double(100);

a[j]=-log(a[j]);// 常数大于0，这里取1 、、、、、、、

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()0;//产生从0-32767的任意一个值

b[j]=double(p)/double(100);

a[j]=sqrt(-2*log(a[j]))*cos(2*3.1415926*b[j]); 第二种：

近似生成标准正态分布，独立同分布的多个随机变量和的分布趋近于正态分布,取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秒左右，后来在网上看到有朋友提出了另一种算法，感觉不错，于是又测试了一下

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 \#include \#include \#include \

typedef unsigned char BYTE; typedef unsigned long DWORD;

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 BYTE[c]; pBuff=new DWORD[n];

memset(pMask,0,sizeof(BYTE)*c); memset(pBuff,0,sizeof(DWORD)*n);

for (i=1;i

idx=(rand() << 15)+rand();

idx %= n; //随机得到一个0 to n之间地址，n>x>=0,

if ( ( pMask[idx / 8] & maskArr[idx % 8]) ==0) // pBuff[x] 没有存储过任何数 {

pMask[idx / 8] |= maskArr[idx % 8];// 置1 pBuff[idx]=i; i++; }

}

//---------

delete[] pMask; delete[] pBuff; }

int main(int argc, char* argv[]) {

DWORD t=GetTickCount(); test(1000000);

t=GetTickCount()-t;

printf(\ return 0; }

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;i<10;i++){

System.out.println(r.nextInt()); }

}

带种子：

此种方式，无论程序运行多少次，返回结果都是一样的

public static void main(String[] args) {

java.util.Random r=new java.util.Random(10);

for(int i=0;i<10;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()); }

另外：

random对象的nextInt(),nextInt(int n)方法的说明：

int nextInt()

返回下一个伪随机数，它是此随机数生成器的序列中均匀分布的 int 值。

int nextInt(int n)

返回一个伪随机数，它是从此随机数生成器的序列中取出的、在 0（包括）和指定值（不包括）之间均匀分布的 int值。

C++中随机数生成方法

标准库（被包含于中）提供两个帮助生成伪随机数的函数： 函数一：int rand(void)；

从srand (seed)中指定的seed开始，返回一个[seed, RAND_MAX（0x7fff）)间的随机整数。 函数二：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（0x7fff）)之间的一个随机取得的值。

3） 如果在调用rand()之前没有调用过srand(seed)，效果将和调用了srand(1)再调用rand()一样（1也是一个定值）。

举几个例子，假设我们要取得0～6之间的随机整数（不含6本身）： 例一，不指定seed： for(int i=0;i<10;i++){ ran_num=rand() % 6; cout<

}

每次运行都将输出：5 5 4 4 5 4 0 0 4 2 例二，指定seed为定值1： srand(1);

for(int i=0;i<10;i++){ ran_num=rand() % 6; cout<

每次运行都将输出：5 5 4 4 5 4 0 0 4 2 跟例子一的结果完全一样。 例三，指定seed为定值6： srand(6);

for(int i=0;i<10;i++){ ran_num=rand() % 6; cout<

每次运行都将输出：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;i<10;i++){ ran_num=rand() % 6; cout<

第一次运行时输出：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日零时零分零秒到目前为止所经过的时间，单位为秒。比如假设输出： cout<

值约为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)可以取得0～1之间的浮点数（注意，不同于整型时候的公式，是除以，不是求模），举例： double ran_numf=0.0; srand((unsigned)time(0)); for(int i=0;i<10;i++){

ran_numf = rand() / (double)(RAND_MAX); cout<

运行结果为：0.716636，0.457725，…等10个0～1之间的浮点数，每次结果都不同。 如果想取更大范围的随机浮点数，比如1～10，可以将

rand() /(double)(RAND_MAX) 改为 rand() /(double)(RAND_MAX/10)

运行结果为：7.19362，6.45775，…等10个1～10之间的浮点数，每次结果都不同。 至于100，1000的情况，如此类推。 ?

C++中常用rand()函数生成随机数，但严格意义上来讲生成的只是伪随机数（pseudo-random integral number）。生成随机数时需要我们指定一个种子，如果在程序内循环，那么下一次生成随机数时调用上一次的结果作为种子。但如果分两次执行程序，那么由于种子相同，生成的“随机数”也是相同的。

在工程应用时，我们一般将系统当前时间(Unix时间)作为种子，这样生成的随机数更接近于实际意义上的随机数。给一下例程如下：

#include #include #include using namespace std;

int main()

{

double random(double,double); srand(unsigned(time(0)));

for(int icnt = 0; icnt != 10; ++icnt)

cout << \ 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 a[10] = {0};

const int Gen_max = 10000000; srand(unsigned(time(0)));

for(int icnt = 0; icnt != Gen_max; ++icnt) switch(int(random(0,10))) {

case 0: a[0]++; break; case 1: a[1]++; break; case 2: a[2]++; break; case 3: a[3]++; break; case 4: a[4]++; break; case 5: a[5]++; break; case 6: a[6]++; break; case 7: a[7]++; break; case 8: a[8]++; break; case 9: a[9]++; break;

default: cerr << \ }

for(int icnt = 0; icnt != 10; ++icnt)

cout << icnt << \\<< setw(6) << setiosflags(ios::fixed) << setprecision(2) << double(a[icnt])/Gen_max*100 << \

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语言产生随机数

在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类型，其取值范围从0~65535； 2) 然后调用rand()，它会根据提供给srand()的种子值返回一个随机数(在0到32767之间) 3) 根据需要多次调用rand()，从而不间断地得到新的随机数；

4) 无论什么时候，都可以给srand()提供一个新的种子，从而进一步“随机化”rand()的输出结果。

下面是0~32767之间的随机数程序： #include

#include

#include //使用当前时钟做种子 void main( void )

{int i;

srand( (unsigned)time( NULL ) ); //初始化随机数 for( i = 0; i < 10;i++ ) //打印出10个随机数 printf( \

}

根据上面的程序可以很容易得到0~1之间的随机数： #include #include #include main( ) {int i;

srand( (unsigned)time( NULL ) ); for( i = 0; i < 10;i++ )

printf( \}

而产生1~100之间的随机数可以这样写： #include #include #include main( )

{int i;

srand( (unsigned)time( NULL ) ); for( i = 0; i < 10;i++ )

printf( \}

come from http://hi.http://www.wodefanwen.com//akaneyu

二，三个通用的随机数发生器，推荐用第三个 函数名: rand

功 能: 随机数发生器 用 法: void rand(void); 程序例:

#include #include

int main(void) {

int i;

printf(\ for(i=0; i<10; i++)

printf(\ 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(\ return 0; }

函数名: randomize 这个比较好！ 功 能: 初始化随机数发生器 用 法: void randomize(void); 程序例:

#include #include #include int main(void) {

int i;

randomize();

printf(\ for(i=0; i<10; i++)

printf(\

return 0; }

在《计算机常用算法》中有介绍随机数的生成算法 三 如何产生设定范围内的随机数

由于rand产生的随机数从0到rand_max，而rand_max是一个很大的数，那么如何产生从X~Y的数呢？

从X到Y，有Y－X＋1个数，所以要产生从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,a[513];

/*int *pa,*pb;*/

srand( (unsigned)time( NULL ) ); /*定义这个可以产生不同的随机数*/ for(i=1; i<=512; i++){a[i]=i;printf(\

for(i=512; i>=1; i--)

{

/* pa=&a[i]; pb=&a[rand()%i+1];*/

swap(&a[i], &a[rand()%i+1]); /*加一是从一到i的随机，就不会包含0*/ /*不用再定义指针，这样结论是一样的*/ }

printf(\;

for(i=1; i<=64; i++) printf(\

getch(); /*wintc的输出*/ } 2）

#include #include #include

int main(void) {

int a[100]={0}; int i,m; for(i=1; i<=99; ++i) printf(\

srand( (unsigned)time( NULL ) ); for(i=1; i<=99; i++) {

while(a[m=rand()0+1]); a[m] = i; }

for(i=1; i<=99; ++i) printf(\getch(); }

// Snake.cpp : 定义控制台应用程序的入口点。

//This program is used to collect the most mark and output the routine. //by nwpu043814 //date:20100509 #include \#include #include #include using namespace std;

//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 Pair[x*y];

memset(m_data, 0, x*y *sizeof(Pair)); m_adjacent = new int[x*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;

return p; }

//this method is used to get or set the item of the grid. int & item(int x, int y) {

return m_data[x+ 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 & loc) {

//this array is used to storage the priority of four adjacents. int value[4] = {0};

//this array is used to access four adjacents according to current location.

int mask[4][2] = {

{-1,0},{0,1},{1,0},{0,-1}/*{x_coordinate, y_coordinate}*/ };

//now, we start to deal with four adjacents. for (int i = 0; i < 4; i++) {

//make sure current location has four adjacents

if (loc.x + mask[i][0] >= 0 && loc.x + mask[i][0] < m_width && loc.y + mask[i][1] >= 0 && loc.y + mask[i][1] < m_height) {

//if the toy in the adjacent can hold current one. int current_toy = (m_data[Bin2One(loc.x, loc.y)].x >

0)?m_data[Bin2One(loc.x, loc.y)].x:m_data[Bin2One(loc.x, loc.y)].y; if ( item(loc.x + mask[i][0], loc.y + mask[i][1]) > current_toy//item(loc.x , loc.y)

|| item(loc.x + mask[i][0], loc.y + mask[i][1]) == 0)//when the adjacent has no toy. {

Pair adjacent;

adjacent.x = loc.x + mask[i][0]; adjacent.y = loc.y + mask[i][1];

m_data[Bin2One(adjacent.x, adjacent.y)].y = current_toy; value[i] = getCap(adjacent); }

} }

int sum = 0;

for (int i = 0; i < 4; i++) {

sum += value[i]; }

//when all adjacents is less than current. if (sum == 0) {

return item(loc.x , loc.y); } else {

int index = 0;

int current_max = value[index]; int select = 0;

for (int index = 0; index < 4; index++) {

if (current_max < value[index]) {

current_max = value[index]; select = index; } }

m_adjacent[Bin2One(loc.x, loc.y)] = Bin2One(loc.x + mask[select][0], loc.y + mask[select][1]);

return current_max + item(loc.x , loc.y); } }

//this method drives the class void run() {

Pair loc; loc.x = 0; loc.y = 0;

for (int i = 0; i < m_width*m_height; i++) {

m_data[i].y = m_data[i].x; }

cout << \}

//display the grid void displayGrid() {

for (int i =0 ; i < this->m_height; i++) {

for (int j = 0; j < this->m_width; j++) {

cout << \ }

cout << endl; } }

//display the routine. void print() {

int current, next, out ; current = 0;

next = m_adjacent[current]; out = m_data[current].x;

while (next != -1) {

cout << \ current = next;

next = m_adjacent[current]; out = m_data[current].x; }

cout << \} };

int _tmain(int argc, _TCHAR* argv[]) {

ifstream in(\int x,y, k, value; in >> x >> y ;

Grid * grid = new Grid(y, x);

value = 0;

//this block initializes the grid items with ifstream. while (true) {

if (in.eof()) {

break; }

in >> k;

grid->item(value%grid->m_width, value/grid->m_width) = k; value++; }

grid->displayGrid(); grid->run();//done grid->print(); cin >>x;

delete grid; grid = NULL; in.close(); return 0; }

// Snake.cpp : 定义控制台应用程序的入口点。

//This program is used to collect the most mark and output the routine. //by nwpu043814 //date:20100509 #include \#include #include #include

using namespace std;

//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 Pair[x*y];

memset(m_data, 0, x*y *sizeof(Pair)); m_adjacent = new int[x*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; return p; }

//this method is used to get or set the item of the grid. int & item(int x, int y) {

return m_data[x+ 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 & loc) {

//this array is used to storage the priority of four adjacents. int value[4] = {0};

//this array is used to access four adjacents according to current location.

int mask[4][2] = {

{-1,0},{0,1},{1,0},{0,-1}/*{x_coordinate, y_coordinate}*/ };

//now, we start to deal with four adjacents. for (int i = 0; i < 4; i++) {

//make sure current location has four adjacents

if (loc.x + mask[i][0] >= 0 && loc.x + mask[i][0] < m_width && loc.y + mask[i][1] >= 0 && loc.y + mask[i][1] < m_height) {

//if the toy in the adjacent can hold current one. int current_toy = (m_data[Bin2One(loc.x, loc.y)].x >

0)?m_data[Bin2One(loc.x, loc.y)].x:m_data[Bin2One(loc.x, loc.y)].y; if ( item(loc.x + mask[i][0], loc.y + mask[i][1]) > current_toy//item(loc.x , loc.y)

|| item(loc.x + mask[i][0], loc.y + mask[i][1]) == 0)//when the adjacent has no toy. {

Pair adjacent;

adjacent.x = loc.x + mask[i][0]; adjacent.y = loc.y + mask[i][1];

m_data[Bin2One(adjacent.x, adjacent.y)].y = current_toy; value[i] = getCap(adjacent); } } }

int sum = 0;

for (int i = 0; i < 4; i++) {

sum += value[i]; }

//when all adjacents is less than current. if (sum == 0) {

return item(loc.x , loc.y); } else {

int index = 0;

int current_max = value[index]; int select = 0;

for (int index = 0; index < 4; index++) {

if (current_max < value[index]) {

current_max = value[index]; select = index; } }

m_adjacent[Bin2One(loc.x, loc.y)] = Bin2One(loc.x + mask[select][0], loc.y + mask[select][1]);

return current_max + item(loc.x , loc.y); } }

//this method drives the class void run() {

Pair loc;

loc.x = 0; loc.y = 0;

for (int i = 0; i < m_width*m_height; i++) {

m_data[i].y = m_data[i].x; }

cout << \}

//display the grid void displayGrid() {

for (int i =0 ; i < this->m_height; i++) {

for (int j = 0; j < this->m_width; j++) {

cout << \ }

cout << endl; } }

//display the routine. void print() {

int current, next, out ; current = 0;

next = m_adjacent[current]; out = m_data[current].x;

while (next != -1) {

cout << \ current = next;

next = m_adjacent[current]; out = m_data[current].x; }

cout << \} };

int _tmain(int argc, _TCHAR* argv[]) {

ifstream in(\int x,y, k, value; in >> x >> y ;

Grid * grid = new Grid(y, x);

value = 0;

//this block initializes the grid items with ifstream. while (true) {

if (in.eof()) {

break; }

in >> k;

grid->item(value%grid->m_width, value/grid->m_width) = k; value++; }

grid->displayGrid(); grid->run();//done grid->print(); cin >>x;

delete grid; grid = NULL; in.close(); return 0; }

应百度网友wu329613403的要求，花半小时写了个大体思路，最近太忙了，只能写个思路，估计有不完善的地方，欢迎指正。（注意题目中没有给将距离与时间沟通起来的教师行进速度，我认为应该给。）

A，假设家长数目为N，从文件读取家长的时间表，定义一个家长类，包括的成员为开始时间，结束时间，家长编号，存储到其余每个家长的距离的一个数组，从文件读入多少个家长就创建多少个家长对象，用一个容器C1来存放N个家长对象的指针，定义一个容器C2保存家长的拜访情况.

B，删除安排时间段小于45分钟的家长，根据每个家长的开始时间对容器C1中的家长进行排序，时间早的排在最前面。

C，选取开始时间最早的家长作为当前准备拜访的家长，拜访时间持续45分钟，将当前家长的拜访情况保存到容器C2，同时从容器C1中删除当前家长的信息。 D，用当前家长到其余每个（未拜访）的家长的时间加上各个家长的开始时间作为每个家长的新的开始时间，重新对容器C1按照新的开始时间进行排序，对容器中的家长C1[i]进行判断(i从0开始)：

if(当前家长的开始时间比现在的时间早（小，意思是已经错过了）) {

新拜访结束时刻1 = 当前时时刻+ 刚刚拜访的家长到当前家长C1[i]需要的时间长度 + 45分钟；

if (新拜访结束时刻1 比 家长C1[i]的结束时刻早(或者为同一个时刻)) {

拜访这个家长C1[i]，时间持续45分钟; 将拜访信息添加到C2;

从C1中删除当前家长C1[i];

if(C1不为空) {

goto D;(意思是：重复步骤D的内容) } else {

goto E;(去输出C2的内容) } } else {

从C1中删除当前家长C1[i]; }

} else {

拜访容器C1中的排第一的家长，时间持续45分钟;(出现这种情况，就是老师走到下个拜访的家长的时候，拜访时间还没有开始，需要等待一段时间，实际上这样的情况是浪费了时间了，谁叫这个家长的开始时间安排的晚呢，不能怪老师。)

将拜访信息添加到C2;

从C1中删除当前家长C1[i];

if(C1不为空) {

goto D;(意思是：重复步骤D的内容) } else {

goto E;(去输出C2的内容) } }

E，根据容器C2的拜访记录输出家访安排计划。

本文来源：https://www.bwwdw.com/article/90ag.html