mat*_*y-d 0 arrays algorithm probability
对你们有趣的思考问题.给定一个长度为n的数组,如果我要在这个数组中选择两个随机索引,a和b平均相隔多远？至于从a到b步行需要多少步骤.没有限制因此我有可能为两者选择相同的索引,并且a和b有可能位于数组的两端.
我已经考虑了一段时间,我最初的想法是他们平均分别是n/2(ish),但我认为这种预感是不正确的.在阵列的中心选择的索引至多就得走n/2个地方找到其相应的第二个选择,而只在阵列的端部将在第二选择永远是围绕Ñ距离.
谢谢!
在为n的前几个值编写一些可能距离的网格之后,我认为确切的结果实际上是由下式给出的:
f(n) = (n² - 1) / 3n