这个C执行Fisher-Yates洗牌是否正确？

概述以下是Fisher-Yates的C实现,我想使用一个甲板洗牌程序.我正在做这个(n =数组的长度)？ 注意：do-while循环尝试纠正模偏(见here).它为该过程增加了一些开销,如果不关心低位偏差,可以消除该过程. void shuffle(int *array, int n) { int i, j, tmp, upper_bound; srand(time(NULL)); 以下是Fisher-Yates的C实现,我想使用一个甲板洗牌程序.我正在做这个(n =数组的长度)？

注意：do-while循环尝试纠正模偏(见here).它为该过程增加了一些开销,如果不关心低位偏差,可以消除该过程.

voID shuffle(int *array,int n) {  int i,j,tmp,upper_bound;  srand(time(NulL));  for (i = n - 1; i > 0; i--) {    upper_bound = RAND_MAX - ((RAND_MAX % (i + 1)) + 1);    do {      j = rand() % (i + 1);    } while (j > upper_bound);    tmp = array[j];    array[j] = array[i];    array[i] = tmp;     }}

解决方法 首先,您应该提取用于生成在0(包括)和n(独占)之间均等分配到一个单独的函数的随机数的代码.这也是您在其他地方需要工作的一项不错的工作.

第二,我不会在洗牌功能中调用srand,而是依赖于调用者初始化随机数生成器.这样你可以在一秒钟内洗牌一次以上.

第三,你应该做j>的测试. upper_bound除以i 1.我不大可能会接近RAND_MAX.

static int rand_int(int n) {  int limit = RAND_MAX - RAND_MAX % n;  int rnd;  do {    rnd = rand();  } while (rnd >= limit);  return rnd % n;}voID shuffle(int *array,int n) {  int i,tmp;  for (i = n - 1; i > 0; i--) {    j = rand_int(i + 1);    tmp = array[j];    array[j] = array[i];    array[i] = tmp;  }}

要检查此实现是否正确,您需要确保随机数生成器询问log2(n！)位的随机性.换句话说,给予rand_int函数的所有ns的乘积必须是n！

总结

以上是内存溢出为你收集整理的这个C执行Fisher-Yates洗牌是否正确？全部内容，希望文章能够帮你解决这个C执行Fisher-Yates洗牌是否正确？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。