设A [1 .. n]是n distinct个数的数组.如果i <j且A [i]> A [j],那么对(i,j)被称为A的反转.(有关反演的更多信息,请参阅问题2-4.)假设选择A的每个元素从1到n的范围内随机,独立地和均匀地.使用指标随机变量来计算预期的反转次数.
问题来自Cormen的算法导论中的练习5.2-5 .这是我的递归解决方案:
假设x(i)是[1..i]中的反转次数,而E(i)是x(i)的期望值,那么E(i + 1)可以如下计算:
我们有的图像i+1如果我们将i + 1置于第一个位置,则放置所有数字的位置,然后x(i + 1)= i + x(i); 如果我们将i + 1放在第二个位置,那么x(i + 1)= i-1 + x(i),...,所以E(i + 1)= 1 /(i + 1)*sum( k)+ E(i),其中k = [0,i].最后我们得到E(i + 1)= i/2 + E(i).
因为我们知道E(2)= 0.5,所以递归得到:E(n)=(n-1 + n-2 + ... + 2)/ 2 + 0.5 = n*(n-1)/ 4 .
虽然上面的推论似乎是正确的,但我仍然不太确定.所以我在这里分享.
如果有问题,请纠正我.
在Google Maps API v2中,我想在拖动标记之前存储先前的位置,但是,当我开始拖动标记时,它将始终跳转到某个较高位置,因此在回调中onMarkerDragStart,我无法获得最后位置.
这是一个错误,还是可以解决问题？
我不确定以下伪代码是否可以生成uniformly random permutation:
PERMUTATE(A):
n = A.length
for i = 1 to n
swap A[i] and A[random(1,n)]
这似乎是对的,但任何人都可以给我一个严格的证据来验证其正确性或错误吗？
除了某些概念外,我觉得它们彼此非常相似.在外部排序中,它们的功能基本相同,即在k 次运行中找到最小/最大值.那么两者之间有一些显着的差异吗？
可以在VC或gcc上正确编译以下代码:
char *str = "I am a const!";
str[2] = 'n';
但是,显然存在运行时错误.因为"我是一个常客!" 是一个const char*,为什么编译器不会给出错误甚至是警告？
此外,如果我定义char a[] = "I am const!",a可以修改所有元素,为什么这次字符串文字成为nonconst？
我现在正在找工作并做很多算法练习.这是我的问题:
给定两个数组:a和b具有相同的长度,主题是| sum(a)-sum(b)| 最小化,通过交换a和b之间的元素.
这是我的:
假设我们交换a [i]和b [j],设置Delt = sum(a) - sum(b),x = a [i] -b [j]
然后Delt2 = sum(a)-a [i] + b [j] - (sum(b)-b [j] + a [i])= Delt - 2*x,
则变化 = | Delt | - | Delt2 |,与| Delt | ^ 2 - | Delt2 | ^ 2 = 4*x*(Delt-x)成比例,
根据上面的想法,我得到以下代码:
Delt = sum(a) - sum(b);
done = false;
while(!done)
{
done = true;
for …假设A类是B类的朋友,B是C类的朋友,A是C的朋友,A是A的朋友,还是两者,或者没有？