15-110: Principles of Computing - Decision Structures Part II Lecture 6, September 18, 2018
Today's session focuses on multi-way decisions in decision structures and revisits a quadratic equation solver in Python. The program encounters a math domain error due to a negative discriminant, preventing computation of square roots for negative numbers. The solution involves checking the discriminant's negativity and handling it accordingly to find real roots.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
15-110: Principles of Computing Decision Structures- Part II Lecture 6, September 18, 2018 Mohammad Hammoud Carnegie Mellon University in Qatar
Today Last Session: Functions- Part II Today s Session: Decision Structures- Part II: Multi-way Decisions A Study on Design Announcement: HA2 will be out by tonight; it is due on September 27 by 10:00AM
Revisiting Our Quadratic Equation Solver #The following line will make the math library in Python available for us. import math def rootsQEq(): print("This program finds the real solutions to a quadratic.") print() a = eval(input("Enter the value of coefficient a: ")) b = eval(input("Enter the value of coefficient b: ")) c = eval(input("Enter the value of coefficient c: "))
Revisiting Our Quadratic Equation Solver #To call a function from the math library, we can use the #dot operator as follows: s_root_val = math.sqrt(b*b - 4 * a * c) root1 = (-b + s_root_val)/(2*a) root2 = (-b - s_root_val)/(2*a) print() print("The solutions are: ", root1, root2) #Call the function rootsQEq() rootsQEq()
Revisiting Our Quadratic Equation Solver A sample run: This program finds the real solutions to a quadratic. Enter the value of coefficient a: 1 Enter the value of coefficient b: 2 Enter the value of coefficient c: 3 Traceback (most recent call last): File "/Users/mhhammou/Desktop/CMU-Q/Courses/15- 110/Programs/Lecture4/RootsQE.py", line 22, in <module> rootsQEq() File "/Users/mhhammou/Desktop/CMU-Q/Courses/15- 110/Programs/Lecture4/RootsQE.py", line 14, in rootsQEq s_root_val = math.sqrt(b*b - 4 * a * c) ValueError: math domain error What is the problem?
Revisiting Our Quadratic Equation Solver The problem is that the discriminant?2 4?? < 0 The sqrt function is unable to compute the square root of a negative number How can we avoid this problem? We can first compute the discriminant ?2 4?? < 0 Then, we can check if it is negative (via using the if statement) If it is negative, we can print out that the equation has no real roots Otherwise (via using the else clause), we can compute the solutions and print them out
A Refined Quadratic Equation Solver import math def rootsQEq(): print("This program finds the real solutions to a quadratic.") print() a = eval(input("Enter the value of coefficient a: ")) b = eval(input("Enter the value of coefficient b: ")) c = eval(input("Enter the value of coefficient c: ")) discriminant = b * b 4 * a * c
A Refined Quadratic Equation Solver if discriminant < 0: print( The equation has no real roots! ) else: s_root_val = math.sqrt(discriminant) root1 = (-b + s_root_val)/(2*a) root2 = (-b - s_root_val)/(2*a) print( \nThe solutions are: ", root1, root2) rootsQEq()
Revisiting Our Quadratic Equation Solver A sample run: This program finds the real solutions to a quadratic. Enter the value of coefficient a: 1 Enter the value of coefficient b: 2 Enter the value of coefficient c: 3 The equation has no real roots!
Good, But This new version of the quadratic solver is certainly a big improvement, but it still has some quirks! Let us illustrate that through examples: This program finds the real solutions to a quadratic. Enter the value of coefficient a: 1 Enter the value of coefficient b: 2 Enter the value of coefficient c: 1 A double root at -1.0; printed twice, thus might seem confusing to some people (a styling issue)! The solutions are: -1.0 -1.0
Good, But Another sample run: This program finds the real solutions to a quadratic. Enter the value of coefficient a: 0 Enter the value of coefficient b: 2 Enter the value of coefficient c: 1 Traceback (most recent call last): File "/Users/mhhammou/Desktop/CMU-Q/Courses/15- 110/Programs/Lecture4/RootsQE.py", line 27, in <module> rootsQEq() File "/Users/mhhammou/Desktop/CMU-Q/Courses/15- 110/Programs/Lecture4/RootsQE.py", line 22, in rootsQEq root1 = (-b + s_root_val)/(2*a) ZeroDivisionError: float division by zero Coefficient a CANNOT be zero since we cannot divide by zero (a serious issue)!
The Need for a Three-Way Decision Let us start with the double-root situation, which occurs when the discriminant is exactly 0 If we want to catch this special case, our quadratic equation solver needs a three-way decision Here is a quick sketch of what we need: Check the value of the discriminant when < 0: handle the case of no roots when = 0: handle the case of a double root when > 0: handle the case of two distinct roots
A Three-Way Decision Via Two if-else Statements One way to code this algorithm is to use two if-else statements if discriminant < 0: print( Equation has no real roots ) else: if discriminant == 0: root = -b / (2 * a) print( There is a double root at , root) else: #Do stuff for two roots
Digging Deeper If we trace this code carefully, we will observe that there are exactly three possible paths Yes No Discriminant < 0 ? Yes No Print no roots Discriminant == 0 ? Do Unique Roots Do Double Roots
Multi-Way Decisions We managed to finesse a 3-way decision by using 2 2-way decisions What happens if we needed to make a 5-way decision using this technique? The if-else structures would nest four levels deep, and the Python code would march off the right-hand edge of the page Is there any other way in Python to write multi-way decisions? Yes, by using if-elif-else statements
Multi-Way Decisions Here is how the if-elif-else form looks like: if <condition1>: <case1 statements> elif <condition2>: <case2 statements> elif <condition3>: <case3 statements> else: <default statements> The else clause is optional; if omitted, it is possible that no indented statement block will be executed!
Revisiting Our Quadratic Equation Solver import math def rootsQEq(): print("This program finds the real solutions to a quadratic.") print() a, b, c = eval(input("Please enter the coefficients (a, b, c): ")) discriminant = b * b 4 * a * c
Revisiting Our Quadratic Equation Solver if discriminant < 0: print("The equation has no real roots!") elif discriminant == 0: root = -b/(2*a) print("\nThere is a double root at", root) else: s_root_val = math.sqrt(discriminant) root1 = (-b + s_root_val)/(2*a) root2 = (-b - s_root_val)/(2*a) print("\nThe solutions are: ", root1, root2) rootsQEq()
Three Sample Runs This program finds the real solutions to a quadratic. When discriminant < 0 Please enter the coefficients (a, b, c): 1, 2, 3 The equation has no real roots! This program finds the real solutions to a quadratic. When discriminant == 0 Please enter the coefficients (a, b, c): 1, 2, 1 There is a double root at -1.0 This program finds the real solutions to a quadratic. When discriminant < 0 Please enter the coefficients (a, b, c): 3, 4, -2 The solutions are: 0.38742588672279316 -1.7207592200561266
Avoid Dividing By Zero Let us now handle the case of avoiding a division by zero import math def rootsQEq(): print("This program finds the real solutions to a quadratic.") print() a, b, c = eval(input("Please enter the coefficients (a, b, c): ")) discriminant = b * b 4 * a * c if a == 0: print("Cannot divide by zero")
Avoid Dividing By Zero Let us now handle the case of avoiding a division by zero elif discriminant < 0: print("The equation has no real roots!") elif discriminant == 0: root = -b/(2*a) print("\nThere is a double root at", root) else: s_root_val = math.sqrt(discriminant) root1 = (-b + s_root_val)/(2*a) root2 = (-b - s_root_val)/(2*a) print("\nThe solutions are: ", root1, root2) rootsQEq()
Avoid Dividing By Zero Let us try to divide by zero: This program finds the real solutions to a quadratic. Please enter the coefficients (a, b, c): 0, 1, 2 Cannot divide by zero
Study in Design: Max of Three Numbers (v1) def main(): x1, x2, x3 = eval(input("Please enter three values: ")) if x1 >= x2 and x1 >= x3: max = x1 elif x2 > x1 and x2 > x3: max = x2 else: max = x3 Difficult to scale the program to more numbers (say, 10, 100, or even more) i.e., following this strategy will make the code very long, complex, and prone to errors! This program uses a strategy that can be referred to as compare each to all print("The largest value is", max) main()
Study in Design: Max of Three Numbers (v2) def main(): x1, x2, x3 = eval(input("Please enter three values: ")) if x1 >= x2: if x1 >= x3: max = x1 else: max = x3 else: if x2 >= x3: max = x2 else: max = x3 This program uses a strategy that can be referred to as decision tree print("The largest value is", max) main()
Study in Design: Max of Three Numbers (v2) Yes No x1 >= x2 Yes No Yes No X1 >= x3 X2 >= x3 max = x1 max = x3 max = x2 max = x3 Still, this strategy (i.e., decision tree) makes it very difficult to scale the program to more numbers (say, 10, 100, or even more)!
Study in Design: Max of Three Numbers (v3) def main(): x1, x2, x3 = eval(input("Please enter three values: ")) max = x1 if x2 > max: max = x2 if x3 > max: max = x3 This program uses a strategy that can be referred to as sequential processing print("The largest value is", max) main()
Study in Design: Max of Three Numbers (v3) Interestingly, this version (i.e., v3) of the program allows us to scale to larger problems In particular, we can easily write a program that computes the largest of n numbers by folding our algorithm into a loop A loop is a device that tells a program to do the same thing over and over again! (more on this next lecture) for i in range(10): print( Hello ) This will print Hello ten times!
Study in Design: Max of Three Numbers (v3) def main(): n = eval(input("How many numbers are there? ")) #set max to be the first value; we can involve conditions here to #ensure that n is greater than or equal to 1 max = eval(input("Enter a number >> ")) #Now compare the n-1 successive values for i in range(n-1): x = eval(input("Enter a number >> ")) if x > max: max = x This is a more general solution! print("The largest value is", max) main()
Study in Design: Max of Three Numbers (v4) We can even go green! def main(): x1, x2, x3 = eval(input("Please enter three values: ")) print("The largest value is", max(x1, x2, x3)) This program uses a strategy that can be referred to as use Python ! main()
Study in Design: Lessons Learned There is typically more than 1 way to solve a problem! Do not rush to code up the first idea that pops into your head; rather, think about your design and ask yourself if there is a better way to solve the problem Generality is good we arrived at the best solution to the max of three problem by considering the more general max of n numbers problem Do not reinvent the wheel you can use Python s existing libraries!
Summary Decision structures are control structures that allow a program to execute different sequences of instructions for different cases Decisions are implemented in Python as follows: A simple decision with 1 condition (i.e., one-way decision) can be implemented with 1 if clause A decision with 2 conditions (i.e., two-way decision) can be implemented with 1 if and 1 else (i.e., if-else) clauses A decision with 3 or more conditions (i.e., multi-way decision) can be implemented with 3 or more if-elif-else clauses E.g., for 3-way, you can use 1 if, 1 elif, and 1 else E.g., for 4-way, you can use 1 if, 2 elifs, and 1 else E.g., for n-way, you can use 1 if, n elifs, and 1 else
Summary Decisions are based on the evaluations of conditions, which are simple Boolean expressions that can be constructed using different kinds of operators (e.g., relational, logical, membership, and identity operators) A Boolean expression is either True or False Algorithms that incorporate decisions can become quite complicated as decision structures are nested Usually a number of solutions are possible, and careful thought should be given to produce correct, efficient, and understandable programs
Next Lecture Loop Structures- Part I
