算法分析与设计第7章.ppt

补充例题： 标识重复元素算法 ACM POJ 3318 ——? Matrix MultiplicationTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 15971 Accepted: 3447 Description You are given three?n?×?n?matrices?A,?B?and?C. Does the equation?A?×?B?=?C?hold true? Input The first line of input contains a positive integer?n?(n?≤ 500) followed by the the three matrices?A,?B?and?C?respectively. Each matrixs description is a block of n × n integers. It guarantees that the elements of?A?and?B?are less than 100 in absolute value and elements of?C?are less than 10,000,000 in absolute value. Output Output YES if the equation holds true, otherwise NO. Hint Multiple inputs will be tested. So O(n3) algorithm will get TLE. ACM POJ 3318 ——? Matrix MultiplicationTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 15971 Accepted: 3447 两个矩阵直接相乘需要O(n^3)的时间复杂度 再用O(n^2)的时间进行AB与C的比较，返回是否相等。 ACM POJ 3318 ——? Matrix MultiplicationTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 15971 Accepted: 3447 ACM POJ 3318 ——? Matrix MultiplicationTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 15971 Accepted: 3447 * 蒙特卡罗(Monte Carlo)算法 在实际应用中常会遇到一些问题，不论采用确定性算法或随机化算法都无法保证每次都能得到正确的解答。蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。 设p是一个实数，且1/2p1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。 如果对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是一致的。 有些蒙特卡罗算法除了具有描述问题实例的输入参数外，还具有描述错误解可接受概率的参数。这类算法的计算时间复杂性通常由问题的实例规模以及错误解可接受概率的函数来描述。 * 主元素问题 设T[1:n]是一个含有n个元素的数组。当|{i|T[i]=x}|n/2时，称元素x是数组T的主元素。 templateclass Type bool Majority(Type *T, int n) {// 判定主元素的蒙特卡罗算法 int i=rnd.Random(n)+1; Type x=T[i]; // 随机选择数组元素 int k=0; for (int j=1;j=n;j++) if (T[j]==x) k++; return (kn/2); // kn/2 时T含有主元素 } templateclass Type bool MajorityMC(Type *T, int n, double e) {// 重复调用算法Majority int k=ceil(log(1/e)/log(2)); for (int i=1;i=k;i++) if (Majority(T,n)) return true; return false; } 对于任何给定的?0，算法majorityMC重复调用?log(1/?)? 次算法majority。它是一个偏真蒙特卡罗算法，且其错误概率小于?。算法majorit