tailieunhanh - Lecture Java methods: Object-oriented programming and data structures (2nd AP edition): Chapter 4 - Maria Litvin, Gary Litvin

Chapter 4 - Algorithms. This chapter’s objectives are to: Understand general properties of algorithms, get familiar with pseudocode and flowcharts, learn about iterations and recursion, learn about working with lists, learn basic facts about OOP. | Algorithms chapter 4 Copyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 2nd AP edition with GridWorld 4- Too often students want to jump to writing code without the necessary background in algorithms. Objectives: Understand general properties of algorithms Get familiar with pseudocode and flowcharts Learn about iterations and recursion Learn about working with lists Learn basic facts about OOP 4- Much more on recursion in Chapter 23. Define Algorithm. Hard to define formally A 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 division Euclid’s Algorithm for finding the greatest common factor (circa 300 BC) Binary Search (guess-the-number game) 4- Fundamental concepts are often hard to define! Tools for Describing Algorithms Pseudocode A . | Algorithms chapter 4 Copyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 2nd AP edition with GridWorld 4- Too often students want to jump to writing code without the necessary background in algorithms. Objectives: Understand general properties of algorithms Get familiar with pseudocode and flowcharts Learn about iterations and recursion Learn about working with lists Learn basic facts about OOP 4- Much more on recursion in Chapter 23. Define Algorithm. Hard to define formally A 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 division Euclid’s Algorithm for finding the greatest common factor (circa 300 BC) Binary Search (guess-the-number game) 4- Fundamental concepts are often hard to define! Tools for Describing Algorithms Pseudocode A sequence of statements, more precise notation Not a programming language, no formal syntax Flowcharts Graphical representation of control flow 4- In pseudocode and flowcharts we do not use data types for variables (such as int, double, etc.); in Java we do. Example: calculate 12 + 22 + . + n2 Pseudocode Input: n sum 0 k 1 Repeat the following three steps while k n: sq k * k sum sum + sq k k + 1 Output: sum A B Set A to the value of B 4- The “repeat” statement is what makes this algorithm compact. Example (cont’d) Flowchart n sum 0 k 1 k n ? sq k * k sum sum + sq k k + 1 sum No Yes Input / output Processing step Decision 4- Flowcharts are pretty much history: they are really not used in software development any more since most software development has switched to OOP. Another Example: 1. Start at pos0, facing dir0 2. If wall in front, turn 90º clockwise else go forward 3. If not back to initial position / direction proceed to Step 2 else stop dir