《算法课件全121301ADA10减治法减常因子算法II》由会员分享，可在线阅读，更多相关《算法课件全121301ADA10减治法减常因子算法II（12页珍藏版）》请在金锄头文库上搜索。
1、2019/6/21,2,2012-2013-01 Design and Analysis of Algorithm SCUN,Review of last class,The decrease and conquer technique and its three variations The application of decrease-by-a-constant-factor technique to search problem The binary search and its analysis,Decrease and Conquer (II),Chapter 5,Decrease
2、-by-a-Constant-Factor Algorithms Russian Peasant Multiplication Fake-coin Problem Josephus Problem,Variable-Size-Decrease Algorithms Euclids algorithm (Already learned!),2019/6/21,4,2012-2013-01 Design and Analysis of Algorithm SCUN,Russian Peasant Multiplication,Problem description: Compute the pro
3、duct of two positive integers n and m,It can be solved by a decrease-by-half algorithm based on the following formulas,2019/6/21,5,2012-2013-01 Design and Analysis of Algorithm SCUN,Example of Russian Peasant Multiplication,n m 50 65,Compute 50 * 65,25 130,12 260 130,6 520,1 2080 1040,3 1040,2080,20
4、19/6/21,6,2012-2013-01 Design and Analysis of Algorithm SCUN,Fake-Coin Puzzle (simpler version),Problem description: There are n identically looking coins one of which is fake. There is a balance scale but there are no weights; the scale can tell whether two sets of coins weigh the same and, if not,
5、 which of the two sets is heavier (but not by how much). Design an efficient algorithm for detecting the fake coin. Assume that the fake coin is known to be lighter than the genuine ones.,Decrease by factor 2 algorithm,Decrease by factor 3 algorithm,Thinking: For large values, about how many times f
6、aster is decrease by factor 3 algorithm than decrease by factor 2 algorithm?,2019/6/21,7,2012-2013-01 Design and Analysis of Algorithm SCUN,Josephus Problem,Problem description: There are n people numbered 1 to n stand in a circle. Starting the grim count with person number 1, we eliminate every sec
7、ond person until only one survivor is left. The goal is to determine the survivors number, denoted as J(n),2019/6/21,8,2012-2013-01 Design and Analysis of Algorithm SCUN,Josephus Problems Example,if n is even, i.e. n=2k,if n is odd, i.e. n=2k+1,In order to get J(n), we consider the cases of even and
8、 odd ns separately,J(2k) = 2J(k)1,J(2k1) = 2J(k)1,2019/6/21,9,2012-2013-01 Design and Analysis of Algorithm SCUN,The closed-form to the two-case recurrence,Can we get a closed-form solution to the two-case recurrence (subject to the initial condition J(1)=1?,The answer is yes, we can apply forward s
9、ubstitutions Compute J(n) for n=1,2,15 Discern a pattern in the solutions for the fifteen values of n Prove its general validity,The closed-form is: J(2k+i) = 2i +1 for i = 0, 1, ,2k-1,Practicable formula: J(n) = J(bkbk-1b0)2) = (bk-1b0bk)2,Example: J(41),2019/6/21,10,2012-2013-01 Design and Analysi
10、s of Algorithm SCUN,Euclids algorithm is based on repeated application of equality gcd(m, n) = gcd(n, m mod n),Euclids Algorithm,We can prove that the size, measured by the second number, decreases at least by half after two consecutive iterations. Hence, T(n) O(log n),Ex.: gcd(80,44) = gcd(44,36) =
11、 gcd(36, 8) = gcd(8,4) = 4,Is Euclids algorithm belongs to variable-size-decrease ? (why),The answer is yes. If we measure the input size by the size of the second parameter, after an application of the equality, the size of the new pair will be (m mod n). It can be any integer between 0 and n-1.,Whats efficiency of Euclids algorithm?,The End,2019/6/21,12,2012-2013-01 Design and Analysis of Algorithm SCUN,Assignments,Reading assignment: Section 5.6(p188) Exercises: No 1, 2, 5(a) of exercises 5.5 (p187),
