算法课件全121301ADA10减治法减常因子算法II.pptVIP

2007-2008-01《Design and Analysis of Algorithms》SCUEC 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 Russian Peasant Multiplication Problem description: Compute the product of two positive integers n and m Example of Russian Peasant Multiplication n m 50 65 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, 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. 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 second person until only one survivor is left. The goal is to determine the survivor’s number, denoted as J(n) Josephus Problem’s Example 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? Euclid’s Algorithm Euclid’s algorithm is based on repeated application of equality gcd(m, n) = gcd(n, m mod n) The End Assignments Reading assignment: Section 5.6(p188) Exercises: No 1, 2, 5(a) of exercises 5.5 (p187) 2012-2013-01 《Design and Analysis of Algorithm》 SCUN * Decrease and Conquer (II) Chapter 5 Decrease-by-a-Constant-Factor Algorithms Russian Peasant Multiplication Fake-coin Problem Josephus Problem Variable-Size-Decrease Algorithms Euclid’s algorithm (Already learned!) It can be solved by a decrease-by-half algorithm based on the following formulas Compute 50 * 65 25 130