10 CHAPTER 1.COMPUTERS AND PROGRAMS print x ×=3.9*x*(1-) print x Obviously using the loop instead saves the programmer a lot of trouble. But what exactly do these statements do?The first one performs a calculation. x=3.9*×*(1-) This is called an assignment statement.The part on the right side of the =is a mathematical expression. Python uses the character to indicate multiplication.Recall that the value of x is 0.25(from the input statement).The computed value is 3.9(0.25)(1-0.25)or 0.73125.Once the value on the righthand side is computed,it is stored back(or assigned)into the variable that appears on the lefthand side of the =in this case x.The new value of x(0.73125)replaces the old value (0.25). The second line in the loop body is a type of statement we have encountered before,a print statement. print x When Python executes this statement the current value of x is displayed on the screen.So,the first number of output is 0.73125. Remember the loop executes 10 times.After printing the value of x,the two statements of the loop are executed again x=3.9*x*(1-x) print x Of course,now x has the value 0.73125,so the formula computes a new value of x as 3.9(0.73125)(1- 0.73125).which is0.76644140625. Can you see how the current value ofx is used to compute a new value each time around the loop?That's where the numbers in the example run came from.You might try working through the steps of the program yourself for a different input value(say 0.5).Then run the program using Python and see how well you did impersonating a computer. 1.8 Chaos and Computers I said above that the chaos program illustrates an interesting phenomenon.What could be interesting about a screen full of numbers?If you try out the program for yourself,you'll find that,no matter what number you start with,the results are always similar:the program spits back 10 seemingly random numbers between 0 and 1.As the program runs,the value ofx seems to jump around,well,chaotically. The function computed by this program has the general form:k(x)(1-x),where k in this case is 3.9. This is called a logistic function.It models certain kinds of unstable electronic circuits and is also sometimes used to predict population under limiting conditions.Repeated application of the logistic function can pro- duce chaos.Although our program has a well defined underlying behavior,the output seems unpredictable. An interesting property of chaotic functions is that very small differences in the initial value can lead to large differences in the result as the formula is repeatedly applied.You can see this in the chaos program by entering numbers that differ by only a small amount.Here is the output from a modified program that shows the results for initial values of 0.25 and 0.26 side by side. input 0.25 0.26 0.731250 0.750360 0.766441 0.730547 0.698135 0.767707 0.821896 0.695499 0.570894 0.825942 0.955399 0.560671
10 CHAPTER 1. COMPUTERS AND PROGRAMS print x x = 3.9 * x * (1 - x) print x Obviously using the loop instead saves the programmer a lot of trouble. But what exactly do these statements do? The first one performs a calculation. x = 3.9 * x * (1 - x) This is called an assignment statement. The part on the right side of the = is a mathematical expression. Python uses the * character to indicate multiplication. Recall that the value of x is 0 25 (from the input statement). The computed value is 3 9 0 25✁ 1 ✂ 0 25✁ or 0 73125. Once the value on the righthand side is computed, it is stored back (or assigned) into the variable that appears on the lefthand side of the =, in this case x. The new value of x (0 73125) replaces the old value (0 25). The second line in the loop body is a type of statement we have encountered before, a print statement. print x When Python executes this statement the current value of x is displayed on the screen. So, the first number of output is 0.73125. Remember the loop executes 10 times. After printing the value of x, the two statements of the loop are executed again. x = 3.9 * x * (1 - x) print x Of course, now x has the value 0 73125, so the formula computes a new value of x as 3 9 0 73125 ✁ 1 ✂ 0 73125✁ , which is 0 76644140625. Can you see how the current value of x is used to compute a new value each time around the loop? That’s where the numbers in the example run came from. You might try working through the steps of the program yourself for a different input value (say 0 5). Then run the program using Python and see how well you did impersonating a computer. 1.8 Chaos and Computers I said above that the chaos program illustrates an interesting phenomenon. What could be interesting about a screen full of numbers? If you try out the program for yourself, you’ll find that, no matter what number you start with, the results are always similar: the program spits back 10 seemingly random numbers between 0 and 1. As the program runs, the value of x seems to jump around, well, chaotically. The function computed by this program has the general form: k x ✁ 1 ✂ x✁ , where k in this case is 3.9. This is called a logistic function. It models certain kinds of unstable electronic circuits and is also sometimes used to predict population under limiting conditions. Repeated application of the logistic function can produce chaos. Although our program has a well defined underlying behavior, the output seems unpredictable. An interesting property of chaotic functions is that very small differences in the initial value can lead to large differences in the result as the formula is repeatedly applied. You can see this in the chaos program by entering numbers that differ by only a small amount. Here is the output from a modified program that shows the results for initial values of 0 25 and 0 26 side by side. input 0.25 0.26 --------------------------- 0.731250 0.750360 0.766441 0.730547 0.698135 0.767707 0.821896 0.695499 0.570894 0.825942 0.955399 0.560671
1.9.EXERCISES 11 0.166187 0.960644 0.540418 0.147447 0.968629 0.490255 0.118509 0.974630 With very similar starting values,the outputs stay similar for a few iterations,but then differ markedly.By about the fifth iteration,there no longer seems to be any relationship between the two models. These two features of our chaos program,apparent unpredictability and extreme sensitivity to initial values,are the hallmarks of chaotic behavior.Chaos has important implications for computer science.It turns out that many phenomena in the real world that we might like to model and predict with our computers exhibit just this kind of chaotic behavior.You may have heard of the so-called butterfly effect.Computer models that are used to simulate and predict weather patterns are so sensitive that the effect of a single butterfly flapping its wings in New Jersey might make the difference of whether or not rain is predicted in Peoria. It's very possible that even with perfect computer modeling,we might never be able to measure existing weather conditions accurately enough to predict weather more than a few days in advance.The measurements simply can't be precise enough to make the predictions accurate over a longer time frame. As you can see,this small program has a valuable lesson to teach users of computers.As amazing as computers are,the results that they give us are only as useful as the mathematical models on which the programs are based.Computers can give incorrect results because of errors in programs,but even correct programs may produce erroneous results if the models are wrong or the initial inputs are not accurate enough. 1.9 Exercises 1.Compare and contrast the following pairs of concepts from the chapter. (a)Hardware vs.Software (b)Algorithm vs.Program (c)Programming Language vs.Natural Language (d)High-Level Language vs.Machine Language (e)Interpreter vs.Compiler (f)Syntax vs.Semantics 2.List and explain in your own words the role of each of the five basic functional units of a computer depicted in Figure 1.1. 3.Write a detailed algorithm for making a peanut butter and jelly sandwich(or some other simple every- day activity) 4.As you will learn in a later chapter,many of the numbers stored in a computer are not exact values,but rather close approximations.For example,the value 0.1,might be stored as 0.10000000000000000555. Usually,such small differences are not a problem;however,given what you have learned about chaotic behavior in Chapter 1,you should realize the need for caution in certain situations.Can you think of examples where this might be a problem?Explain. 5.Trace through the Chaos program from Section 1.6 by hand using 0.15 as the input value.Show the sequence of output that results. 6.Enter and run the Chaos program from Section 1.6 using whatever Python implementation you have available.Try it out with various values of input to see that it functions as described in the chapter. 7.Modify the Chaos program from Section 1.6 using 2.0 in place of 3.9 as the multiplier in the logistic function.Your modified line of code should look like this:
1.9. EXERCISES 11 0.166187 0.960644 0.540418 0.147447 0.968629 0.490255 0.118509 0.974630 With very similar starting values, the outputs stay similar for a few iterations, but then differ markedly. By about the fifth iteration, there no longer seems to be any relationship between the two models. These two features of our chaos program, apparent unpredictability and extreme sensitivity to initial values, are the hallmarks of chaotic behavior. Chaos has important implications for computer science. It turns out that many phenomena in the real world that we might like to model and predict with our computers exhibit just this kind of chaotic behavior. You may have heard of the so-called butterfly effect. Computer models that are used to simulate and predict weather patterns are so sensitive that the effect of a single butterfly flapping its wings in New Jersey might make the difference of whether or not rain is predicted in Peoria. It’s very possible that even with perfect computer modeling, we might never be able to measure existing weather conditions accurately enough to predict weather more than a few days in advance. The measurements simply can’t be precise enough to make the predictions accurate over a longer time frame. As you can see, this small program has a valuable lesson to teach users of computers. As amazing as computers are, the results that they give us are only as useful as the mathematical models on which the programs are based. Computers can give incorrect results because of errors in programs, but even correct programs may produce erroneousresults if the models are wrong or the initial inputs are not accurate enough. 1.9 Exercises 1. Compare and contrast the following pairs of concepts from the chapter. (a) Hardware vs. Software (b) Algorithm vs. Program (c) Programming Language vs. Natural Language (d) High-Level Language vs. Machine Language (e) Interpreter vs. Compiler (f) Syntax vs. Semantics 2. List and explain in your own words the role of each of the five basic functional units of a computer depicted in Figure 1.1. 3. Write a detailed algorithm for making a peanut butter and jelly sandwich (or some other simple everyday activity). 4. As you will learn in a later chapter, many of the numbers stored in a computer are not exact values, but rather close approximations. For example, the value 0.1, might be stored as 0.10000000000000000555. Usually, such small differences are not a problem; however, given what you have learned about chaotic behavior in Chapter 1, you should realize the need for caution in certain situations. Can you think of examples where this might be a problem? Explain. 5. Trace through the Chaos program from Section 1.6 by hand using 0 15 as the input value. Show the sequence of output that results. 6. Enter and run the Chaos program from Section 1.6 using whatever Python implementation you have available. Try it out with various values of input to see that it functions as described in the chapter. 7. Modify the Chaos program from Section 1.6 using 2.0 in place of 3.9 as the multiplier in the logistic function. Your modified line of code should look like this:
12 CHAPTER 1.COMPUTERS AND PROGRAMS ×=2.0*8*(1-) Run the program for various input values and compare the results to those obtained from the original program.Write a short paragraph describing any differences that you notice in the behavior of the two versions. 8.Modify the Chaos program from Section 1.6 so that it prints out 20 values instead of 10 9.(Advanced)Modify the Chaos program so that it accepts two inputs and then prints a table with two columns similar to the one shown in Section 1.8.(Note:You will probably not be able to get the columns to line up as nicely as those in the example.Chapter 4 discusses how to print numbers with a fixed number of decimal places
12 CHAPTER 1. COMPUTERS AND PROGRAMS x = 2.0 * x * (1 - x) Run the program for various input values and compare the results to those obtained from the original program. Write a short paragraph describing any differences that you notice in the behavior of the two versions. 8. Modify the Chaos program from Section 1.6 so that it prints out 20 values instead of 10. 9. (Advanced) Modify the Chaos program so that it accepts two inputs and then prints a table with two columns similar to the one shown in Section 1.8. (Note: You will probably not be able to get the columns to line up as nicely as those in the example. Chapter 4 discusses how to print numbers with a fixed number of decimal places.)
Chapter 2 Writing Simple Programs As you saw in the previous chapter,it is easy to run programs that have already been written.The hard part is actually coming up with the program in the first place.Computers are very literal,and they must be told what to do right down to the last detail.Writing large programs is a daunting task.It would be almost impossible without a systematic approach. 2.1 The Software Development Process The process of creating a program is often broken down into stages according to the information that is produced in each phase.In a nutshell,here's what you should do. Formulate Requirements Figure out exactly what the problem to be solved is.Try to understand as much as possible about it.Until you really know what the problem is,you cannot begin to solve it. Determine Specifications Describe exactly what your program will do.At this point,you should not worry about how your program will work,but rather with deciding exactly what it will accomplish.For simple programs this involves carefully describing what the inputs and outputs of the program will be and how they relate to each other. Create a Design Formulate the overall structure of the program.This is where the how of the program gets worked out.The main task is to design the algorithm(s)that will meet the specifications. Implement the Design Translate the design into a computer language and put it into the computer.In this book,we will be implementing our algorithms as Python programs. Test/Debug the Program Try out your program and see if it works as expected.If there are any errors(often called bugs),then you should go back and fix them.The process of locating and fixing errors is called debugging a program. Maintain the Program Continue developing the program in response to the needs of your users.Most programs are never really finished;they keep evolving over years of use. 2.2 Example Program:Temperature Converter Let's go through the steps of the software development process with a simple real-world example.Suzie Programmer has a problem.Suzie is an American computer science student spending a year studying in Europe.She has no problems with language,as she is fluent in many languages(including Python).Her problem is that she has a hard time figuring out the temperature in the morning so that she knows how to dress for the day.Suzie listens to the weather report each morning,but the temperatures are given in degrees Celsius,and she is used to Fahrenheit. 13
Chapter 2 Writing Simple Programs As you saw in the previous chapter, it is easy to run programs that have already been written. The hard part is actually coming up with the program in the first place. Computers are very literal, and they must be told what to do right down to the last detail. Writing large programs is a daunting task. It would be almost impossible without a systematic approach. 2.1 The Software Development Process The process of creating a program is often broken down into stages according to the information that is produced in each phase. In a nutshell, here’s what you should do. Formulate Requirements Figure out exactly what the problem to be solved is. Try to understand as much as possible about it. Until you really know what the problem is, you cannot begin to solve it. Determine Specifications Describe exactly what your program will do. At this point, you should not worry about how your program will work, but rather with deciding exactly what it will accomplish. For simple programs this involves carefully describing what the inputs and outputs of the program will be and how they relate to each other. Create a Design Formulate the overall structure of the program. This is where the how of the program gets worked out. The main task is to design the algorithm(s) that will meet the specifications. Implement the Design Translate the design into a computer language and put it into the computer. In this book, we will be implementing our algorithms as Python programs. Test/Debug the Program Try out your program and see if it works as expected. If there are any errors (often called bugs), then you should go back and fix them. The process of locating and fixing errors is called debugging a program. Maintain the Program Continue developing the program in response to the needs of your users. Most programs are never really finished; they keep evolving over years of use. 2.2 Example Program: Temperature Converter Let’s go through the steps of the software development process with a simple real-world example. Suzie Programmer has a problem. Suzie is an American computer science student spending a year studying in Europe. She has no problems with language, as she is fluent in many languages (including Python). Her problem is that she has a hard time figuring out the temperature in the morning so that she knows how to dress for the day. Suzie listens to the weather report each morning, but the temperatures are given in degrees Celsius, and she is used to Fahrenheit. 13
14 CHAPTER 2.WRITING SIMPLE PROGRAMS Fortunately,Suzie has an idea to solve the problem.Being a computer science major,she never goes anywhere without her laptop computer.She thinks it might be possible that a computer program could help her out. Suzie begins with the requirements of her problem.In this case,the problem is pretty clear:the radio an- nouncer gives temperatures in degrees Celsius,but Suzie only comprehends temperatures that are in degrees Fahrenheit.That's the crux of the problem. Next,Suzie considers the specifications of a program that might help her out.What should the input be?She decides that her program will allow her to type in the temperature in degrees Celsius.And the output?The program will display the temperature converted into degrees Fahrenheit.Now she needs to specify the exact relationship of the output to the input.Suzie does some quick figuring to derive the formula F=(9/5)C+32(Can you see how?).That seems an adequate specification. Notice that this describes one of many possible programs that could solve this problem.If Suzie had background in the field of Artificial Intelligence (Al),she might consider writing a program that would actually listen to the radio announcer to get the current temperature using speech recognition algorithms.For output,she might have the computer control a robot that goes to her closet and picks an appropriate outfit based on the converted temperature.This would be a much more ambitious project,to say the least! Certainly the robot program would also solve the problem identified in the requirements.The purpose of specification is to decide exactly what this particular program will do to solve a problem.Suzie knows better than to just dive in and start writing a program without first having a clear idea of what she is trying to build. Suzie is now ready to design an algorithm for her problem.She immediately realizes that this is a simple algorithm that follows a standard pattern:Input,Process,Output (IPO).Her program will prompt the user for some input information(the Celsius temperature),process it to convert to a Fahrenheit temperature,and then output the result by displaying it on the computer screen. Suzie could write her algorithm down in a computer language.However,the precision of writing it out formally tends to stifle the creative process of developing the algorithm.Instead,she writes her algorithm using pseudocode.Pseudocode is just precise English that describes what a program does.It is meant to communicate algorithms without all the extra mental overhead of getting the details right in any particular programming language. Here is Suzie's completed algorithm: Input the temperature in degrees Celsius (call it celsius) Calculate fahrenheit as 9/5 celsius 32 Output fahrenheit The next step is to translate this design into a Python program.This is straightforward,as each line of the algorithm turns into a corresponding line of Python code. convert.py A program to convert Celsius temps to Fahrenheit by:Suzie Programmer def main(): celsius input("What is the Celsius temperature?" fahrenheit =9.0/5.0 celsius 32 print "The temperature is",fahrenheit,"degrees Fahrenheit." main() See if you can figure out what each line of this program does.Don't worry if some parts are a bit confusing. They will be discussed in detail in the next section. After completing her program,Suzie tests it to see how well it works.She uses some inputs for which she knows the correct answers.Here is the output from two of her tests. What is the Celsius temperature?0 The temperature is 32.0 degrees fahrenheit
14 CHAPTER 2. WRITING SIMPLE PROGRAMS Fortunately, Suzie has an idea to solve the problem. Being a computer science major, she never goes anywhere without her laptop computer. She thinks it might be possible that a computer program could help her out. Suzie begins with the requirements of her problem. In this case, the problem is pretty clear: the radio announcer gives temperatures in degrees Celsius, but Suzie only comprehends temperatures that are in degrees Fahrenheit. That’s the crux of the problem. Next, Suzie considers the specifications of a program that might help her out. What should the input be? She decides that her program will allow her to type in the temperature in degrees Celsius. And the output? The program will display the temperature converted into degrees Fahrenheit. Now she needs to specify the exact relationship of the output to the input. Suzie does some quick figuring to derive the formula F 9✁ 5✁ C ✂ 32 (Can you see how?). That seems an adequate specification. Notice that this describes one of many possible programs that could solve this problem. If Suzie had background in the field of Artificial Intelligence (AI), she might consider writing a program that would actually listen to the radio announcer to get the current temperature using speech recognition algorithms. For output, she might have the computer control a robot that goes to her closet and picks an appropriate outfit based on the converted temperature. This would be a much more ambitious project, to say the least! Certainly the robot program would also solve the problem identified in the requirements. The purpose of specification is to decide exactly what this particular program will do to solve a problem. Suzie knows better than to just dive in and start writing a program without first having a clear idea of what she is trying to build. Suzie is now ready to design an algorithm for her problem. She immediately realizes that this is a simple algorithm that follows a standard pattern: Input, Process, Output (IPO). Her program will prompt the user for some input information (the Celsius temperature), process it to convert to a Fahrenheit temperature, and then output the result by displaying it on the computer screen. Suzie could write her algorithm down in a computer language. However, the precision of writing it out formally tends to stifle the creative process of developing the algorithm. Instead, she writes her algorithm using pseudocode. Pseudocode is just precise English that describes what a program does. It is meant to communicate algorithms without all the extra mental overhead of getting the details right in any particular programming language. Here is Suzie’s completed algorithm: Input the temperature in degrees Celsius (call it celsius) Calculate fahrenheit as 9/5 celsius + 32 Output fahrenheit The next step is to translate this design into a Python program. This is straightforward, as each line of the algorithm turns into a corresponding line of Python code. # convert.py # A program to convert Celsius temps to Fahrenheit # by: Suzie Programmer def main(): celsius = input("What is the Celsius temperature? ") fahrenheit = 9.0 / 5.0 * celsius + 32 print "The temperature is", fahrenheit, "degrees Fahrenheit." main() See if you can figure out what each line of this program does. Don’t worry if some parts are a bit confusing. They will be discussed in detail in the next section. After completing her program, Suzie tests it to see how well it works. She uses some inputs for which she knows the correct answers. Here is the output from two of her tests. What is the Celsius temperature? 0 The temperature is 32.0 degrees fahrenheit