Kiến trúc máy tính và hợp ngữ - Java methods

Algorithmschapter  4Copyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved.Java MethodsObject-Oriented Programmingand Data StructuresMaria Litvin ● Gary Litvin2nd AP edition  with GridWorld1Objectives:Understand general properties of algorithmsGet familiar with pseudocode and flowchartsLearn about iterations and recursionLearn about working with listsLearn basic facts about OOP2Define Algorithm...Hard to define formallyA more or less compact, general, and abstract step-by-step recipe that describes how to perform a certain task or solve a certain problem.Examples:Long divisionEuclid’s Algorithm for finding the greatest common factor (circa 300 BC)Binary Search (guess-the-number game) 3Tools for Describing AlgorithmsPseudocodeA sequence of statements, more precise notationNot a programming language, no formal syntaxFlowchartsGraphical representation of control flow4Example: calculate 12 + 22 + ... + n2PseudocodeInput: nsum  0k  1Repeat the followingthree steps while k  n: sq  k * k sum  sum + sq k  k + 1Output: sum A  BSet A to the value of B5Example (cont’d)Flowchartnsum  0k  1k  n ?sq  k * ksum  sum + sqk  k + 1sumNoYesInput / outputProcessing stepDecision6Another Example:1. Start at pos0, facing dir02. If wall in front, turn 90º clockwise else go forward3. If not back to initial position / direction proceed to Step 2 else stopdir  dir + 90ºpos = pos0and dir = dir0?YesNoYesNo pos  pos0 dir  dir0Step forwardInput:pos0, dir0StopWall in front?7VariablesAlgorithms usually work with variablesA variable is a “named container”A variable is like a slate on which a value can be written and later erased and replaced with another valuesum  sum + sqsum8Properties of AlgorithmsCompactness: an algorithm can use iterations or recursion to repeat the same steps multiple timesGenerality: the same algorithm applies to any “size” of task or any input valuesAbstractness: an algorithm does not depend on a particular computer language or platform (although it may depend on the general computing model)9Properties (cont’d)Input: nsum  0k  1Repeat the followingthree steps while k  n: sq  k * k sum  sum + sq k  k + 1Output: sum Compact: the same length regardless of n, thanks to iterations  the algorithm repeats the same instructions many times, but with different values of the variables(The “running time” depends on n, of course)General: works for any n10Properties (cont’d)def addSquares(n): s = 0 k = 1 while k ) { ... // do something } while (k ; ; ) { ... // do something } for ( int k = 1; k b?a  a - bb  b - aaYesYesNoNo22Euclid’s Algorithm (cont’d)With iterationsWith recursion public static int gcf (int a, int b) { while (a != b) // a not equal to b { if (a > b) a -= b; // subtract b from a else b -= a; // subtract a from b } return a; } public static int gcf (int a, int b) { if (a == b) // if a equals b return a; if (a > b) return gcf( a - b, b); else // if a < b return gcf(a, b - a); }Base case23Working with ListsA list is a data structure in which the items are numberedWe know how to get to the i-th itemWe know how to get from one item to the next quicklyAmy5Ben3Cal2Dan0Eve6In Java, the elements are counted from 0Fay1Guy424List Traversal Start at the first element While more elements remain process the next element for (int i = 0; i < list.length; i++) System.out.println (list [ i ]); for (String word : list) System.out.println (word);Increment i by 1Java’s “for each” loop (a.k.a. enhanced for loop)25Sequential SearchThe number of comparisons is proportional to n, where n is the length of the listAmy5Ben3Cal2Dan0Eve6Fay1Guy4Amy?Amy?Amy?Amy?Amy?Amy!26Binary Search“Divide and conquer” algorithmThe elements of the list must be arranged in ascending (or descending) orderThe target value is always compared with the middle element of the remaining search range27Binary Search (cont’d)Fay5Dan3Cal2Amy0Guy6Ben1Eve4Eve?Fay5Dan3Cal2Amy0Guy6Ben1Eve4Fay5Dan3Cal2Amy0Guy6Ben1Eve4Eve?Eve!28 Search: Sequential Binary The list can be in random orderThe number of comparisons is proportional to nFor a list of 1,000,000 elements takes, on average, 500,000 comparisonsThe list must be sorted (e.g., in ascending order)The number of comparisons is proportional to log2 nFor a list of 1,000,000 elements takes, on average, only 20 comparisons29Review:Why algorithms often use iterations?How is pseudocode different from Java code?Name three basic shapes used in flowcharts.Explain how variables are used in iterations.Which Java statements can be used to express iterations?30Review (cont’d):What is called a base case in recursion?Suppose we define “word” as a sequence of letters. Turn this into a recursive definition.When does Binary Search apply?How many comparisons, on average, are needed to find one of the values in a list of 1000 elements using Sequential Search? Binary Search?31