算法导论 5.3-1

发布时间:2014-10-23 23:26:46
来源:分享查询网

1 问题 Marceau教授对引理5.5证明过程中使用的循环不变式表示异议。他对在第一次迭代之前循环不变式是否为真提出质疑。他的理由是人们可以容易地宣称空数组不包含0排列。因此空数组包含0排列的概率应该是0。所以第一次迭代之前循环不变式无效。请改写过程RANDOMIZE-IN-PLACE,使其相关的循环不变式在第一次迭代之前对非空数组仍使用,并为你的过程修改引理5.5的证明。 2 分析与解答 在循环的第一次迭代之前使循环不变式的数组不为空。 RANDOMIZE-IN-PLACE(A) n <- length[A] swap A[1] <-> A[RANDOM(1, n)] for i <- 2 to n do swap A[i] <-> A[RANDOM(i, n)] 证明: 改写引理5.5的循环不变式为:   在循环的第i次迭代开始前,对每个可能的(i-1)排列,在A[1…i-1]中出现的概率是(n-i+1)!/n!;   初始化:在循环的第1次迭代开始前,i=2,A[i-1] = A[ 1],由代码可知,此时A[1 ]中随机的包含A中元素的1排列, 满足循环不变式;   保持:假设在循环的第i次迭代开始前,循环满足不变式,即A中的元素的(i-1)排列,在A[1…i-1]中出现的概率是(n-i+1)!/n!,第i次循环,随机选择A[i…n]中元素的一个1排列赋值到A[i],那么每个1排列出现在A[i]中的概率是1/(n-i+1),考察第i次循环结束后序列A[1…i],由于A[1…i-1]是A中元素的一个i-1排列,A[i]只能从除去这i-1个元素的剩余元素中选择,所以A[1…i]是A中元素的一个i排列,而这个i排列出现在A[1…i]中的概率为A中元素的一个(i-1)排列出现在A[1…i-1]中的概率乘以剩余元素的一个1排列出现的概率,即为(n-i+1)!/n! * 1/(n-i+1)= (n-i)!/n!=(n-((i+1)-1))!/n!,所以在第i+1次迭代开始前,满足循环不变式;   终止:此时,i=n+1,按照不变式A[1…n]中存储着A中元素的一个n排列,而且每个n排列出现的概率为(n-(n+1)+1)!/n!= 1/n!,也就是说过程RANDOMIZE-IN-PALCE生成了均匀随机序列。

返回顶部
查看电脑版