Chapter 1: General Problem-Solving Concepts PDF

Chapter 1: General Problem-Solving Concepts SW 100: Principles of Programming and Problem Solving Dr.HYA 2023 1 Overview What is problem solving Problem solving in daily life The six steps in problem solving The problem of what to do this even...

Chapter 1: General Problem-Solving Concepts SW 100: Principles of Programming and Problem Solving Dr.HYA 2023 1 Overview What is problem solving Problem solving in daily life The six steps in problem solving The problem of what to do this evening Types of the problem Problem Solving with computers Terminologies Difficulties with Problem Solving Dr.HYA 2023 2 Problem Solving Problem solving is the process of transforming the description of a problem into the solution of that problem by using our knowledge of the problem domain and by relying on our ability to select and use appropriate problem-solving strategies, techniques, and tools. Dr.HYA 2023 3 The six steps in problem solving 6- Evaluate the solution 1- Identify the problem 5- List instructions 2- Understand the problem 4- Select the best way to 3- Identify alternatives solve the problem Dr.HYA 2023 4 The six steps in problem solving[1-5] 1. Identify the problem. What is the specific problem? (This means you should determine what is that you want to change) Clearly define the goal that you want to achieve. (What are you trying to achieve?) Determine what are the inputs and outputs Dr.HYA 2023 5 The six steps in problem solving[1-5] 2. Understand the problem. Understanding the knowledge base of the person or machine for whom you are solving the problem. Also, you also must know your own knowledge base. You cannot solve a problem if you do not know the subject. For example, to solve a problem involving accounting, you must know accounting Dr.HYA 2023 6 The six steps in problem solving[2-5] 3. Identify alternative ways to solve the problem Generate as many potential solutions as possible List the features for each possible solution You might want to talk to other people to find other solutions than those you have identified. Alternative solutions must be acceptable ones. Dr.HYA 2023 7 The six steps in problem solving[3-5] 4. Select the best way to solve the problem from the list of alternative solutions Select criteria for the evaluation. Identify and evaluate the pros and cons of each possible solution before selecting the best one based on the selected criteria. Dr.HYA 2023 8 The six steps in problem solving[4-5] 5. List instructions that enable you to solve the problem using the selected solution. These numbered, step-by-step instructions must fall within the knowledge base set up in step 2. No instruction can be used unless the individual or the machine can understand it. Dr.HYA 2023 9 The six steps in problem solving[5-5] 6. Evaluate the solution Means check its result to see if it is correct, and to see if it satisfies the needs of the person(s) with the problem. Test the solution Are the results accurate? Does the solution solve the original problem? Does it satisfy the needs of the user? Is it acceptable to the user? Dr.HYA 2023 10 Problems examples People solve problems daily at home, or work, or wherever they go. At home: At work: what to cook for dinner The problems might which movie to see this involve dealing with: evening work policies which car to buy Management Customers Dr.HYA 2023 11 The problem of what to do this evening 1. Identify the problem: How do the individuals wish to spend the evening? 2. Understand the problem. The knowledge base of the participants must be considered. The only solutions that should be selected are ones that everyone involved would know how to do. Example? Dr.HYA 2023 12 The problem of what to do this evening 3. Identify alternatives. a. Watch television. b. Invite friends over. c. Play video games. d. Go to the movies. e. Play miniature golf. f. Go to the amusement park. g. Go to a friend’s party. Note: The list is complete only when you can think of no more alternatives. Dr.HYA 2023 13 The problem of what to do this evening 4. Select the best way to solve the problem. a. Weed out alternatives that are not acceptable, such as those that cost too much money or do not interest one of the individuals involved. b. Specify the pros and cons of each remaining alternative. c. Weigh the pros and cons to make the final decision. Dr.HYA 2023 14 The problem of what to do this evening 5. Prepare a list of steps (instructions) that will result in a fun evening. 6. Evaluate the solution. Are we having fun yet? Dr.HYA 2023 15 Problem solving with computers Dr.HYA 2023 16 Types of Problems Problems with … Algorithmic solutions: Solutions that can be reached with a series of actions Example: baking a cake. These steps are called the algorithm. Heuristic solutions Solutions that cannot be reached through a direct set of steps require reasoning built on knowledge and experience, and a process of trial and error. Example: how to buy the best stock or whether to expand the company. Dr.HYA 2023 17 Problem Solving with Computers Terminologies: Solution  instructions followed to produce best result Result  outcome, computer-assisted answer Program  instructions for solution using computer language Algorithm  a step by step solution to a problem. Dr.HYA 2023 19 Problem Solving with Computers Computers are built to deal with algorithmic solutions. People are better than computers at developing heuristic solutions. How? The field of computers that deals with heuristic types of problems is called artificial intelligence. Dr.HYA 2023 20 Difficulties with Problem Solving Lack of problem solving experience Inadequate solution steps Incorrect problem definition Alternatives chosen incorrectly Invalid logic Incorrect solution evaluation Dr.HYA 2023 21 Difficulties with Problem Solving Task: Which number is the largest from a group of three numbers? Dr.HYA 2023 22  Algorithmic solution example RIVER CROSSING PROBLEM A farmer has a FOX, a GOAT, and a CABBAGE. He wants to cross a river, but his boat will hold only one item beside himself. He cannot leave the FOX with the GOAT, or the GOAT with the CABBAGE. How can he get all THREE across the river? Dr.HYA 2023 23 A 15th Cheltenham (SHURDINGTON) Scout Group resource - 1995 End Chapter 1 Dr.HYA 2023 24 Resources Book: Problem Solving and Programming Concepts 9th Edition By Maureen Sprankle and Jim Hubbard Pictures: 1. This Photo by Unknown Author is licensed under CC BY-SA-NC 2. This Photo by Unknown Author is licensed under CC BY-NC 3. This Photo by Unknown Author is licensed under CC BY-NC 4. This Photo by Unknown Author is licensed under CC BY-ND 5. This Photo by Unknown Author is licensed under CC BY-SA Dr.HYA 2023 25 Overview of programming and how does a computer run a program Chapter 2 SW100 Dr.HYA 2024 1 Overview Programs Six Steps for Problem Solving Using a Computer Interpreting/Compiling Source Code Compiling and Running a Java Program Dr.HYA 2024 2  Programming Dr.HYA 2024 3 Programs A program is simply a set of instructions for a computer to follow. When you give the computer a program and some data and tell the computer to follow the instructions in the program, you are running, or executing, the program on the data For example, text editors and word processors are programs. Dr.HYA 2024 4 Six Steps for Problem Solving Using a Computer 1- Problem analysis Understand the problem and what the solution must do Define the exact requirements, inputs, outputs, constraints and process. Dr.HYA 2024 5 Six Steps for Problem Solving Using a Computer 2. Program Design - Algorithm, Flowchart, and Pseudocode Algorithm: Create a step-by-step plan or procedure to solve the problem. Flowchart: Visualize the algorithm using diagrams that represent the flow of control. Pseudocode: Write a formal description of the algorithm using a combination of natural language and programming constructs. It is not “real code”. Dr.HYA 2024 6 Six Steps for Problem Solving Using a Computer 3. Coding Choose a programming language: Select a language suitable for the problem and your skill level. Implement the algorithm: Translate the pseudocode into actual code using the chosen language's syntax. 4. Running (Executing) the program on the computer. This step uses a program compiler or interpreter. Dr.HYA 2024 7 Six Steps for Problem Solving Using a Computer 5. Debugging and Testing Debugging is the process of identifying and fixing errors or bugs in a computer program. Testing is the process of verifying that a software program meets its specified requirements and functions as intended. It involves executing the program with various inputs and comparing the output to the expected results. Dr.HYA 2024 8 Six Steps for Problem Solving Using a Computer 6. Program Documentation Create documentation: Write clear and concise explanations of the program's purpose, usage, and how it works. Include comments: Add comments within the code to explain specific sections or algorithms Dr.HYA 2024 9 In this course we will focus on Step 1 and Step 2 Dr.HYA 2024 10 Problem: Calculating the Area of a Rectangle Problem Statement: Given the Height and width of a rectangle, calculate its area. 1. Problem Analysis Inputs: Height and width of the rectangle. Outputs: Area of the rectangle. Constraints: Both Height and width should be non-negative. Processing Steps: 1. Read inputs: Prompt the user to enter the Height and width of the rectangle. 2. Validate inputs: Ensure that both Height and width are non-negative. 3. Calculate area: Multiply the Height and width to determine the area of the rectangle. Area = Width * Height 4. Display result: Output the calculated area. Dr.HYA 2024 11 Problem: Calculating the Area of a Rectangle 2. Program Design - Algorithm, Flowchart, and Pseudocode Decide whether the following algorithm is good or bad and explain why. Algorithm A: Algorithm B: 1. Ask the user to enter Width 1. Ask the user to enter Width 2. Ask the user to enter Height 2. Ask the user to enter Height 3. If Width and Height are both greater 3. If Width and Height are both than 0, set Area to (Width × Height). greater than 0, calculate Area. 4. Otherwise, display an error message 4. Otherwise, display an error and exit. message and exit. 5. Display Area for the user 5. Display Area for the user Dr.HYA 2024 12  Problem: Calculating the Area of a Rectangle Algorithm C: Algorithm D: 1. Set Area to (Width × Height) 1. Set Area to (Width × Height) 2. Ask the user to enter Width 2. Display Area for the user 3. Ask the user to enter Height Algorithm E: 4. Check if Width and Height are both 1. Ask the user to enter Width greater than 0. 2. Ask the user to enter Height 5. If either Width or Height is less than 3. If Width and Height are both greater than or equal to 0, display an error message 0, set Area to (Width × Height x 2). and exit. 4. Otherwise, display an error message and 6. Display Area for the user exit. 5. Display Area for the user Dr.HYA 2024 13 Problem: Calculating the Area of a Rectangle Flowchart: Pseudocode: BEGIN INPUT Height INPUT width IF Height 0 OR Y < 100 4. DataOk (DataOk is a logical datum) Dr.HYA 6 The Decision Logic Structure Logical operators are used to link more than one condition together. For example, consider a store policy requiring that to cash a check, a customer must have a driver’s license, AND the check must be under $50. Two conditions are linked by the logical operator AND. ( Check < 50 AND DriverLicense ) note: the data type of DriverLicense is logical. Dr.HYA 7 The Decision Logic Structure The programmer can set up the conditions for a decision through the use of operands and various operators. These conditions can be used alone or linked with other conditions for use in the instruction. The programmer derives the information needed to set up the condition(s) for a decision from the problem itself during problem analysis. Dr.HYA 8 Flowchart Diagram of the Decision Structure Dr.HYA 9 Single Condition—Two Possible Actions or Sets of Actions Dr.HYA 10 Next… Common forms of decision logic structure Logic conversion Decision table Dr.HYA 11 Common Forms of the Decision Logic Structure If/Then/Else instruction Single Condition Multiple Condition Multiple If/Then/Else Instructions Straight-through Logic Positive logic Negative logic Dr.HYA 12 Single Condition A simple decision with only one condition and one action or set of actions (one instruction or set of instructions) for True and another for False is relatively simple. Dr.HYA 13 Single Condition For example, assume you are calculating pay at an hourly rate and overtime pay (over 40 hours) at 1.5 times the hourly rate. The decision to calculate pay would be stated in the following way: Hourly rate: Pay=PayRate * Hours Overtime pay: Pay=PayRate * (40 + 1.5 * (Hours-40)) If the hours are greater than 40, Then the pay is calculated for overtime, or Else the pay is calculated in the usual way. Dr.HYA 14 Single Condition Dr.HYA 15 Multiple Conditions Decisions in which you have multiple conditions that lead to one action or set of actions for True and another action or set of actions for False are slightly more complicated than those with single conditions. In these decisions you will use logical operators to connect the conditions. Dr.HYA 16 Multiple If/Then/Else Instructions There are three types of decision logic you will use to write algorithms for solutions consisting of more than one decision : 1. Straight-through Logic 2. Positive logic 3. Negative logic Dr.HYA 17 Straight-through logic Straight-through logic means that all of the decisions are processed sequentially, one after the other. There is no Else part of the instructions; The False branch always goes to the next decision, The True branch goes to the next decision after the instructions for the True branch have been processed. Dr.HYA 18 Straight-through logic Straight-through logic is the least efficient of all types of decision logic because all the decisions must be processed. However, you must use it to solve certain problems: Those that require two or more unrelated decisions Those in which all decisions must be processed. Dr.HYA 19 Straight-through logic: Example 1 Example 1: Find the amount to charge people of varying ages for a concert ticket. When the person is under 16, the charge is $7; when the person is 65 or over, the charge is $5; all others are charged $10. The conditions are the following: Age Charge Age < 16 7 Age >= 16 and Age < 65 10 Age >= 65 5 Dr.HYA 20 Straight-Through Logic: Example 1 Dr.HYA 21 Straight-through logic: Example 2 Example 2: Change the value of X to 0 when X becomes greater than 100, and to change the value of Y to 0 when Y becomes greater than 250. Each decision is independent of the other. The conditions are X > 100 X becomes 0 Y < 250 Y becomes 0 Dr.HYA 22 Straight-through logic: Example 2 Straight-through logic is required when all the decisions have to be processed, and when they are independent of each other. Based on these criteria, the only appropriate logic type for the decision in Example 2 would be straight-through logic. Dr.HYA 23 Straight-through logic: Example 2 Dr.HYA 24 Using Positive Logic On the other hand, with positive logic not all of the instructions are processed. Positive logic allows the flow of the processing to continue through the module instead of processing succeeding decisions, once the resultant of a decision is True. Whenever the resultant is False (the Else part of the decision), another decision in the sequence is processed until the resultant is True, or there are no more decisions to process. Dr.HYA 25 Positive Logic: Example 1 Example 1: The same problem, and therefore, the same set of conditions as in Slide 30. Age Charge Age < 16 7 Age >= 16 and Age < 65 10 Age >= 65 5 Dr.HYA 26 Positive Logic: Example 1 Dr.HYA 27 Positive Logic: Example 1 Notice that there are fewer decisions processed than in slide 31—two compared to three—even if all the decisions are processed. When the age is NOT less than 16, it has to be greater than or equal to 16. Therefore, the third decision in the set of conditions is not necessary. Dr.HYA 28 Using Positive Logic: Example 2 Example1: Calculate the commission rate for a salesperson, given the amount of sales. When the salesperson has sold less than or equal to $2,000 worth of goods, the commission is 2%. When the sales total is more than $2,000 and less than or equal to $4,000, the commission is 4%. When the sales total is more than $4,000 and less than or equal to $6,000, the commission is 7%. When the person has sold more than $6,000, the commission is 10%. Dr.HYA 29 Using Positive Logic: Example 2 The conditions are the following: Sales Commission < = 2000 0.02 2001 - 4000 0.04 4001-6000 0.07 > 6000 0.10 Dr.HYA 30 Using Positive Logic: Example 2 Dr.HYA 31 Using Positive Logic: Example 2 Dr.HYA 32 Negative logic Negative logic is similar to positive logic except that the flow of the processing continues through the module when the resultant of a decision is False. Whenever the resultant is True, another decision is processed until the resultant is False, or there are no more decisions to process. At that time, the True branch processes the remaining instructions. Negative logic is the hardest to use and understand. Dr.HYA 33 Negative Logic: Example 1 Example 1: The same problem, and therefore, the same set of conditions as in slide 11 and slide 17. Age Charge Age < 16 7 Age >= 16 and Age < 65 10 Age >= 65 5 Dr.HYA 34 Negative Logic: Example 1 Dr.HYA 35 Negative Logic: Example 2 Example 2: The same problem using positive logic in slide 21. The conditions are the following: Sales Commission < = 2000 0.02 2001 - 4000 0.04 4001-6000 0.07 > 6000 010 Dr.HYA 36 Negative Logic: Example 2 Dr.HYA 37 Negative Logic: Example 2 Dr.HYA 38 Nested If/Then/Else instructions In algorithms containing multiple decisions, you may have to write nested If/Then/Else instructions. Decisions using positive and negative logic use nested If/Then/Else instructions. Decisions using straight-through logic do not. Dr.HYA 39 Revision So far, we have covered the following: If/Then/Else instruction Single and Multiple Conditions Multiple If/Then/Else Instructions Straight-through Logic Positive logic Negative logic Now let’s move to the logic conversion and decision table. Dr.HYA 40 Logic Conversion There are times when it is necessary to change the logic from positive to negative or vice versa in order to improve the efficiency or readability of a solution. In a decision, there must always be instructions for a True section, but not always for a False section. If there are no instructions for the True section of a decision instruction, then it is better to convert the logic type. Dr.HYA 41 Logic Conversion To convert from positive logic to negative logic or vice versa, do the following: 1. Change all < to >= 2. Change all 3. Change all > to = to < 5. Change all = to 6. Change all to = 7. Interchange all of the Then set of instructions with the corresponding Else set of instructions. Dr.HYA 42 Conversion from Positive Logic to Negative Logic Dr.HYA 43 Conversion from Positive Logic to Negative Logic Dr.HYA 44 Which Decision Logic? The general rule is to evaluate all three types for each solution and choose the one that is most readable, requires the fewest tests, easiest to maintain. If you find at the end of the analysis that more than one of the logic types could be equally effective, then simply choose one. Dr.HYA 45 Which Decision Logic? Example 1 Example 1: The problem is to calculate a pay bonus given the set of conditions: From the data given, which logic type is the most efficient? Dr.HYA 46 Which Decision Logic? Example 1 Dr.HYA 47 Which Decision Logic? Example 1 Dr.HYA 48 Which Decision Logic? Example 1 Dr.HYA 49 Which Decision Logic? Example 1 Dr.HYA 50 Decision Tables You may have a problem with multiple conditions and multiple consequent actions. In such a case discovering all of the actions that correspond to particular conditions can be complicated. A good way to simplify this process is to draw a decision table. You would draw a decision table during problem analysis. Dr.HYA 51 Decision Tables A decision table consists of four parts: 1. The conditions 2. The actions 3. The combinations of True and False for the conditions 4. The action to be taken or the consequences for each combination of conditions Dr.HYA 52 Decision Table Format Dr.HYA 53 Decision Table Format 1. Draw a decision table in the form of a rectangle divided into the four major sections. 2. Each section is divided into smaller sections, as needed, according to the number of possible combinations of True and False 3. The total number of possible combinations of True and False for the conditions is two to the power of the number of conditions. two conditions  2^2 = 4 possible combinations of True and False. three conditions  2^3 = 8 possible combinations of True and False. Dr.HYA 54 Flowchart development from the decision table The four steps to develop a flowchart from the decision table are the following: 1. Draw all decisions in flowchart form. 2. Compare the true and false sides of each decision, starting with the first one. 3. Eliminate any decisions that have the same instructions on both the true and false sides, keeping the true consequence or action. 4. Redraw the flowchart Dr.HYA 55 Starting Flowchart from the decision table Dr.HYA 56 Elimination of Conditions Notice that the true side of decision one is exactly the same as the false side. Therefore, this decision is not needed. The decision and the false side can be eliminated. The true side and the false side of the second decision are different and therefore, they need to stay. The same is true for the third decision. Dr.HYA 57 Elimination of Conditions Dr.HYA 58 Final Flowchart Dr.HYA 59 Decision Table Example There are three conditions: 1. The purchase is less than $100. 2. The last payment to the account was made in the last 30 days. 3. The balance of the account is less than $1,000. Each of these three conditions could be True or False depending on the customer. The following actions could be taken: 1. Credit is okay, and the customer can charge the item. 2. Refer the customer to the credit department. 3. Credit is denied and the customer cannot charge the item. Dr.HYA 60 Decision Table Example These conditions and actions are supplied by the manager of the credit department. The manager also states when each of the actions will take place. Dr.HYA 61 Starting Flowchart from the Table Dr.HYA 62 Elimination of Conditions Dr.HYA 63 Elimination of Conditions Dr.HYA 64 Final Algorithm Dr.HYA 65 Final Flowchart Dr.HYA 66 End of Lecture 7 Dr.HYA 67  Lecture 8: Problem Solving with Loops SW 100: Principles of Programming and Problem Solving Dr.HYA 1 Overview The Loop Logic Structure Incrementing Accumulating While/WhileEnd Repeat/Until Automatic-Counter Loop Nested Loops Recursion Dr.HYA 2 The Loop Logic Structure A third logic structure for designing decisions is the loop structure. The loop logic structure is the repeating structure. Example: The Process of calculating the Total Payment for more than one employee. Dr.HYA 3 Example Write an Algorithm that calculate the average of 6 students grade. Average() 1. Enter Grade1, Grade2, Grade3, Grade4, Grade5, Grade6 What about 100 2. Total = Grade1+ Grade2+Grade3+Grade4+Grade5+ students? Grade6 3. Average = Total / 6 We need to use a 4. Print Average loop logic structure End Dr.HYA 4 Types of Loop Structure While/WhileEnd loop which repeats instructions while a condition is True and stops repeating when a condition arises that is not True. Repeat/Until loop, which repeats instructions while a condition is False or until a condition is True. Automatic-counter loop in which a variable is set equal to a given number and increases in equal given increments until it is greater than an ending number. Dr.HYA 5 Types of Loop Structure The algorithm and the flowchart differ with each type of loop structure. Several standard types of tasks are accomplished through the use of the loop structure. Two of these types are: counting (also called incrementing and decrementing) accumulating (also called calculating a sum or a total) Dr.HYA 6 Types of Loop Structure In both tasks (counting, accumulating) a number is added or subtracted from a variable and the result is stored back into the same variable. In each case the resultant variable is assigned the value of zero before starting the loop → called initializing the variable. Dr.HYA 7 Incrementing or Decrementing The task of incrementing, or counting, is done by adding a constant, such as 1 or 2, to the value of a variable. Example: C must be initialized to zero before C=C+1 starting the loop This instruction enables the programmer to count the number of items, people, temperatures, and so on, as part of the solution to a problem. Decrement example: C=C-1 Dr.HYA 8 Accumulating Summing a group of numbers is a process of accumulating is similar to incrementing, except a variable instead of a constant is added to another variable, which holds the value of the sum or total. The instruction for accumulating is the following: Sum = Sum + Variable or S = S + V For example, the instruction to find total sales would be TotalSales = TotalSales + Sales Sum and TotalSales must be initialized to zero before starting the loop Dr.HYA 9 Accumulating Calculating the product of a series of numbers is similar to finding the sum of a series of numbers with two exceptions. First, the plus sign is replaced by the multiplication sign (*). Second, the product variable must be initialized to 1 instead of 0. For example: Product=1 Product = Product * Number Dr.HYA 10 Types of Loop Structure 1. While/WhileEnd loop 2. Repeat/Until loop 3. Automatic-counter loop Dr.HYA 11 While/WhileEnd This type of loop tells the computer that while the condition is True, repeat all instructions between the While and the WhileEnd. Dr.HYA 12 While/WhileEnd Dr.HYA 13 While/WhileEnd At the beginning of the While/WhileEnd loop, the program processes the condition in order to decide whether to execute the loop instructions. When the resultant of the condition is True, the complete set of instructions will be executed, and then the computer will go back to the beginning of the loop and process the condition again. The loop will repeat until the resultant of the condition is False. Dr.HYA 14 While/WhileEnd Use the While/WhileEnd structure when: you do not know the number of times the instructions will be repeated, or if there are cases when the instructions in the loop should not be processed. Examples of such cases are: when you are entering information on clients and you don’t know the number of clients; when you are finding the total amount of sales for the day and you don’t know the number of sales. Dr.HYA 15 While/WhileEnd Example Problem: Create the algorithm and the flowchart to find the average age of all the students in a class. How many While/WhileEnd students?? Dr.HYA 16 Average Age of a Class Dr.HYA 17 While/WhileEnd An age must be entered before the loop so that the condition has data to use to get a resultant. This is called a primer Read because it gives the While/WhileEnd loop a valid value for the variable Age in order for the conditions to be true the first time through the loop. The last age should be zero. This zero is called a trip value, or a flag. It allows the value of Age to control when to stop the looping process and continue with the rest of the solution. Dr.HYA 18 Types of Loop Structure 1. While/WhileEnd loop 2. Repeat/Until loop 3. Automatic-counter loop Dr.HYA 19 Repeat/Until This type of loop tells the computer to repeat the set of instructions between the Repeat and the Until, until a condition is True. Algorithm Format Dr.HYA 20 Flowchart Diagram of Repeat/Until Dr.HYA 21 While/WhileEnd vs Repeat/Until While/WhileEnd Repeat/Until the program continues to loop as long the program stops the loop process when as the resultant of the condition is the resultant of the condition is True True the condition is processed at the The condition is processed at the end. beginning The instructions in the loop are processed entirely at least once. Dr.HYA 22 Repeat/Until Use the Repeat/Until structure when you do not know the number of times the instructions will be executed, when you know they will be executed at least once, or when you do not know the condition for repeating until after the instructions in the loop are processed. Dr.HYA 23 Repeat/Until loop Average Age of a Class Dr.HYA 24 Types of Loop Structure 1. While/WhileEnd loop 2. Repeat/Until loop 3. Automatic-counter loop Dr.HYA 25 Automatic-Counter Loop This type of loop increments or decrements a variable each time the loop is repeated The programmer uses a variable as a counter that starts counting at a specified number and increments the variable each time the loop is processed. The beginning value, the ending value, and the increment value may be constants, variables, or expressions (calculations). Use it when you know from the start the number of times the loop will be executed. Dr.HYA 26 Automatic-Counter Loop The form of the algorithm for the automatic-counter loop is the following: Dr.HYA 27 Flowchart of Automatic- Counter Loop Counter is the variable used for the counter, Begin is the beginning value, End is the ending value StepValue is the value by which the counter is to be incremented To decrement, StepValue needs to be a negative number and Begin must be greater than End. Dr.HYA 28 Automatic-Counter Loop When incrementing the counter, remember the following rules: 1. When the computer executes the Loop instruction, it sets the counter equal to the beginning number. 2. When the computer executes the Loop-End, it increments the counter. Dr.HYA 29 Automatic-Counter Loop 3. When the counter is less than or equal to the ending number → the processing continues at the instruction that follows the Loop instruction. 4. When the counter is greater than the ending number → Stop Dr.HYA 30 Automatic-Counter Loop When decrementing the counter : The counter is decremented at the end of the loop. When the counter is greater than or equal to the ending value, the loop continues. Step value needs to be a negative number and begin must be greater than end Dr.HYA 31 Automatic-Counter Loop Example Create the algorithm and the flowchart to find the average age of the 12 students in a class. How many Automatic- students?? 12 Counter Loop Dr.HYA 32 Step 1 Step 1 Dr.HYA 33 Automatic-Counter Loop Example The counter begins at 1 and is incremented by 1 until the counter is greater than 12. When the increment value is left out, the computer assumes the value to be 1. When the counter increases to a value greater than 12, the average age is calculated and printed. Also notice the absence of the primer Read. The primer Read is not necessary because there is no trip value needed since the number of students is known. Dr.HYA 34 Decision Equivalents to Automatic-Counter Loop Dr.HYA 35 While/WhileEnd Loop Equivalent of the Automatic-Counter Loop Dr.HYA 36 Nested Loops Loops can be nested like decisions can. Each loop must be nested inside the loop just outside it. Dr.HYA 37 Nested loops Examples Outer loop Inner loop (outer loop (Inner loop counter) counter) 1 1 1 2 1 3 2 1 2 2 2 3 Dr.HYA 38 Nested loops Examples Outer loop Inner loop (outer loop (Inner loop counter) counter) 1 1 1 2 1 3 2 1 2 2 2 3 Dr.HYA 39 Recursion (Extra) Another type of loop structure is recursion. Recursion occurs when a module or a function calls itself. The condition that ends the loop must be within the module. Factorial(N) An example of a recursive function that calculates a factorial number such as 5! (5! = 5 * 4 * 3 * 2 * 1) Notice that Factorial(N) continues to call itself until N=1. There must be a way to stop the recursion. Dr.HYA 40 Recursion example Dr.HYA 41 Recursion example Dr.HYA 42 Execution of a Recursion Problem Dr.HYA 43  End of Lecture 8 (Chapter 7) Dr.HYA 44