<分区>
给你们的有趣的思考问题。给定一个长度为 n 的数组,如果我要在这个数组中选择两个随机索引,a 和 b 它们平均相隔多远是?至于从 a 走到 b 我需要走多少步。没有限制,所以我有可能为两者选择相同的索引,并且有可能 a 和 b 位于数组的两端。
我已经考虑了一段时间,我最初的想法是它们平均相差 n/2(ish),但我认为这种直觉是不正确的。在数组中心选择的索引至多 必须走 n/2 个位置才能找到其对应的第二个选择,而只有在数组的末端,第二个选择才会在 n 距离左右离开。
谢谢!
<分区>
给你们的有趣的思考问题。给定一个长度为 n 的数组,如果我要在这个数组中选择两个随机索引,a 和 b 它们平均相隔多远是?至于从 a 走到 b 我需要走多少步。没有限制,所以我有可能为两者选择相同的索引,并且有可能 a 和 b 位于数组的两端。
我已经考虑了一段时间,我最初的想法是它们平均相差 n/2(ish),但我认为这种直觉是不正确的。在数组中心选择的索引至多 必须走 n/2 个位置才能找到其对应的第二个选择,而只有在数组的末端,第二个选择才会在 n 距离左右离开。
谢谢!
最佳答案
在为 n 的前几个值绘制了一些可能距离的网格之后,我认为确切的结果实际上是:
f(n) = (n² - 1) / 3n
关于arrays - 数组中两个随机选择的索引之间的平均距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22057339/