注意: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洗牌是否正确?所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)