波波老师，关于随机函数的两个问题
来源：5-10 二分搜索树的局限性
慕运维6075306
2021-08-30
这里rand()%i是不是更好，如果是i+1的话，就可能发生自己和自己交换的情况？
是不是由于srand(time(NULL))函数的存在，所以i=x的概率非常小，所以这里写不写成i都没关系？
写回答
1回答
-
这个算法不在这个课程的讲解范围里，但你要是有兴趣，可以搜索查询一下 Knuth Shuffle 算法，这一段代码是 Knuth Shuffle 算法。我专门写过一篇公众号文章：https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247484310&idx=1&sn=916f92afff6016256648cfb3c7fd83e7&chksm=fd8cacd0cafb25c670587f22524b111d74b4ddd9954070930b6ef6efb1bd8fba13d4250e57d8&token=1188254129&lang=zh_CN#rd
随便提供两个角度“反驳”为什么需要是 i + 1 不是 i：
1）如果是 i，每一步随机的结果就不可能是自己，那么整个算法就无法“随机出”一个和自己一模一样的序列。但是，和自己一模一样的序列，是一个合法的随机结果，能够出现的概率应该是 1/ (n!)，而不是 0（实际上，由这 n 个数字组成的人一个序列，出现的概率都应该是 1 / (n!)）
2) 循环中 i 可以到 0，如果 % i，% 0 是非法的。
继续加油！：）
022021-08-31
相似问题