在做ｃ语言课题设计的时候，我的选题是一个跳格子的游戏。在做一个自动演示（机器能够自动从(0,0)跳到(hor,ver)点）的模块儿时，我采用了一种算法，目的是能够找到从起点到终点的最近的路径。拿6*6最大可跳步数为4的一个格子为例。（编者按：作者研究的模型是离散数学中有名的“最短通路模型”——在附权图中找到从起点Q到终点M的最短通路。实际上在这个环节上，作者采用的方法并不是最高效的，作者本人也和编者探讨过。但本文的重点不是找“最短通路”而是在解决这个问题中引发的对产生随机数的思考)
程序的基本算法思路是，从坐标起点，也就是(0,0)点，每一个格子在每一次的方向命令指令下都会有四种移动的方式：向上，向下，向左，向右。对位置变量(j,i)进行加减,四种计算,来实现移动.交互式的手动模式下,方向命令指令当然是利用键盘响应值了,但是在自动演示模式下,我做了一个函数,用来随机产生一个方向指令.下面是模块的源代码:
#include<graphics.h>
#include<stdio.h>
#include<dos.h>
#include<time.h>
#include<stdlib.h>
#include<c:/windows/desktop/new/flag.c>*/
|
这是一个用于画图的函数，本身并没有多大的意义，但是，在其中，我加入了dalay（）并加入了随机参数，目的是为了取消随机返回的方向值的周期性和规律性，使得随机方向值分布的更加广泛
/******FUNCTION
FOR loading******/
void load(int
y,int times)
{
setcolor(YELLOW);
outtextxy(37,y,"Loading...");
setcolor(WHITE);
rectangle(37,y+17,604,y+17+9);
setcolor(BLACK);
line(38,y+17+9,604,y+17+9);
line(604,y+17+9,604,y+17);
if(times%5==0)
{
setfillstyle(SOLID_FILL,MAGENTA);
bar(38,y+17+1,38+times/5,y+17+8);
}
setcolor(BLUE);
outtextxy(37,y,"Loading...");
randomize();
sound(1000);
delay(50*random(3));
nosound();
}
|
随机产生一个方向参数，并且，能够验证所产生的方向值合理（意为通过这种计算方法可以走到下一个格子）。
/******随机产生一种合理的运算方法的函数******/
int suan(int
a,int x,int
y)
{
int c,u;
delay(20);
randomize();
for(u=0;u<=15;u++)
{
c=random(4)+1;
if(c==1&&(a+x)<6)
{
return(c);
}
if(c==2&&(x-a)>=0)
{
return(c);
}
if(c==3&&(a+y)<6)
{
return(c);
}
if(c==4&&(y-a)>=0)
{
return(c);
}
}
return(0);
}
|
将game函数和自动演示的算法合并，利用所计算到的最短路径从起点走道终点
extern
uto(int Wdth,int
Hight,int X,int
y)
{
int h[30][30],s[30][30];
int a[30][30];
int hl[29],sl[29];
int k=605/Wdth,g=231/Hight;
char ch[3];
int num,i,j;
int open_clo[30][30]={0};
int gg[30]={0},hh[30]={0};
int times;
int nu,mi,min=30;
int xx[30],yy[30];
int li=0;
/** draw the back color **/
setfillstyle(SOLID_FILL,LIGHTGRAY);
bar(30,44,635,275);
/** draw the line **/
for(i=0;i<=Hight-2;i++)
{
hl[i]=44+g*(i+1);
xian(hl[i],1);/*在其它函数中有定义*/
for(i=0;i<=Wdth-2;i++)
{
sl[i]=30+k*(i+1);
xian(sl[i],2);
}
setcolor(DARKGRAY);
line(29,43,29,275);
line(29,43,635,43);
setcolor(WHITE);
line(28,42,636,42);
line(28,42,28,276);
/** to put the rand num **/
randomize();
for(i=0;i<Wdth;i++)
for(j=0;j<Hight;j++)
{
a[i][j]=random(X)+1;
a[5][5]=1;
a[4][5]=1;
a[5][4]=1;
h[i][j]=30+i*k;
s[i][j]=44+j*g;
setcolor(a[i][j]%16+1);
if(a[i][j]%16+1==7)
setcolor(RED);
itoa(a[i][j],ch,10);
outtextxy(h[i][j]+2,s[i][j]+1,ch);
}
outtextxy(h[5][5],s[5][5],"END");
i=0,j=0;
open_clo[i][j]=1;
for(nu=0;nu<=2825;nu++)
{
num=0;
load(y,li++);
times=0;
for(i=0;i<6;i++)
for(j=0;j<6;j++)
open_clo[i][j]=0;
open_clo[0][0]=1;
i=0,j=0;
while(i!=5||j!=5)/*如果没有到终点，就循环*/
{
mi=suan(a[i][j],j,i);
gg[times]=i;/*代表其横坐标*/
hh[times]=j;/*代表其纵坐标*/
if(mi==1&&open_clo[i][(j+a[i][j])]==0)/*
1代表向下方向，2代表上方向，3代表右方向，4代表左方向*/
{
j=a[i][j]+j;
open_clo[i][j]=1;/*走过的点开关值变为1，为关，此格子已不能在跳到了。*/
}
if(mi==3&&open_clo[(i+a[i][j])][j]==0)
{
i=a[i][j]+i;
open_clo[i][j]=1;
}
if(mi==2&&open_clo[i][(j-a[i][j])]==0)
{
j=j-a[i][j];
open_clo[i][j]=1;
}
if(mi==4&&open_clo[(i-a[i][j])][j]==0)
{
i=i-a[i][j];
open_clo[i][j]=1;
}
num++;
times++;
}
if(min>num)
{
min=num;
for(times=0;times<min;times++)
{
xx[times]=hh[times];
yy[times]=gg[times];
}
}
}
|
开始自动演示，数组clo[i]，此数组是一个对应开关，0代表这个坐标的格子是开着的，意为此格子可走。经大量实验证明，当nu为3000左右，可算出6*6，最大跳跃步数为4的最短路径。如果，这次所跳的次数小于min就把这次的路径记录下来存于xx[times]和yy[times]数组。下面将找到的最短路径表现在格子中：
for(times=0;times<=min;times++)
{
flag(h[yy[times]][xx[times]]+2,s[yy[times]][xx[times]]+1,k,g);
if(yy[times]==5&&xx[times]==4&&a[yy[times]][xx[times]]==1)
{
flag(h[5][5]+2,s[5][5]+1,k,g);
break;
}
if(yy[times]==5&&xx[times]==3&&a[yy[times]][xx[times]]==2)
{
flag(h[5][5]+2,s[5][5]+1,k,g);
break;
}
if(yy[times]==5&&xx[times]==2&&a[yy[times]][xx[times]]==3)
{
flag(h[5][5]+2,s[5][5]+1,k,g);
break;
}
if(yy[times]==5&&xx[times]==1&&a[yy[times]][xx[times]]==4)
{
flag(h[5][5]+2,s[5][5]+1,k,g);
break;
}
if(yy[times]==1&&xx[times]==5&&a[yy[times]][xx[times]]==4)
{
flag(h[5][5]+2,s[5][5]+1,k,g);
break;
}
if(yy[times]==2&&xx[times]==5&&a[yy[times]][xx[times]]==3)
{
flag(h[5][5]+2,s[5][5]+1,k,g);
break;
}
if(yy[times]==3&&xx[times]==5&&a[yy[times]][xx[times]]==2)
{
flag(h[5][5]+2,s[5][5]+1,k,g);
break;
}
if(yy[times]==4&&xx[times]==5&&a[yy[times]][xx[times]]==1)
{
flag(h[5][5]+2,s[5][5]+1,k,g);
break;
}
getch();
}
|
虽然这个算法并不是很好，但是其中却让我想到了许多有关随机数的一些东西，也在一步步摸索随机数的原理和产生机制。
大家会感到奇怪,我为什么会人为的加入时间拖延函数delay,并且在laoding函数中的delay的参数中又加入随机数了呢？起初，我并没有这样加入如此多的delay函数，因为这样是很影响程序的运行速度，但是，意想不到的事情却发生了，程序败了，标记flag函数满天都是，令人无奈。后来，我分析原因，却总也找不出逻辑上的错误，于是，我开始怀疑到在随机返回计算方法的函数。
随机数一般是伪随机数，每个随机数都是由随机种子(rand_seed).rand_seed在系统中通常是参照系统时钟生成的。以当日0点为起点，取得种子的时刻（randomize();）为终点取得种子.然后按照Rand_Number
= (Rand_Seed * X + Y) % Z获得伪随机数，所以，当计算机高速计算中，随机通过函数取得计算方法之间的时间差几乎是0，且分布是呈周期性的。这样，无法做到真正的‘随机’。
可按照统计学原理，每一次，返回的计算方法越随机，可真正得到的路径范围越广，越能找出真正最短路径来.于是，与无奈中我只好选择用了delay函数，来拖延时间，并在delay（）参数中加入了随机因子，来消除随机数周期分布现象，实在是一个丢卒保车的无奈之举。
有文讲 ，根据Randomize的工作原理，利用函数Timer得到从午夜开始到现在经过的秒数，然后再根据要得到的随机数值大小对该数值进行"“衰减”处理，这样得到的数值则可称得上是真正意义的随机数值，我认为，这也是人为的方法，仍有它的确定性和周期性，仍称不上是真正的随机数，单纯改变伪随机数的生成逻辑计算方法并不能达到目的，最有效的办法只能是改变rand_seed，就是种子。而且，改变后的rand_seed不应该是人为的。
（注：目前，在 Intel 的PIII处理器中内置了一个与CPU温度相关的随机数生成器，算是一个比较有效的种子生成器。）
如果，随机数的随机性得不到保障，后果是十分严重的。特别是安全方面， 计算机一直是具有完全确定性的机器，所以，特别在随机的行为方面表现不尽人意，在服务器随机生成通讯密钥并传送给通讯的双方，但如果，攻击者了解这台服务器随机数产生的种子，并通过长期观察总结出公式，那么，这种通讯对于攻击者而言就毫无秘密可言了。
Reliable Software Technologies (RST) 的软件安全性组最近在 Texas Hold 'em Poker（由 ASF
软件公司发行的） 实现中发现了一系列缺陷。这个揭秘允许欺骗性的玩家可以实时计算每人手中确切的牌。这意味着，使用这个揭秘的玩家可以知道每个对家手中的牌和将要发出的牌（指在一圈下赌后，将它面朝上放置的牌）。欺骗者每次可以“知道什么时候持有它们以及什么时候牌面朝下退出”。一个臭名昭著的攻击者可能使用这个揭秘，在未被发现的情况下来诈骗不知情玩家的钱财。这个缺陷存在于用来生成每副牌的洗牌算法中。具有讽刺意味的是，这个代码曾公在http://www.planetpoker.com/ppfaq.htm
上，为的是显示这个游戏是很公平的，来吸引玩家（这个页面从公布了它的缺陷后已经被拿掉了）。在这段代码中，用randomize() 来在每副牌生成前生成一副随机牌。这个的实现是用
Delphi 4构建的，随机数生成器的种子是按照系统时钟，用午夜后的毫秒数选取的。这意味着随机数生成器的输出是容易预测的。对，可预测的随机数生成器是一个很严重的安全性问题。
更好的办法是根据“随机事件”生成随机数，如键盘和鼠标输入值、中断、磁盘读取等等。然而，许多服务器没有键盘和鼠标，许多“黑盒”产品也不带有硬盘，因此很难找到好的随机数源，当然，通讯密钥也就一样不安全。而如网络状态等也不能很好地保证随机数的“随机性”。电器噪声和声音频率也许是很好的随机数源，但大多数人恐怕并不愿意在计算机中增加这种设备，而且也可能出现设备失灵和外部操纵（影响）等问题。对于要处理大量连接的网关服务器，是必须要考虑的问题。
如果可以通过，精确检测机器cpu的通电电流强度，来作为随机数种子，或是其他一些没有人为因素的干扰的，且瞬间变化快的方法获得种子，必将能产生符和要求的随机数。以上的尽是我个人的理解，一定会有很多的错误和纰漏，希望大家多多指教。
|
