首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C语言 >

求指点!关于随机算法的理解有关问题

2013-01-23 
求指点!!!关于随机算法的理解问题。各位老师,这是我从网络上获得并加以实际修改的一段取随机数的程序,但我

求指点!!!关于随机算法的理解问题。
  各位老师,这是我从网络上获得并加以实际修改的一段取随机数的程序,
但我没有理解它避免重复(代码中注释部分)的原理,请各位老师指点。
另外附带一问:若要使这个程序能避免出现40号和42号(我们班没有),应该如何修改?
P.S.抱歉可能要等一段时间才能回复,初三生不容易啊,在此先谢过各位老师了。

这代码写的  
如果真的想知道什么意思就单步吧!
求指点!关于随机算法的理解有关问题
[解决办法]
随机必然有重复。
所谓“不重复的随机”实际上是洗牌。
洗牌算法参考下面:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int d[6];
int i,n,a,b,t;
int c,j;
void main() {
    srand(time(NULL));
    printf("shuffle 0..n-1 demo\n");
    for (n=1;n<=5;n++) {/* 测试1~5个元素 */
        printf("_____n=%d_____\n",n);
        j=1;
        for (c=1;c<=n;c++) j=j*c;/* j为n! */
        j*=n*2;
        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */
            for (i=0;i<n;i++) d[i]=i;/* 填写0~n-1 */
            for (i=n;i>0;i--) {/* 打乱0~n-1 */


                a=i-1;b=rand()%i;
                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
            }
            printf("%04d:",c);
            for (i=0;i<n;i++) printf("%d",d[i]);
            printf("\n");
        }
    }
    printf("shuffle 1..n demo\n");
    for (n=1;n<=5;n++) {/* 测试1~5个元素 */
        printf("_____n=%d_____\n",n);
        j=1;
        for (c=1;c<=n;c++) j=j*c;/* j为n! */
        j*=n*2;
        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */
            for (i=1;i<=n;i++) d[i]=i;/* 填写1~n */
            for (i=n;i>1;i--) {/* 打乱1~n */
                a=i;b=rand()%i+1;
                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
            }
            printf("%04d:",c);
            for (i=1;i<=n;i++) printf("%d",d[i]);
            printf("\n");
        }
    }
}


[解决办法]
这些都是伪随机,也就是说每次虽然是随机的,但是从大体上讲,随机的序列是固定的,可参考下面代码:
unsigned int new_random(void)
{
int fd;
unsigned int n =0;
fd=open("/dev/urandom",O_RDONLY);
if(fd>0){
read(fd,&n,sizeof(n));
close(fd);
}
return n;
}
int getRangeNumber(int minNum, int maxNum)
{
int num = 0;

if(maxNum <2){
return 1;
}

//get seed for random()
unsigned int ticks;
struct timeval tv;
int fd;
gettimeofdaymodify(&tv,NULL);
ticks = tv.tv_sec + tv.tv_usec;
fd=open("/dev/urandom",O_RDONLY);
if(fd == -1)
{
return 1;
}
unsigned int r;
int i;
for(i=0;i<512;i++){
read(fd,&r,sizeof(r));
ticks += r;
}
close(fd);
srand(ticks);

srand((unsigned)time(NULL));
while (1)
{
    num=new_random()%maxNum;
    if (num >= minNum)
    {
        break;
    }
}

return num;
}

热点排行