Python Programming: An Introduction to Computer Science John M. Zelle, Ph.D. Version 1.0rc2 Fall 2002
Copyright c 2002 by John M. Zelle
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without prior written permission of the author.
This document was prepared with LATEX 2ε and reproduced by Wartburg College Printing Services.
Contents 1 Computers and Programs 1.1 The Universal Machine . . . 1.2 Program Power . . . . . . . 1.3 What is Computer Science? . 1.4 Hardware Basics . . . . . . 1.5 Programming Languages . . 1.6 The Magic of Python . . . . 1.7 Inside a Python Program . . 1.8 Chaos and Computers . . . . 1.9 Exercises . . . . . . . . . .
CONTENTS 13.3.3 Comparing Sorts . . 13.4 Hard Problems . . . . . . . 13.4.1 Towers of Hanoi . . 13.4.2 The Halting Problem 13.4.3 Conclusion . . . . .
v . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
234 235 236 239 241
Computers and Programs Almost everyone has used a computer at one time or another. Perhaps you have played computer games or used a computer to write a paper or balance your checkbook. Computers are used to predict the weather, design airplanes, make movies, run businesses, perform financial transactions, and control factories. Have you ever stopped to wonder what exactly a computer is? How can one device perform so many different tasks? These basic questions are the starting point for learning about computers and computer programming.
1.1 The Universal Machine A modern computer might be defined as “a machine that stores and manipulates information under the control of a changeable program.” There are two key elements to this definition. The first is that computers are devices for manipulating information. This means that we can put information into a computer, and it can transform the information into new, useful forms, and then output or display the information for our interpretation. Computers are not the only machines that manipulate information. When you use a simple calculator to add up a column of numbers, you are entering information (the numbers) and the calculator is processing the information to compute a running sum which is then displayed. Another simple example is a gas pump. As you fill your tank, the pump uses certain inputs: the current price of gas per gallon and signals from a sensor that reads the rate of gas flowing into your car. The pump transforms this input into information about how much gas you took and how much money you owe. We would not consider either the calculator or the gas pump as full-fledged computers, although modern versions of these devices may actually contain embedded computers. They are different from computers in that they are built to perform a single, specific task. This is where the second part of our definition comes into the picture: computers operate under the control of a changeable program. What exactly does this mean? A computer program is a detailed, step-by-step set of instructions telling a computer exactly what to do. If we change the program, then the computer performs a different sequence of actions, and hence, performs a different task. It is this flexibility that allows your PC to be at one moment a word processor, at the next moment a financial planner, and later on, an arcade game. The machine stays the same, but the program controlling the machine changes. Every computer is just a machine for executing (carrying out) programs. There are many different kinds of computers. You might be familiar with Macintoshes and PCs, but there are literally thousands of other kinds of computers both real and theoretical. One of the remarkable discoveries of computer science is the realization that all of these different computers have the same power; with suitable programming, each computer can basically do all the things that any other computer can do. In this sense, the PC that you might have sitting on your desk is really a universal machine. It can do anything you want it to, provided you can describe the task to be accomplished in sufficient detail. Now that’s a powerful machine! 1
CHAPTER 1. COMPUTERS AND PROGRAMS
1.2 Program Power You have already learned an important lesson of computing: Software (programs) rules the hardware (the physical machine). It is the software that determines what any computer can do. Without programs, computers would just be expensive paperweights. The process of creating software is called programming, and that is the main focus of this book. Computer programming is a challenging activity. Good programming requires an ability to see the big picture while paying attention to minute detail. Not everyone has the talent to become a first-class programmer, just as not everyone has the skills to be a professional athlete. However, virtually anyone can learn how to program computers. With some patience and effort on your part, this book will help you to become a programmer. There are lots of good reasons to learn programming. Programming is a fundamental part of computer science and is, therefore, important to anyone interested in becoming a computer professional. But others can also benefit from the experience. Computers have become a commonplace tool in our society. Understanding the strengths and limitations of this tool requires an understanding of programming. Non-programmers often feel they are slaves of their computers. Programmers, however, are truly the masters. If you want to become a more intelligent user of computers, then this book is for you. Programming can also be loads of fun. It is an intellectually engaging activity that allows people to express themselves through useful and sometimes remarkably beautiful creations. Believe it or not, many people actually write computer programs as a hobby. Programming also develops valuable problem-solving skills, especially the ability to analyze complex systems by reducing them to interactions of understandable subsystems. As you probably know, programmers are in great demand. More than a few liberal arts majors have turned a couple computer programming classes into a lucrative career option. Computers are so commonplace in the business world today that the ability to understand and program computers might just give you the edge over your competition, regardless of your occupation.
1.3 What is Computer Science? You might be surprised to learn that computer science is not the study of computers. A famous computer scientist named Edsgar Dijkstra once quipped that computers are to computer science what telescopes are to astronomy. The computer is an important tool in computer science, but it is not itself the object of study. Since a computer can carry out any process that we can describe, the real question is What processes can we describe? Put another way, the fundamental question of computer science is simply What can be computed? Computer scientists use numerous techniques of investigation to answer this question. The three main ones are design, analysis, and experimentation. One way to demonstrate that a particular problem can be solved is to actually design a solution. That is, we develop a step-by-step process for achieving the desired result. Computer scientists call this an algorithm. That’s a fancy word that basically means “recipe.” The design of algorithms is one of the most important facets of computer science. In this book you will find techniques for designing and implementing algorithms. One weakness of design is that it can only answer the question What is computable? in the positive. If I can devise an algorithm, then the problem is solvable. However, failing to find an algorithm does not mean that a problem is unsolvable. It may mean that I’m just not smart enough, or I haven’t hit upon the right idea yet. This is where analysis comes in. Analysis is the process of examining algorithms and problems mathematically. Computer scientists have shown that some seemingly simple problems are not solvable by any algorithm. Other problems are intractable. The algorithms that solve these problems take too long or require too much memory to be of practical value. Analysis of algorithms is an important part of computer science; throughout this book we will touch on some of the fundamental principles. Chapter 13 has examples of unsolvable and intractable problems. Some problems are too complex or ill-defined to lend themselves to analysis. In such cases, computer scientists rely on experimentation; they actually implement systems and then study the resulting behavior. Even when theoretical analysis is done, experimentation is often needed in order to verify and refine the
1.4. HARDWARE BASICS
Output Devices CPU Input Devices
Figure 1.1: Functional View of a Computer.
analysis. For most problems, the bottom-line is whether a working, reliable system can be built. Often we require empirical testing of the system to determine that this bottom-line has been met. As you begin writing your own programs, you will get plenty of opportunities to observe your solutions in action.
1.4 Hardware Basics You don’t have to know all the details of how a computer works to be a successful programmer, but understanding the underlying principles will help you master the steps we go through to put our programs into action. It’s a bit like driving a car. Knowing a little about internal combustion engines helps to explain why you have to do things like fill the gas tank, start the engine, step on the accelerator, etc. You could learn to drive by just memorizing what to do, but a little more knowledge makes the whole process much more understandable. Let’s take a moment to “look under the hood” of your computer. Although different computers can vary significantly in specific details, at a higher level all modern digital computers are remarkably similar. Figure 1.1 shows a functional view of a computer. The central processing unit (CPU) is the “brain” of the machine. This is where all the basic operations of the computer are carried out. The CPU can perform simple arithmetic operations like adding two numbers and can also do logical operations like testing to see if two numbers are equal. The memory stores programs and data. The CPU can only directly access information that is stored in main memory (called RAM for Random Access Memory). Main memory is fast, but it is also volatile. That is, when the power is turned off, the information in the memory is lost. Thus, there must also be some secondary memory that provides more permanent storage. In a modern personal computer, this is usually some sort of magnetic medium such as a hard disk (also called a hard drive) or floppy. Humans interact with the computer through input and output devices. You are probably familiar with common devices such as a keyboard, mouse, and monitor (video screen). Information from input devices is processed by the CPU and may be shuffled off to the main or secondary memory. Similarly, when information needs to be displayed, the CPU sends it to one or more output devices. So what happens when you fire up your favorite game or word processing program? First, the instructions that comprise the program are copied from the (more) permanent secondary memory into the main memory of the computer. Once the instructions are loaded, the CPU starts executing the program. Technically the CPU follows a process called the fetch execute cycle. The first instruction is retrieved from memory, decoded to figure out what it represents, and the appropriate action carried out. Then the next instruction is fetched, decoded and executed. The cycle continues, instruction after instruction. This is really all the computer does from the time that you turn it on until you turn it off again: fetch, decode, execute. It doesn’t seem very exciting, does it? But the computer can execute this stream of simple instructions with blazing speed, zipping through millions of instructions each second. Put enough simple instructions together in just the right way, and the computer does amazing things.
CHAPTER 1. COMPUTERS AND PROGRAMS
1.5 Programming Languages Remember that a program is just a sequence of instructions telling a computer what to do. Obviously, we need to provide those instructions in a language that a computer can understand. It would be nice if we could just tell a computer what to do using our native language, like they do in science fiction movies. (“Computer, how long will it take to reach planet Alphalpha at maximum warp?”) Unfortunately, despite the continuing efforts of many top-flight computer scientists (including your author), designing a computer to understand human language is still an unsolved problem. Even if computers could understand us, human languages are not very well suited for describing complex algorithms. Natural language is fraught with ambiguity and imprecision. For example, if I say: “I saw the man in the park with the telescope,” did I have the telescope, or did the man? And who was in the park? We understand each other most of the time only because all humans share a vast store of common knowledge and experience. Even then, miscommunication is commonplace. Computer scientists have gotten around this problem by designing notations for expressing computations in an exact, and unambiguous way. These special notations are called programming languages. Every structure in a programming language has a precise form (its syntax) and a precise meaning (its semantics). A programming language is something like a code for writing down the instructions that a computer will follow. In fact, programmers often refer to their programs as computer code, and the process of writing an algorithm in a programming language is called coding. Python is one example of a programming language. It is the language that we will use throughout this book. You may have heard of some other languages, such as C++, Java, Perl, Scheme, or BASIC. Although these languages differ in many details, they all share the property of having well-defined, unambiguous syntax and semantics. All of the languages mentioned above are examples of high-level computer languages. Although they are precise, they are designed to be used and understood by humans. Strictly speaking, computer hardware can only understand very low-level language known as machine language. Suppose we want the computer to add two numbers. The instructions that the CPU actually carries out might be something like this. load the number from memory location 2001 into the CPU load the number from memory location 2002 into the CPU Add the two numbers in the CPU store the result into location 2003 This seems like a lot of work to add two numbers, doesn’t it? Actually, it’s even more complicated than this because the instructions and numbers are represented in binary notation (as sequences of 0s and 1s). In a high-level language like Python, the addition of two numbers can be expressed more naturally: c = a + b. That’s a lot easier for us to understand, but we need some way to translate the high-level language into the machine language that the computer can execute. There are two ways to do this: a high-level language can either be compiled or interpreted. A compiler is a complex computer program that takes another program written in a high-level language and translates it into an equivalent program in the machine language of some computer. Figure 1.2 shows a block diagram of the compiling process. The high-level program is called source code, and the resulting machine code is a program that the computer can directly execute. The dashed line in the diagram represents the execution of the machine code. An interpreter is a program that simulates a computer that understands a high-level language. Rather than translating the source program into a machine language equivalent, the interpreter analyzes and executes the source code instruction by instruction as necessary. Figure 1.3 illustrates the process. The difference between interpreting and compiling is that compiling is a one-shot translation; once a program is compiled, it may be run over and over again without further need for the compiler or the source code. In the interpreted case, the interpreter and the source are needed every time the program runs. Compiled programs tend to be faster, since the translation is done once and for all, but interpreted languages lend themselves to a more flexible programming environment as programs can be developed and run interactively. The translation process highlights another advantage that high-level languages have over machine language: portability. The machine language of a computer is created by the designers of the particular CPU.
1.6. THE MAGIC OF PYTHON Source Code (Program)
Figure 1.2: Compiling a High-Level Language
Source Code (Program)
Computer Running an Outputs Interpreter
Figure 1.3: Interpreting a High-Level Language. Each kind of computer has its own machine language. A program for a Pentium CPU won’t run on a Macintosh that sports a PowerPC. On the other hand, a program written in a high-level language can be run on many different kinds of computers as long as there is a suitable compiler or interpreter (which is just another program). For example, if I design a new computer, I can also program a Python interpreter for it, and then any program written in Python can be run on my new computer, as is.
1.6 The Magic of Python Now that you have all the technical details, it’s time to start having fun with Python. The ultimate goal is to make the computer do our bidding. To this end, we will write programs that control the computational processes inside the machine. You have already seen that there is no magic in this process, but in some ways programming feels like magic. The computational processes inside the computer are like magical spirits that we can harness for our work. Unfortunately, those spirits only understand a very arcane language that we do not know. What we need is a friendly Genie that can direct the spirits to fulfill our wishes. Our Genie is a Python interpreter. We can give instructions to the Python interpreter, and it directs the underlying spirits to carry out our demands. We communicate with the Genie through a special language of spells and incantations (i.e., Python). The best way to start learning about Python is to let our Genie out of the bottle and try some spells. You can start the Python interpreter in an interactive mode and type in some commands to see what happens. When you first start the interpreter program, you may see something like the following: Python 2.1 (#1, Jun 21 2001, 11:39:00) [GCC pgcc-2.91.66 19990314 (egcs-1.1.2 release)] on linux2 Type "copyright", "credits" or "license" for more information. >>> The is a Python prompt indicating that the Genie is waiting for us to give it a command. In programming languages, a complete command is called a statement. Here is a sample interaction with the Python interpreter.
Here I have tried out three examples using the Python print statement. The first statement asks Python to display the literal phrase Hello, World. Python responds on the next line by printing the phrase. The second print statement asks Python to print the sum of 2 and 3. The third print combines these two ideas. Python prints the part in quotes “2 + 3 =” followed by the result of adding 2 + 3, which is 5. This kind of interaction is a great way to try out new things in Python. Snippets of interactive sessions are sprinkled throughout this book. When you see the Python prompt in an example, that should tip you off that an interactive session is being illustrated. It’s a good idea to fire up Python and try the examples for yourself. Usually we want to move beyond snippets and execute an entire sequence of statements. Python lets us put a sequence of statements together to create a brand-new command called a function. Here is an example of creating a new function called hello. >>> def hello(): print "Hello" print "Computers are Fun" >>> The first line tells Python that we are defining a new function called hello. The following lines are indented to show that they are part of the hello function. The blank line (obtained by hitting the key twice) lets Python know that the definition is finished, and the interpreter responds with another prompt. Notice that the definition did not cause anything to happen. We have told Python what should happen when the hello function is used as a command; we haven’t actually asked Python to perform it yet. A function is invoked by typing its name. Here’s what happens when we use our hello command. >>> hello() Hello Computers are Fun >>> Do you see what this does? The two print statements from the hello function are executed in sequence. You may be wondering about the parentheses in the definition and use of hello. Commands can have changeable parts called parameters that are placed within the parentheses. Let’s look at an example of a customized greeting using a parameter. First the definition: >>> def greet(person): print "Hello", person print "How are you?" Now we can use our customized greeting. >>> greet("John") Hello John How are you? >>> greet("Emily") Hello Emily How are you? >>>
1.6. THE MAGIC OF PYTHON
Can you see what is happening here? When we use greet we can send different names to customize the result. We will discuss parameters in detail later on. For the time being, our functions will not use parameters, so the parentheses will be empty, but you still need to include them when defining and using functions. One problem with entering functions interactively at the Python prompt like this is that the definitions go away when we quit Python. If we want to use them again the next time, we have to type them all over again. Programs are usually created by typing definitions into a separate file called a module or script. This file is saved on a disk so that it can be used over and over again. A module file is just a text file, and you can create one using any program for editing text, like a notepad or word processor program (provided you save your program as a “plain text” file). A special type of program known as a programming environment simplifies the process. A programming environment is specifically designed to help programmers write programs and includes features such as automatic indenting, color highlighting, and interactive development. The standard Python distribution includes a programming environment called Idle that you may use for working on the programs in this book. Let’s illustrate the use of a module file by writing and running a complete program. Our program will illustrate a mathematical concept known as chaos. Here is the program as we would type it into Idle or some other editor and save in a module file: # File: chaos.py # A simple program illustrating chaotic behavior. def main(): print "This program illustrates a chaotic function" x = input("Enter a number between 0 and 1: ") for i in range(10): x = 3.9 * x * (1 - x) print x main() This file should be saved with with the name chaos.py. The .py extension indicates that this is a Python module. You can see that this particular example contains lines to define a new function called main. (Programs are often placed in a function called main.) The last line of the file is the command to invoke this function. Don’t worry if you don’t understand what main actually does; we will discuss it in the next section. The point here is that once we have a program in a module file, we can run it any time we want. This program can be run in a number of different ways that depend on the actual operating system and programming environment that you are using. If you are using a windowing system, you can run a Python program by (double-)clicking on the module file’s icon. In a command-line situation, you might type a command like python chaos.py. If you are using Idle (or another programming environment) you can run a program by opening it in the editor and then selecting a command like import, run, or execute. One method that should always work is to start the Python interpreter and then import the file. Here is how that looks. >>> import chaos This program illustrates a chaotic function Enter a number between 0 and 1: .25 0.73125 0.76644140625 0.698135010439 0.82189581879 0.570894019197 0.955398748364 0.166186721954 0.540417912062 0.9686289303 0.118509010176 >>>
CHAPTER 1. COMPUTERS AND PROGRAMS
Typing the first line import chaos tells the Python interpreter to load the chaos module from the file chaos.py into main memory. Notice that I did not include the .py extension on the import line; Python assumes the module will have a .py extension. As Python imports the module file, each line executes. It’s just as if we had typed them one-by-one at the interactive Python prompt. The def in the module causes Python to create the main function. When Python encounters the last line of the module, the main function is invoked, thus running our program. The running program asks the user to enter a number between 0 and 1 (in this case, I typed “.25”) and then prints out a series of 10 numbers. When you first import a module file in this way, Python creates a companion file with a .pyc extension. In this example, Python creates another file on the disk called chaos.pyc. This is an intermediate file used by the Python interpreter. Technically, Python uses a hybrid compiling/interpreting process. The Python source in the module file is compiled into more primitive instructions called byte code. This byte code (the .pyc) file is then interpreted. Having a .pyc file available makes importing a module faster the second time around. However, you may delete the byte code files if you wish to save disk space; Python will automatically re-create them as needed. A module only needs to be imported into a session once. After the module has been loaded, we can run the program again by asking Python to execute the main command. We do this by using a special dot notation. Typing chaos.main() tells Python to invoke the main function in the chaos module. Continuing with our example, here is how it looks when we rerun the program with 26 as the input. >>> chaos.main() Enter a number between 0 and 1: .26 0.75036 0.73054749456 0.767706625733 0.6954993339 0.825942040734 0.560670965721 0.960644232282 0.147446875935 0.490254549376 0.974629602149 >>>
1.7 Inside a Python Program The output from the chaos program may not look very exciting, but it illustrates a very interesting phenomenon known to physicists and mathematicians. Let’s take a look at this program line by line and see what it does. Don’t worry about understanding every detail right away; we will be returning to all of these ideas in the next chapter. The first two lines of the program start with the # character: # File: chaos.py # A simple program illustrating chaotic behavior. These lines are called comments. They are intended for human readers of the program and are ignored by Python. The Python interpreter always skips any text from the pound sign (#) through the end of a line. The next line of the program begins the definition of a function called main. def main(): Strictly speaking, it would not be necessary to create a main function. Since the lines of a module are executed as they are loaded, we could have written our program without this definition. That is, the module could have looked like this:
1.7. INSIDE A PYTHON PROGRAM
# File: chaos.py # A simple program illustrating chaotic behavior. print "This program illustrates a chaotic function" x = input("Enter a number between 0 and 1: ") for i in range(10): x = 3.9 * x * (1 - x) print x This version is a bit shorter, but it is customary to place the instructions that comprise a program inside of a function called main. One immediate benefit of this approach was illustrated above; it allows us to (re)run the program by simply invoking chaos.main(). We don’t have to reload the module from the file in order to run it again, which would be necessary in the main-less case. The first line inside of main is really the beginning of our program. print "This program illustrates a chaotic function" This line causes Python to print a message introducing the program when it runs. Take a look at the next line of the program. x = input("Enter a number between 0 and 1: ") Here x is an example of a variable. A variable is used to give a name to a value so that we can refer to it at other points in the program. The entire line is an input statement. When Python gets to this statement, it displays the quoted message Enter a number between 0 and 1: and then pauses, waiting for the user to type something on the keyboard and press the key. The value that the user types is then stored as the variable x. In the first example shown above, the user entered .25, which becomes the value of x. The next statement is an example of a loop. for i in range(10): A loop is a device that tells Python to do the same thing over and over again. This particular loop says to do something 10 times. The lines indented underneath the loop heading are the statements that are done 10 times. These form the body of the loop. x = 3.9 * x * (1 - x) print x The effect of the loop is exactly the same as if we had written the body of the loop 10 times: x = 3.9 print x x = 3.9 print x x = 3.9 print x x = 3.9 print x x = 3.9 print x x = 3.9 print x x = 3.9 print x x = 3.9 print x x = 3.9
* x * (1 - x) * x * (1 - x) * x * (1 - x) * x * (1 - x) * x * (1 - x) * x * (1 - x) * x * (1 - x) * x * (1 - x) * x * (1 - x)
CHAPTER 1. COMPUTERS AND PROGRAMS
10 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.
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 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:
CHAPTER 1. COMPUTERS AND PROGRAMS
12 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.)
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
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.
2.3. ELEMENTS OF PROGRAMS
What is the Celsius temperature? 100 The temperature is 212.0 degrees fahrenheit. You can see that Suzie used the values of 0 and 100 to test her program. It looks pretty good, and she is satisfied with her solution. Apparently, no debugging is necessary.
2.3 Elements of Programs Now that you know something about the programming process, you are almost ready to start writing programs on your own. Before doing that, though, you need a more complete grounding in the fundamentals of Python. The next few sections will discuss technical details that are essential to writing correct programs. This material can seem a bit tedious, but you will have to master these basics before plunging into more interesting waters.
2.3.1 Names You have already seen that names are an important part of programming. We give names to modules (e.g., convert) and to the functions within modules (e.g., main). Variables are used to give names to values (e.g., celsius and fahrenheit). Technically, all these names are called identifiers. Python has some rules about how identifiers are formed. Every identifier must begin with a letter or underscore (the “ ” character) which may be followed by any sequence of letters, digits, or underscores. This implies that a single identifier cannot contain any spaces. According to these rules, all of the following are legal names in Python: x celsius spam spam2 SpamAndEggs Spam_and_Eggs Identifiers are case-sensitive, so spam, Spam, sPam, and SPAM are all different names to Python. For the most part, programmers are free to choose any name that conforms to these rules. Good programmers always try to choose names that describe the thing being named. One other important thing to be aware of is that some identifiers are part of Python itself. These names are called reserved words and cannot be used as ordinary identifiers. The complete list of Python reserved words is shown in Table 2.1. and assert break class continue def
del elif else except exec finally
for from global if import in
is lambda not or pass print
raise return try while yield
Table 2.1: Python Reserved Words.
2.3.2 Expressions Programs manipulate data. The fragments of code that produce or calculate new data values are called expressions. So far our program examples have dealt mostly with numbers, so I’ll use numeric data to illustrate expressions.
CHAPTER 2. WRITING SIMPLE PROGRAMS
The simplest kind of expression is a literal. A literal is used to indicate a specific value. In chaos.py you can find the numbers 3.9 and 1. The convert.py program contains 9.0, 5.0, and 32. These are all examples of numeric literals, and their meaning is obvious: 32 represents, well, 32. A simple identifier can also be an expression. We use identifiers as variables to give names to values. When an identifier appears in an expression, this value is retrieved to provide a result for the expression. Here is an interaction with the Python interpreter that illustrates the use of variables as expressions. >>> x = 5 >>> x 5 >>> print x 5 >>> print spam Traceback (innermost last): File "", line 1, in ? print spam NameError: spam >>> First the variable x is assigned the value 5 (using the numeric literal 5). The next line has Python evaluate the expression x. Python spits back 5, which is the value that was just assigned to x. Of course, we get the same result when we put x in a print statement. The last example shows what happens when we use a variable that has not been assigned a value. Python cannot find a value, so it reports a Name Error. This says that there is no value with that name. A variable must always be assigned a value before it can be used in an expression. More complex and interesting expressions can be constructed by combining simpler expressions with operators. For numbers, Python provides the normal set of mathematical operations: addition, subtraction, multiplication, division, and exponentiation. The corresponding Python operators are: +, -, *, /, and **. Here are some examples of complex expressions from chaos.py and convert.py 3.9 * x * (1 - x) 9.0 / 5.0 * celsius + 32 Spaces are irrelevant within an expression. The last expression could have been written 9.0/5.0*celsius+32 and the result would be exactly the same. Usually it’s a good idea to place some spaces in expressions to make them easier to read. Python’s mathematical operators obey the same rules of precedence and associativity that you learned in your math classes, including using parentheses to modify the order of evaluation. You should have little trouble constructing complex expressions in your own programs. Do keep in mind that only the round parentheses are allowed in expressions, but you can nest them if necessary to create expressions like this. ((x1 - x2) / 2*n) + (spam / k**3) If you are reading carefully, you may be curious why, in her temperature conversion program, Suzie Programmer chose to write 9.0/5.0 rather than 9/5. Both of these are legal expressions, but they give different results. This mystery will be discussed in Chapter 3. If you can’t stand the wait, try them out for yourself and see if you can figure out what’s going on.
2.4 Output Statements Now that you have the basic building blocks, identifier and expression, you are ready for a more complete description of various Python statements. You already know that you can display information on the screen using Python’s print statement. But what exactly can be printed? Python, like all programming languages, has a precise set of rules for the syntax (form) and semantics (meaning) of each statement. Computer scientists have developed sophisticated notations called meta-languages for describing programming languages. In this book we will rely on a simple template notation to illustrate the syntax of statements. Here are the possible forms of the print statement:
2.5. ASSIGNMENT STATEMENTS
print print print , , ..., print , , ..., , In a nutshell, these templates show that a print statement consists of the keyword print followed by zero or more expressions, which are separated by commas. The angle bracket notation ( ) is used to indicate “slots” that are filled in by other fragments of Python code. The name inside the brackets indicate what is missing; expr stands for an expression. The ellipses (“...”) indicate an indefinite series (of expressions, in this case). You don’t actually type the dots. The fourth version shows that a print statement may be optionally ended with a comma. That is all there is to know about the syntax of print. As far as semantics, a print statement displays information in textual form. Any supplied expressions are evaluated left to right, and the resulting values are displayed on a single line of output in a left-to-right fashion. A single blank space character is placed between the displayed values. Normally, successive print statements will display on separate lines of the screen. A bare print (first version above) can be used to get a blank line of output. If a print statement ends with a comma (fourth version), a final space is appended to the line, but the output does not advance to the next line. Using this method, multiple print statements can be used to generate a single line of output. Putting it all together, this sequence of print statements print print print print print print
3+4 3, 4, 3 + 4 3, 4, 3+4 "The answer is", 3 + 4
produces this output 7 3 4 7 3 4 7 The answer is 7 That last print statement may be a bit confusing. According to the syntax templates above, print requires a sequence of expressions. That means "The answer is" must be an expression. In fact, it is an expression, but it doesn’t produce a number. Instead, it produces another kind of data called a string. A sequence of characters enclosed in quotes is a string literal. Strings will be discussed in detail in a later chapter. For now, consider this a convenient way of labeling output.
2.5 Assignment Statements 2.5.1 Simple Assignment One of the most important kinds of statements in Python is the assignment statement. We’ve already seen a number of these in our previous examples. The basic assignment statement has this form: = Here variable is an identifier and expr is an expression. The semantics of the assignment is that the expression on the right side is evaluated to produce a value, which is then associated with the variable named on the left side. Here are some of the assignments we’ve already seen. x = 3.9 * x * (1 - x) fahrenheit = 9.0 / 5.0 * celsius + 32 x = 5
CHAPTER 2. WRITING SIMPLE PROGRAMS
A variable can be assigned many times. It always retains the value of the most recent assignment. Here is an interactive Python session that demonstrates the point: >>> >>> 0 >>> >>> 7 >>> >>> 8
The last assignment statement shows how the current value of a variable can be used to update its value. In this case I simply added one to the previous value. The chaos.py program from Chapter 1 did something similar, though a bit more complex. Remember, the values of variables can change; that’s why they’re called variables.
2.5.2 Assigning Input The purpose of an input statement is to get some information from the user of a program and store it into a variable. Some programming languages have a special statement to do this. In Python, input is accomplished using an assignment statement combined with a special expression called input. This template shows the standard form. = input() Here prompt is an expression that serves to prompt the user for input; this is almost always a string literal (i.e., some text inside of quotation marks). When Python encounters an input expression, it evaluates the prompt and displays the result of the prompt on the screen. Python then pauses and waits for the user to type an expression and press the Enter key. The expression typed by the user is then evaluated to produce the result of the input. This sounds complicated, but most uses of input are straightforward. In our example programs, input statements are used to get numbers from the user. x = input("Please enter a number between 0 and 1: ") celsius = input("What is the Celsius temperature? ") If you are reading programs carefully, you probably noticed the blank space inside the quotes at the end of these prompts. I usually put a space at the end of a prompt so that the input that the user types does not start right next to the prompt. Putting a space in makes the interaction easier to read and understand. Although these two examples specifically prompt the user to enter a number, a number is just a numeric literal—a simple Python expression. In fact, any valid expression would be just as acceptable. Consider the following interaction with the Python interpreter. >>> ans = input("Enter an expression: ") Enter an expression: 3 + 4 * 5 >>> print ans 23 >>> Here, when prompted to enter an expression, the user typed “3 + 4 * 5.” Python evaluated this expression and stored the value in the variable ans. When printed, we see that ans got the value 23 as expected. In a way, the input is like a delayed expression. The example interaction produced exactly the same result as if we had simply done ans = 3 + 4 * 5. The difference is that the expression was supplied at the time the statement was executed instead of being determined when the statement was written by the programmer. Thus, the user can supply formulas for a program to evaluate.
2.5. ASSIGNMENT STATEMENTS
2.5.3 Simultaneous Assignment There is an alternative form of the assignment statement that allows us to calculate several values all at the same time. It looks like this: , , ..., = , , ..., This is called simultaneous assignment. Semantically, this tells Python to evaluate all the expressions on the right-hand side and then assign these values to the corresponding variables named on the left-hand side. Here’s an example. sum, diff = x+y, x-y Here sum would get the sum of x and y and diff would get the difference. This form of assignment seems strange at first, but it can prove remarkably useful. Here’s an example. Suppose you have two variables x and y and you want to swap the values. That is, you want the value currently stored in x to be in y and the value that is currently in y to be stored in x. At first, you might think this could be done with two simple assignments. x = y y = x This doesn’t work. We can trace the execution of these statements step-by-step to see why. Suppose x and y start with the values 2 and 4. Let’s examine the logic of the program to see how the variables change. The following sequence uses comments to describe what happens to the variables as these two statements are executed. # # x # y #
variables initial values = y now = x final
See how the first statement clobbers the original value of x by assigning to it the value of y? When we then assign x to y in the second step, we just end up with two copies of the original y value. One way to make the swap work is to introduce an additional variable that temporarily remembers the original value of x. temp = x x = y y = temp Let’s walk-through this sequence to see how it works. # variables # initial values temp = x # x = y # y = temp #
temp no value yet
As you can see from the final values of x and y, the swap was successful in this case. This sort of three-way shuffle is common in other programming languages. In Python, the simultaneous assignment statement offers an elegant alternative. Here is a simpler Python equivalent: x, y = y, x
CHAPTER 2. WRITING SIMPLE PROGRAMS
Because the assignment is simultaneous, it avoids wiping out one of the original values. Simultaneous assignment can also be used to get multiple values from the user in a single input. Consider this program for averaging exam scores: # avg2.py # A simple program to average two exam scores # Illustrates use of multiple input def main(): print "This program computes the average of two exam scores." score1, score2 = input("Enter two scores separated by a comma: ") average = (score1 + score2) / 2.0 print "The average of the scores is:", average main() The program prompts for two scores separated by a comma. Suppose the user types 86, 92. The effect of the input statement is then the same as if we had done this assignment: score1, score2 = 86, 92 We have gotten a value for each of the variables in one fell swoop. This example used just two values, but it could be generalized to any number of inputs. Of course, we could have just gotten the input from the user using separate input statements. score1 = input("Enter the first score: ") score2 = input("Enter the second score: ") In some ways this may be better, as the separate prompts are more informative for the user. In this example the decision as to which approach to take is largely a matter of taste. Sometimes getting multiple values in a single input provides a more intuitive user interface, so it is nice technique to have in your toolkit.
2.6 Definite Loops You already know that programmers use loops to execute a sequence of statements several times in succession. The simplest kind of loop is called a definite loop. This is a loop that will execute a definite number of times. That is, at the point in the program when the loop begins, Python knows how many times to go around (or iterate) the body of the loop. For example, the Chaos program from Chapter 1 used a loop that always executed exactly ten times. for i in range(10): x = 3.9 * x * (1 - x) print x This particular loop pattern is called a counted loop, and it is built using a Python for statement. Before considering this example in detail, let’s take a look at what for loops are all about. A Python for loop has this general form. for in : The body of the loop can be any sequence of Python statements. The start and end of the body is indicated by its indentation under the loop heading (the for in : part). The meaning of the for statement is a bit awkward to explain in words, but is very easy to understand, once you get the hang of it. The variable after the keyword for is called the loop index. It takes on
2.6. DEFINITE LOOPS
each successive value in the sequence, and the statements in the body are executed once for each value. Usually, the sequence portion is a list of values. You can build a simple list by placing a sequence of expressions in square brackets. Some interactive examples help to illustrate the point: >>> for i in [0,1,2,3]: print i 0 1 2 3 >>> for odd in [1, 3, 5, 7, 9]: print odd * odd 1 9 25 49 81 You can see what is happening in these two examples. The body of the loop is executed using each successive value in the list. The length of the list determines the number of times the loop will execute. In the first example, the list contains the four values 0 through 3, and these successive values of i are simply printed. In the second example, odd takes on the values of the first five odd natural numbers, and the body of the loop prints the squares of these numbers. Now, let’s go back to the example which began this section (from chaos.py) Look again at the loop heading: for i in range(10): Comparing this to the template for the for loop shows that the last portion, range(10) must be some kind of sequence. Let’s see what the Python interpreter tells us. >>> range(10) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Do you see what is happening here? The range function is a built-in Python command that simply produces a list of numbers. The loop using range(10) is exactly equivalent to one using a list of 10 numbers. for i in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]: In general, range() will produce a list of numbers that starts with 0 and goes up to, but not including, the value of . If you think about it, you will see that the value of the expression determines the number of items in the resulting list. In chaos.py we did not even care what values the loop index variable used (since the value of i was not referred to anywhere in the loop body). We just needed a list of length 10 to make the body execute 10 times. As I mentioned above, this pattern is called a counted loop, and it is a very common way to use definite loops. When you want to do something in your program a certain number of times, use a for loop with a suitable range. for in range(): The value of the expression determines how many times the loop executes. The name of the index variable doesn’t really matter much; programmers often use i or j as the loop index variable for counted loops. Just be sure to use an identifier that you are not using for any other purpose. Otherwise you might accidentally wipe out a value that you will need later.
CHAPTER 2. WRITING SIMPLE PROGRAMS
The interesting and useful thing about loops is the way that they alter the “flow of control” in a program. Usually we think of computers as executing a series of instructions in strict sequence. Introducing a loop causes Python to go back and do some statements over and over again. Statements like the for loop are called control structures because they control the execution of other parts of the program. Some programmers find it helpful to think of control structures in terms of pictures called flowcharts. A flowchart is a diagram that uses boxes to represent different parts of a program and arrows between the boxes to show the sequence of events when the program is running. Figure 2.1 depicts the semantics of the for loop as a flowchart.
more items in
yes = next item
Figure 2.1: Flowchart of a for loop.
If you are having trouble understanding the for loop, you might find it useful to study the flowchart. The diamond shape box in the flowchart represents a decision in the program. When Python gets the the loop heading, it checks to see if there are any (more) items left if the sequence. If the answer is yes, the value of the loop index variable is set to the next item in the sequence, and then the loop body is executed. Once the body is complete, the program goes back to the loop heading and checks for another value in the sequence. The loop quits when there are no more items, and the program moves on to the statements that come after the loop.
2.7 Example Program: Future Value Let’s close the chapter with one more example of the programming process in action. We want to develop a program to determine the future value of an investment. Let’s start with an analysis of the problem (requirements). You know that money that is deposited in a bank account earns interest, and this interest accumulates as the years pass. How much will an account be worth ten years from now? Obviously it depends on how much money we start with (the principal) and how much interest the account earns. Given the principal and the interest rate, a program should be able to calculate the value of the investment ten years into the future. We continue by developing the exact specifications for the program. Recall, this is a description of what the program will do. What exactly should the inputs be? We need the user to enter the initial amount to invest, the principal. We will also need some indication of how much interest the account earns. This depends both on the interest rate and how often the interest is compounded. One simple way of handling this is to have the user enter an annualized percentage rate. Whatever the actual interest rate and compounding frequency, the annualized rate tells us how much the investment accrues in one year. If the annualized interest is 3%, then a
2.7. EXAMPLE PROGRAM: FUTURE VALUE
$100 investment will grow to $103 in one year’s time. How should the user represent an annualized rate of 3%? There are a number of reasonable choices. Let’s assume the user supplies a decimal, so the rate would be entered as 0.03. This leads us to the following specification. Program Future Value Inputs principal The amount of money being invested in dollars. apr The annualized percentage rate expressed as a decimal fraction. Output The value of the investment 10 years into the future. Relationship Value after one year is given by principal 1 apr . This formula needs to be applied 10 times.
Next we design an algorithm for the program. We’ll use pseudocode, so that we can formulate our ideas without worrying about all the rules of Python. Given our specification, the algorithm seems straightforward. Print an introduction Input the amount of the principal (principal) Input the annualized percentage rate (apr) Repeat 10 times: principal = principal * (1 + apr) Output the value of principal Now that we’ve thought the problem all the way through to pseudocode, it’s time to put our new Python knowledge to work and develop a program. Each line of the algorithm translates into a statement of Python. Print an introduction (print statement, Section 2.4) print "This program calculates the future value of a 10-year investment" Input the amount of the principal (input statement, Section 2.5.2) principal = input("Enter the initial principal: Input the annualized percentage rate (input statement, Section 2.5.2) apr = input("Enter the annualized interest rate:
Repeat 10 times: (counted loop, Section 2.6) for i in range(10): Calculate principal = principal * (1 + apr) (simple assignment statement, Section 2.5.1) principal = principal * (1 + apr) Output the value of the principal (print statement, Section 2.4) print "The amount in 10 years is:", principal
All of the statement types in this program have been discussed in detail in this chapter. If you have any questions, you should go back and review the relevant descriptions. Notice especially the counted loop pattern is used to apply the interest formula 10 times. That about wraps it up. Here is the completed program. # futval.py # A program to compute the value of an investment # carried 10 years into the future
CHAPTER 2. WRITING SIMPLE PROGRAMS
24 # by:
John M. Zelle
def main(): print "This program calculates the future value of a 10-year investment." principal = input("Enter the initial principal: ") apr = input("Enter the annualized interest rate: ") for i in range(10): principal = principal * (1 + apr) print "The amount in 10 years is:", principal main() Notice that I have added a few blank lines to separate the Input, Processing, and Output portions of the program. Strategically placed “white space” can help make your programs more readable. That’s about it for this example; I leave the testing and debugging as an exercise for you.
2.8 Exercises 1. List and describe in your own words the six steps in the software development process. 2. Write out the chaos.py program (Section 1.6) and identify the parts of the program as follows: Circle each identifier. Underline each expression. Put a comment at the end of each line indicating the type of statement on that line (output, assignment, input, loop, etc.) 3. A user-friendly program should print an introduction that tells the user what the program does. Modify the convert.py program (Section 2.2) to print an introduction. 4. Modify the avg2.py program (Section 2.5.3) to find the average of three exam scores. 5. Modify the futval.py program (Section 2.7) so that the number of years for the investment is also a user input. Make sure to change the final message to reflect the correct number of years. 6. Modify the convert.py program (Section 2.2) with a loop so that it executes 5 times before quitting (i.e., it converts 5 temperatures in a row). 7. Modify the convert.py program (Section 2.2) so that it computes and prints a table of Celsius temperatures and the Fahrenheit equivalents every 10 degrees from 0C to 100C. 8. Write a program that converts from Fahrenheit to Celsius. 9. Modify the futval.py program (Section 2.7) so that it computes the actual purchasing power of the investment, taking inflation into account. The yearly rate of inflation will be a second input. The adjustment is given by this formula: principal = principal/(1 + inflation)
Computing with Numbers When computers were first developed, they were seen primarily as number crunchers, and that is still an important application. As you have seen, problems that involve mathematical formulas are easy to translate into Python programs. This chapter takes a closer look at computations involving numeric calculations.
3.1 Numeric Data Types The information that is stored and manipulated by computer programs is generically referred to as data. Different kinds of data will be stored and manipulated in different ways. Consider this program that calculates the value of loose change. # change.py # A program to calculate the value of some change in dollars def main(): print "Change Counter" print print "Please enter the count of each coin type." quarters = input("Quarters: ") dimes = input("Dimes: ") nickels = input("Nickels: ") pennies = input("Pennies: ") total = quarters * .25 + dimes * .10 + nickels * .05 + pennies * .01 print print "The total value of your change is", total main() Here is an example of the output. Change Counter Please enter the count of each coin type. Quarters: 5 Dimes: 3 Nickels: 4 Pennies: 6 The total value of your change is 1.81 This program actually manipulates two different kinds of numbers. The values entered by the user (5, 3, 4, 6) are are whole numbers; they don’t have any fractional part. The values of the coins (.25, .10, .05, .01) 25
CHAPTER 3. COMPUTING WITH NUMBERS
are decimal fractions. Inside the computer, whole numbers and numbers that have fractional components are represented differently. Technically, we say that these are two different data types. The data type of an object determines what values it can have and what operations can be performed on it. Whole numbers are represented using the integer data type (int for short). Values of type int can be positive or negative whole numbers. Numbers that can have fractional parts are represented as floating point (or float) values. So how do we tell whether a number is an int or a float? A numeric literal that does not contain a decimal point produces an int value, while a literal that has a decimal point is represented by a float (even if the fractional part is 0). Python provides a special function called type that tells us the data type of any value. Here is an interaction with the Python interpreter showing the difference between int and float literals. >>> type(3) >>> type(3.14) >>> type(3.0) >>> myInt = -32 >>> type(myInt) >>> myFloat = 32.0 >>> type(myFloat) You may be wondering why there are two different data types for numbers. One reason has to do with program style. Values that represent counts can’t be fractional; we can’t have 3 12 quarters, for example. Using an int value tells the reader of a program that the value can’t be a fraction. Another reason has to do with the efficiency of various operations. The underlying algorithms that perform computer arithmetic are simpler, and therefore faster, for ints than the more general algorithms required for float values. You should be warned that the float type only stores approximations. There is a limit to the precision, or accuracy, of the stored values. Since float values are not exact, while ints always are, your general rule of thumb should be: if you don’t absolutely need fractional values, use an int. operator
operation addition subtraction multiplication division exponentiation remainder absolute value
Table 3.1: Python built-in numeric operations. A value’s data type determines what operations can be used on it. As we have seen, Python supports the usual mathematical operations on numbers. Table 3.1 summarizes these operations. Actually, this table is somewhat misleading since the two numeric data types have their own operations. When addition is performed on floats, the computer performs a floating point addition. Whereas, with ints, the computer performs an integer addition. Consider the following interaction with Python: >>> 3.0 + 4.0 7.0 >>> 3 + 4 7
3.2. USING THE MATH LIBRARY
>>> 3.0 * 4.0 12.0 >>> 3 * 4 12 >>> 10.0 / 3.0 3.33333333333 >>> 10 / 3 3 >>> 10 % 3 1 >>> abs(5) 5 >>> abs(-3.5) 3.5 Notice how operations on floats produce floats, and operations on ints produce ints. Most of the time, we don’t have to worry about what type of operation is being performed; for example, integer addition produces pretty much the same result as floating point addition. However, in the case of division, the results are quite different. Integer division always produces an integer, discarding any fractional result. Think of integer division as “gozinta.” The expression, 10 / 3 produces 3 because three gozinta (goes into) ten three times (with a remainder of one). The third to last example shows the remainder operation (%) in action. The remainder of dividing 10 by 3 is 1. The last two examples illustrate taking the absolute value of an expression. You may recall from Chapter 2 that Suzie Programmer used the expression 9.0 / 5.0 in her temperature conversion program rather than 9 / 5. Now you know why. The former gives the correct multiplier of 1 8, while the latter yields just 1, since 5 gozinta 9 just once.
3.2 Using the Math Library Besides the operations listed in Table 3.1, Python provides many other useful mathematical functions in a special math library. A library is just a module that contains some useful definitions. Our next program illustrates the use of this library to compute the roots of quadratic equations. A quadratic equation has the form ax2 bx c 0. Such an equation has two solutions for the value of x given by the quadratic formula: b b2 4ac x 2a Let’s write a program that can find the solutions to a quadratic equation. The input to the program will be the values of the coefficients a, b, and c. The outputs are the two values given by the quadratic formula. Here’s a program that does the job.
# quadratic.py # A program that computes the real roots of a quadratic equation. # Illustrates use of the math library. # Note: this program crashes if the equation has no real roots. import math
# Makes the math library available.
def main(): print "This program finds the real solutions to a quadratic" print a, b, c = input("Please enter the coefficients (a, b, c): ") discRoot = math.sqrt(b * b - 4 * a * c)
CHAPTER 3. COMPUTING WITH NUMBERS
28 root1 = (-b + discRoot) / (2 * a) root2 = (-b - discRoot) / (2 * a)
print print "The solutions are:", root1, root2 main() This program makes use of the square root function sqrt from the math library module. The line at the top of the program: import math
tells Python that we are using the math module. Importing a module makes whatever is defined in it available to the program. To compute x, we use math.sqrt(x). You may recall this dot notation from Chapter 1. This tells Python to use the sqrt function that “lives” in the math module. In the quadratic program we calculate b2 4 ac with the line
discRoot = math.sqrt(b * b - 4 * a * c) Here is how the program looks in action: This program finds the real solutions to a quadratic Please enter the coefficients (a, b, c): 3, 4, -2 The solutions are: 0.387425886723 -1.72075922006 This program is fine as long as the quadratics we try to solve have real solutions. However, some inputs will cause the program to crash. Here’s another example run: This program finds the real solutions to a quadratic Please enter the coefficients (a, b, c): 1, 2, 3 Traceback (innermost last): File "", line 1, in ? File "quadratic.py", line 13, in ? discRoot = math.sqrt(b * b - 4 * a * c) OverflowError: math range error The problem here is that b2 4 a c 0, and the sqrt function is unable to compute the square root of a negative number. Python prints a math range error. Right now, we don’t have the tools to fix this problem, so we will just have to assume that the user gives us solvable equations. Actually, quadratic.py did not need to use the math library. We could have taken the square root using exponentiation **. (Can you see how?) Using math.sqrt is somewhat more efficient and allowed me to illustrate the use of the math library. In general, if your program requires a common mathematical function, the math library is the first place to look. Table 3.2 shows some of the other functions that are available in the math library.
3.3 Accumulating Results: Factorial Suppose you have a root beer sampler pack containing six different kinds of root beer. Drinking the various flavors in different orders might affect how good they taste. If you wanted to try out every possible ordering, how many different orders would there be? It turns out the answer is a surprisingly large number, 720. Do you know where this number comes from? The value 720 is the factorial of 6. In mathematics, factorial is often denoted with an exclamation (“!”). The factorial of a whole number n 1 . This happens to be the number of distinct arrangements for n items. is defined as n! n n 1 n 2 Given six items, we compute 6! 6 5 4 3 2 1 720 possible arrangements.
3.3. ACCUMULATING RESULTS: FACTORIAL Python pi e sin(x) cos(x) tan(x) asin(x) acos(x) atan(x) log(x) log10(x) exp(x) ceil(x) floor(x)
Mathematics π e sin x cos x tan x arcsinx arccosx arctanx ln x log10 x ex x x
English An approximation of pi. An approximation of e. The sine of x. The cosine of x. The tangent of x. The inverse of sine x. The inverse of cosine x. The inverse of tangent x. The natural (base e) logarithm of x The common (base 10) logarithm of x. The exponential of x. The smallest whole number x The largest whole number x
Table 3.2: Some math library functions.
Let’s write a program that will compute the factorial of a number entered by the user. The basic outline of our program follows an Input-Process-Output pattern. Input number to take factorial of, n Compute factorial of n, fact Output fact Obviously, the tricky part here is in the second step. How do we actually compute the factorial? Let’s try one by hand to get an idea for the process. In computing the factorial of 6, we first multiply 6 5 30. Then we take that result and do another multiplication 30 4 120. This result is multiplied by three 120 3 360. Finally, this result is multiplied by 2 360 2 720. According to the definition, we then multiply this result by 1, but that won’t change the final value of 720. Now let’s try to think about the algorithm more generally. What is actually going on here? We are doing repeated multiplications, and as we go along, we keep track of the running product. This is a very common algorithmic pattern called an accumulator. We build up, or accumulate, a final value piece by piece. To accomplish this in a program, we will use an accumulator variable and a loop structure. The general pattern looks like this. Initialize the accumulator variable Loop until final result is reached update the value of accumulator variable Realizing this is the pattern that solves the factorial problem, we just need to fill in the details. We will be accumulating the factorial. Let’s keep it in a variable called fact. Each time through the loop, we need to multiply fact by one of the factors n n 1 1. It looks like we should use a for loop that iterates over this sequence of factors. For example, to compute the factorial of 6, we need a loop that works like this.
fact = 1 for factor in [6,5,4,3,2,1]: fact = fact * factor Take a minute to trace through the execution of this loop and convince yourself that it works. When the loop body first executes, fact has the value 1 and factor is 6. So, the new value of fact is 1 6 6. The next time through the loop, factor will be 5, and fact is updated to 6 5 30. The pattern continues for each successive factor until the final result of 720 has been accumulated. The initial assignment of 1 to fact before the loop is essential to get the loop started. Each time through the loop body (including the first), the current value of fact is used to compute the next value. The
CHAPTER 3. COMPUTING WITH NUMBERS
initialization ensures that fact has a value on the very first iteration. Whenever you use the accumulator pattern, make sure you include the proper initialization. Forgetting it is a common mistake of beginning programmers. Of course, there are many other ways we could have written this loop. As you know from math class, multiplication is commutative and associative, so it really doesn’t matter what order we do the multiplications in. We could just as easily go the other direction. You might also notice that including 1 in the list of factors is unnecessary, since multiplication by 1 does not change the result. Here is another version that computes the same result. fact = 1 for factor in [2,3,4,5,6]: fact = fact * factor Unfortunately, neither of these loops solves the original problem. We have hand-coded the list of factors to compute the factorial of six. What we really want is a program that can compute the factorial of any given input n. We need some way to generate an appropriate list from the value of n. Luckily, this is quite easy to do using the Python range function. Recall that range(n) produces a list of numbers starting with 0 and continuing up to, but not including, n. There are other variations of range that can be used to produce different sequences. With two parameters, range(start,n) produces a sequence that starts with the value start and continues up to, but not including, n. A third version range(start, n, step) is like the two parameter version, except that it uses step as the increment between numbers. Here are some examples. >>> range(10) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> range(5,10) [5, 6, 7, 8, 9] >>> range(5, 10, 3) [5, 8] Given our input value n we have a couple of different range commands that produce an appropriate list of factors for computing the factorial of n. To generate them from smallest to largest (a la our second loop), we could use range(2,n+1). Notice how I used n+1 as the second parameter, since the range will go up to, but not including this value. We need the +1 to make sure that n itself is included as the last factor. Another possibility is to generate the factors in the other direction (a la our first loop) using the threeparameter version of range and a negative step to cause the counting to go backwards: range(n,1,-1). This one produces a list starting with n and counting down (step -1) to, but not including 1. Here then is one possible version of the factorial program. # factorial.py # Program to compute the factorial of a number # Illustrates for loop with an accumulator def main(): n = input("Please enter a whole number: ") fact = 1 for factor in range(n,1,-1): fact = fact * factor print "The factorial of", n, "is", fact main() Of course there are numerous other ways this program could have been written. I have already mentioned changing the order of factors. Another possibility is to initialize fact to n and then use factors starting at n 1 (as long as n 0). You might try out some of these variations and see which you like best.
3.4. THE LIMITS OF INT
3.4 The Limits of Int So far, I have talked about numeric data types as representations of familiar numbers such as integers and decimal fractions. It is important to keep in mind, however, that these numeric types are just representations, and they do not always behave exactly like the numbers that they represent. We can see an example of this as we test out our new factorial program. >>> import factorial Please enter a whole number: 6 The factorial of 6 is 720 >>> factorial.main() Please enter a whole number: 10 The factorial of 10 is 3628800 >>> factorial.main() Please enter a whole number: 13 Traceback (innermost last): File "", line 1, in ? File "factorial.py", line 9, in main fact = fact * factor OverflowError: integer multiplication Everything seems fine until we try to compute the factorial of 13. When computing 13! the program prints out an OverflowError message. What is going on here? The problem is that this program is representing whole numbers using Python’s int data type. Unfortunately, ints are not exactly like mathematical integers. There are infinitely many integers, but only a finite range of ints. Inside the computer, ints are stored in a fixed-sized binary representation. To make sense of this, we need to look at what’s going on at the hardware level. Computer memory is composed of electrical “switches,” each of which can be in one of two possible states, basically on or off. Each switch represents a binary digit or bit of information. One bit can encode two possibilities, usually represented with the numerals 0 (for off) and 1 (for on). A sequence of bits can be used to represent more possibilities. With two bits, we can represent four things. bit 2 0 0 1 1
bit 1 0 1 0 1
Three bits allow us to represent eight different values by adding a zero or one to each of the four two-bit patterns. bit 3 bit 2 bit 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 You can see the pattern here. Each extra bit doubles the number of distinct patterns. In general, n bits can represent 2n different values. The number of bits that a particular computer uses to represent an int depends on the design of the CPU. Typical PCs today use 32 bits. That means there are 232 possible values. These values are centered at 0 to
CHAPTER 3. COMPUTING WITH NUMBERS
represent a range of positive and negative integers. Now 22 231 . So, the range of integers that can be 31 31 represented in a 32 bit int value is 2 2 1. The reason for the 1 on the high end is to account for the representation of 0 in the top half of the range. Let’s try out some expressions in Python to test this analysis. Remember that ** is the Python exponentiation operator.
>>> 2 ** 30 1073741824 >>> 2 ** 31 Traceback (innermost last): File "", line 1, in ? OverflowError: integer pow() Python can calculate 230 , but “blows up” trying to compute 231 . You can see that the overflow happens somewhere between the 30th and 31st power of two. That is consistent with our analysis that the largest int is 231 1. Suppose we try to display the largest int.
>>> 2 ** 31 - 1 Traceback (innermost last): File "", line 1, in ? OverflowError: integer pow() Our first try didn’t work. Can you see why? Python evaluates this expression by first trying to calculate 2 ** 31. That calculation produces the error before Python has a chance to subtract one. We need to be a little cleverer and sneak up on the value from underneath. We can use the fact that 231 230 230 . Strategically subtracting one from each side gives us 231 1 230 1 230. By subtracting one in the middle of the computation, we can ensure that the intermediate value never gets bigger than the final result. Here’s what Python says:
>>> 2 ** 30 - 1 + 2 ** 30 2147483647 By the way, this expression illustrates another way that Python ints differ from the integers that they represent. In normal arithmetic, there is no difference between 2 31 1 and 230 1 230. They both represent the same value. In computer arithmetic, however, one is computable and the other is not! Representations of numbers do not always obey all the properties that we take for granted with numbers. Now that we have a numeric value, we can directly test our conjecture that this is the largest int.
>>> 2147483647 2147483647 >>> 2147483648 OverflowError: integer literal too large There you have it. The largest int that can be represented in 32 bits is 2 147 483 647. Now you know exactly why our program for factorial can’t compute 13!. This value is larger than the limit of 2 147 483 647. Naturally, the next step is to figure out a way around this limitation.
3.5 Handling Large Numbers: Long Ints As long as our factorial program relies on the int data type, we will not be able to find the factorial of larger numbers. We need to use another numeric type. You might first think of using a float instead. This does not really solve our problem. Here is an example run of a modified factorial program that initializes fact to the float 1 0.
3.5. HANDLING LARGE NUMBERS: LONG INTS
Please enter a whole number. 15 The factorial of 15 is 1.307674368e+12 We do not get an overflow error, but we also do not get an exact answer. A very large (or very small) floating point value is printed out using exponential, or scientific, notation. The e+12 at the end means that the result is equal to 1 307674368 10 12. You can think of the +12 at the end as a marker that shows where the decimal point should be placed. In this case, it must move 12 places to the right to get the actual value. However, there are only 9 digits to the right of the decimal, so we have “lost” the last three digits. Remember, floats are approximations. Using a float allows us to represent a much larger range of values, but the amount of precision is still fixed. In fact, a computer stores floating point numbers as a pair of fixedlength (binary) integers. One integer represents the string of digits in the value, and the second represents the exponent value that keeps track of where the whole part ends and the fractional part begins. Fortunately, Python provides a better solution for large, exact values in the form of a third numeric type long int. A long int is not a fixed size, but expands to accommodate whatever value it holds. The only limit is the amount of memory the computer has available to it. To get a long int, you put an “L” suffix on a numeric literal. So, the literal 5 is an int representation of the number five, but 5L is a long int representation of the number five. Of course, for a number this small, there is no reason to use a long int. However, using a long int causes Python to use long int operations, and our value can grow to any size. Here are some examples that illustrate: >>> 2L 2L >>> 2L ** 31 2147483648L >>> type(100L) >>> 10000000000000000000000000000000000000L + 25 10000000000000000000000000000000000025L Notice how calculations involving a long int produce a long int result. Using long ints allows us to compute with really large numbers. We can modify our factorial program to use long int by simply initializing fact to 1L. Since we start with a long int, each successive multiplication will produce another long int. # factorial2.py def main(): n = input("Please enter a whole number: ") fact = 1L # Use a long int here for factor in range(n,0,-1): fact = fact * factor print "The factorial of", n, "is", fact Now we can take the factorial of arbitrarily large inputs. >>> import factorial2 Please enter a whole number: 13 The factorial of 13 is 6227020800 >>> factorial2.main() Please enter a whole number: 100 The factorial of 100 is 933262154439441526816992388562667004907159682 643816214685929638952175999932299156089414639761565182862536979208272 23758251185210916864000000000000000000000000
CHAPTER 3. COMPUTING WITH NUMBERS
If you have an older version of Python (prior to version 2.0), these answers will be printed with an “L” appended. This is Python’s way of saying that the number is a long int. In newer versions, this artifact is automatically removed by the print statement. In the next chapter, you will learn how you could take care of getting the “L” out yourself. Now we have a factorial program that can compute interestingly large results. Long ints are pretty cool; you might be tempted to use them all the time. The down-side of using long ints is that these representations are less efficient than the plain int data type. The operations needed to do arithmetic on ints is built into the CPU of the computer. When doing operations on long ints, Python has to employ algorithms that simulate long arithmetic using the computer’s built-in fixed-length operations. As a result, long int arithmetic is much slower than int arithmetic. Unless you need very large values, ints are preferred.
3.6 Type Conversions Sometimes values of one data type need to be converted into another. You have seen that combining an int with an int produces an int, and combining a float with a float creates another float. But what happens if we write an expression that mixes an int with a float? For example, what should the value of x be after this assignment statement? x = 5.0 / 2 If this is floating point division, then the result should be the float value 2 5. If integer division is performed, the result is 2. Before reading ahead for the answer, take a minute to consider how you think Python should handle this situation. In order to make sense of the expression 5.0 / 2, Python must either change 5.0 to 5 and perform integer division or convert 2 to 2.0 and perform floating point division. In general, converting a float to an int is a dangerous step, because some information (the fractional part) will be lost. On the other hand, an int can be safely turned into a float just by adding a fractional part of 0. So, in mixed-typed expressions, Python will automatically convert ints to floats and perform floating point operations to produce a float result. Sometimes we may want to perform a type conversion ourselves. This is called an explicit type conversion. For example, suppose we are writing a program that finds the average of some numbers. Our program would first sum up the numbers and then divide by n, the count of how many numbers there are. The line of code to compute the average might look like this. average = sum / n Unfortunately, this line may not always produce the result we intend. Consider a specific example. The numbers to be averaged are the ints 4, 5, 6, 7. The sum variable will hold 22, also an int, and dividing by 4 gives the answer 5, not 5.5. Remember, an int divided by an int always produces an int. To solve this problem, we need to tell Python to convert one of the operands to a floating point value. average = float(sum) / n The float() function converts an int into a float. We only need to convert the numerator, because this produces a mixed-type expression, and Python will automatically convert the denominator. Notice that putting the float() around the entire expression would not work. average = float(sum/n) In this form, sum and n could both be ints causing Python to perform an integer division and then convert the resulting quotient to a float. Of course, this float would always end in 0, since it is being converted from an int. That is not what we want. Python also provides int() and long() functions that can be used to convert numbers into ints and longs, respectively. Here are a few examples.
As you can see, converting to an int or long int simply discards the fractional part of a float; the value is truncated, not rounded. If you want a rounded result, you can add 0.5 to the value before using int(), assuming the value is positive. A more general way of rounding off numbers is to use the built-in round function which rounds a float off to the nearest whole value. >>> round(3.14) 3.0 >>> round(-3.14) -3.0 >>> round(3.5) 4.0 >>> round(-3.5) -4.0 >>> int(round(-3.14)) -3 Notice that round returns a float. The last example shows how the result can then be turned into an int value, if necessary, by using int().
3.7 Exercises 1. Show the result of evaluating each expression. Be sure that the value is in the proper form to indicate its type (int, long int, or float). If the expression is illegal, explain why. (a) 4.0 / 10.0 + 3.5 * 2 (b) 10 % 4 + 6 / 2 (c) abs(4 - 20 / 3) ** 3 (d) sqrt(4.5 - 5.0) + 7 * 3 (e) 3 * 10 / 3 + 10 % 3 (f) 3L ** 3 2. Translate each of the following mathematical expressions into an equivalent Python expression. You may assume that the math library has been imported (via import math). (a) 3 (b) (c) (d) (e)
nn 1 2 4π r2
r cos a
y2 y1 x2 x1
CHAPTER 3. COMPUTING WITH NUMBERS
3. Show the list of numbers that would be generated by each of the following range expressions. (a) range(5) (b) range(3, 10) (c) range(4, 13, 3) (d) range(15, 5, -2) (e) range(5, 3) 4. Show the output that would be generated by each of the following program fragments. (a) for i in range(1, 11): print i*i (b) for i in [1,3,5,7,9]: print i, ":", i**3 print i (c) x = 2 y = 10 for j in range(0, y, x): print j, print x + y print "done" (d) ans = 0 for i in range(1, 11): ans = ans + i*i print i print ans 5. Write a program to calculate the volume and surface area of a sphere from its radius, given as input. Here are some formulas that might be useful: V 4 3π r 3 A 4π r2
6. Write a program that calculates the cost per square inch of a circular pizza, given its diameter and price. A π r2 7. Write a program that determines the molecular weight of a hydrocarbon based on the number of hydrogen, carbon, and oxygen atoms. You should use the following weights: Atom H C O
Weight (grams / mole) 1.0079 12.011 15.9994
8. Write a program that determines the distance to a lighting strike based on the time elapsed between the flash and the sound of thunder. The speed of sound is approximately 1100 ft/sec and 1 mile is 5280 ft. 9. The Konditorei coffee shop sells coffee at $10.50 a pound plus the cost of shipping. Each order ships for $0.86 per pound + $1.50 fixed cost for overhead. Write a program that calculates the cost of an order. 10. Two points in a plane are specified using the coordinates (x1,y1) and (x2,y2). Write a program that y1 calculates the slope of a line through two (non-vertical) points entered by the user. m y2 x2 x1
11. Write a program that accepts two points (see previous problem) and determines the distance between x2 x1 2 y2 y1 2 them. d
12. The Gregorian Epact is the number of days between Jan. 1st and the previous 1st quarter moon phase. This value is used to figure out the date of Easter. It is calculated by these formulas (using int arith8 C 4 C 8C 13 25 11 year%19 %30 Write a program metic): C year 100 epact that prompts the user for a 4-digit year and then outputs the value of the epact.
13. Write a program to calculate the area of a triangle given the length of its three sides a, b, and c. s a 2b c A ss a s b s c
14. Write a program to determine the length of a ladder required to reach a given height when leaned against a house. The height and angle of the ladder are given as inputs. len sinheight angle 15. Write a program to find the sum of the first n natural numbers, where the value of n is provided by the user. 16. Write a program to find the sum of the squares for the first n natural numbers. 17. Write a program to sum a series of numbers entered by the user. The program should first prompt the user for how many numbers are to be summed. It should then input each of the numbers and print a total sum. 18. Write a program that finds the average of a series of numbers entered by the user. As in the previous problem, the program will first ask the user how many numbers there are. Note: the average should always be a float, even if the user inputs are all ints. 19. Write a program that approximates the value of π by summing the terms of this series: 4 1 4 3 4 5 4 7 4 9 4 11 The program should prompt the user for n, the number of terms to sum and then output the sum of the first n terms of this series.
20. A Fibonacci sequence is a sequence of numbers where each successive number is the sum of the previous two. The classic Fibonacci sequence begins: 1, 1, 2, 3, 5, 8, 13, . Write a program that computes the nth Fibonacci number where n is a value input by the user. For example, if n = 6, then the result is 8. Note: Fibonacci numbers grow very rapidly; your program should be able to handle very large numbers. 21. You have seen that the math library contains a function that computes the square root of numbers. In this exercise, you are to write your own algorithm for computing square roots. One way to solve this problem is to use a guess-and-check approach. You first guess what the square root might be and then see how close your guess is. You can use this information to make another guess and continue guessing until you have found the square root (or a close approximation to it). One particularly good way of making guesses is to use Newton’s method. Suppose x is the number we want the root of, and guess is the current guessed answer. The guess can be improved by using
x guess guess 2
as the next guess.
Write a program that implements Newton’s method. The program should prompt the user for the value to find the square root of (x) and the number of times to improve the guess. Starting with a guess value of x/2, your program should loop the specified number of times applying Newton’s method and report the final value of guess. You might also print out the value of math.sqrt(x) for comparison.
CHAPTER 3. COMPUTING WITH NUMBERS
Computing with Strings So far, we have been discussing programs designed to manipulate numbers. These days we know that computers are also useful for working with other kinds of data. In fact, the most common use for most personal computers is word processing. The data in this case is text. Text is represented in programs by the string data type, which is the subject of this chapter.
4.1 The String Data Type A string is a sequence of characters. In Chapter 2 you learned that a string literal is a sequence of characters in quotations. Python also allows strings to be delimited by single quotes (apostrophes). There’s no difference— just be sure to use a matching set. Strings can be stored in variables, just like numbers. Here are some examples illustrating these two forms of string literals. >>> str1 = "Hello" >>> str2 = ’spam’ >>> print str1, str2 Hello spam >>> type(str1) >>> type(str2) You already know how to print strings. Some programs also need to get string input from the user (e.g., a name). Getting string-valued input requires a bit of care. Remember that the input statement treats whatever the user types as an expression to be evaluated. Consider the following interaction. >>> firstName = input("Please Please enter your name: John Traceback (innermost last): File "", line 1, firstName = input("Please File "", line 0, in NameError: John
enter your name: ")
in ? enter your name: ") ?
Something has gone wrong here. Can you see what the problem is? Remember, an input statement is just a delayed expression. When I entered the name, “John”, this had the exact same effect as executing this assignment statement: firstName = John This statement says, “look up the value of the variable John and store that value in firstName.” Since John was never given a value, Python cannot find any variable with that name and responds with a NameError. One way to fix this problem is to type quotes around a string input so that it evaluates as a string literal. 39
CHAPTER 4. COMPUTING WITH STRINGS
>>> firstName = input("Please enter your name: ") Please enter your name: "John" >>> print "Hello", firstName Hello John This works, but it is not a very satisfactory solution. We shouldn’t have to burden the users of our programs with details like typing quotes around their names. Python provides a better mechanism. The raw input function is exactly like input except it does not evaluate the expression that the user types. The input is simply handed to the program as a string of text. Revisiting our example, here is how it looks with raw input: >>> firstName = raw_input("Please enter your name: ") Please enter your name: John >>> print "Hello", firstName Hello John Notice that this example works as expected without having to type quotes around the input. If you want to get textual input from the user, raw input is the way to do it. So far, we have seen how to get strings as input, assign them to variables and print them out. That’s enough to write a parrot program, but not to do any serious text-based computing. For that, we need some string operations. The rest of this section takes you on a tour of the more important Python string operations. In the following section, we’ll put these ideas to work in some example programs. While the idea of numeric operations may be old hat to you from your math studies, you may not have thought about string operations before. What kinds of things can we do with strings? For starters, remember what a string is: a sequence of characters. One thing we might want to do is access the individual characters that make up the string. In Python, this can be done through the operation of indexing. We can think of the positions in a string as being numbered, starting from the left with 0. Figure 4.1
Figure 4.1: Indexing of the string ”Hello Bob” illustrates with the string “Hello Bob.” Indexing is used in string expressions to access a specific character position in the string. The general form for indexing is . The value of the expression determines which character is selected from the string. Here are some interactive indexing examples: >>> >>> ’H’ >>> H l >>> >>> B
greet = "Hello Bob" greet print greet, greet, greet o x = 8 print greet[x-2]
Notice that, in a string of n characters, the last character is at position n 1, because the indexes start at 0. Indexing returns a string containing a single character from a larger string. It is also possible to access a contiguous sequence of characters or substring from a string. In Python, this is accomplished through an operation called slicing. You can think of slicing as a way of indexing a range of positions in the string. Slicing takes the form string [ start : end ]. Both start and end should be int-valued expressions. A slice produces the substring starting at the position given by start and running up to, but not including, position end. Continuing with our interactive example, here are some slices.
4.2. SIMPLE STRING PROCESSING
>>> greet[0:3] ’Hel’ >>> greet[5:9] ’ Bob’ >>> greet[:5] ’Hello’ >>> greet[5:] ’ Bob’ >>> greet[:] ’Hello Bob’ The last three examples show that if either expression is missing, the start and end of the string are the assumed defaults. The final expression actually hands back the entire string. Indexing and slicing are useful operations for chopping strings into smaller pieces. The string data type also supports operations for putting strings together. Two handy operators are concatenation (+) and repetition (*). Concatenation builds a string by “gluing” two strings together. Repetition builds a string by multiple concatenations of a string with itself. Another useful function is len, which tells how many characters are in a string. Here are some examples: >>> "spam" + "eggs" ’spameggs’ >>> "Spam" + "And" + "Eggs" ’SpamAndEggs’ >>> 3 * "spam" ’spamspamspam’ >>> "spam" * 5 ’spamspamspamspamspam’ >>> (3 * "spam") + ("eggs" * 5) ’spamspamspameggseggseggseggseggs’ >>> len("spam") 4 >>> len("SpamAndEggs") 11 >>> These basic string operations are summarized in Table 4.1. Operator + * string [ ] len( string ) string [ : ]
Meaning Concatenation Repetition Indexing length slicing
Table 4.1: Python string operations
4.2 Simple String Processing Now that you have an idea what string operations can do, we’re ready to write some programs. Our first example is a program to compute the usernames for a computer system. Many computer systems use a username and password combination to authenticate system users. The system administrator must assign a unique username to each user. Often, usernames are derived from the user’s actual name. One scheme for generating usernames is to use the user’s first initial followed by up
CHAPTER 4. COMPUTING WITH STRINGS
to seven letters of the user’s last name. Using this method, the username for Elmer Thudpucker would be “ethudpuc,” and John Smith would just be “jsmith.” We want to write a program that reads a person’s name and computes the corresponding username. Our program will follow the basic input-process-output pattern. The result is simple enough that we can skip the algorithm development and jump right to the code. The outline of the algorithm is included as comments in the final program. # username.py # Simple string processing program to generate usernames. def main(): print "This program generates computer usernames." print # get user’s first and last names first = raw_input("Please enter your first name (all lowercase): ") last = raw_input("Please enter your last name (all lowercase): ") # concatenate first initial with 7 chars of the last name. uname = first + last[:7] # output the username print "Your username is:", uname main() This program first uses raw input to get strings from the user. Then indexing, slicing, and concatenation are combined to produce the username. Here’s an example run. This program generates computer usernames. Please enter your first name (all lowercase): elmer Please enter your last name (all lowercase): thudpucker Your username is: ethudpuc As you can see, computing with strings is very similar to computing with numbers. Here is another problem that we can solve with string operations. Suppose we want to print the abbreviation of the month that corresponds to a given month number. The input to the program is an int that represents a month number (1–12), and the output is the abbreviation for the corresponding month. For example, if the input is 3, then the output should be Mar, for March. At first, it might seem that this program is beyond your current ability. Experienced programmers recognize that this is a decision problem. That is, we have to decide which of 12 different outputs is appropriate, based on the number given by the user. We will not cover decision structures until later; however, we can write the program now by some clever use of string slicing. The basic idea is to store all the month names in a big string. months = "JanFebMarAprMayJunJulAugSepOctNovDec" We can lookup a particular month by slicing out the appropriate substring. The trick is computing where to slice. Since each month is represented by three letters, if we knew where a given month started in the string, we could easily extract the abbreviation. monthAbbrev = months[pos:pos+3] This would get us the substring of length three that starts in the position indicated by pos. How do we compute this position? Let’s try a few examples and see what we find. Remember that string indexing starts at 0.
4.3. STRINGS AND SECRET CODES month Jan Feb Mar Apr
43 number 1 2 3 4
position 0 3 6 9
Of course, the positions all turn out to be multiples of 3. To get the correct multiple, we just subtract 1 from the month number and then multiply by 3. So for 1 we get 1 1 3 0 3 0 and for 12 we have 12 1 3 11 3 33 Now we’re ready to code the program. Again, the final result is short and sweet; the comments document the algorithm we’ve developed.
# month.py # A program to print the abbreviation of a month, given its number def main(): # months is used as a lookup table months = "JanFebMarAprMayJunJulAugSepOctNovDec" n = input("Enter a month number (1-12): ") # compute starting position of month n in months pos = (n-1) * 3 # Grab the appropriate slice from months monthAbbrev = months[pos:pos+3] # print the result print "The month abbreviation is", monthAbbrev + "." main() Notice the last line of this program uses string concatenation to put a period at the end of the month abbreviation. Here is a sample of program output. Enter a month number (1-12): 4 The month abbreviation is Apr.
4.3 Strings and Secret Codes 4.3.1 String Representation Hopefully, you are starting to get the hang of computing with textual (string) data. However, you might still be wondering how computers actually manipulate strings. In the previous chapter, you saw how computers store numbers in binary notation (sequences of zeros and ones); the computer CPU contains circuitry to do arithmetic with these representations. Textual information is represented in exactly the same way. Underneath, when the computer is manipulating text, it is really no different from number crunching. To understand this, you might think in terms of messages and secret codes. Consider the age-old grade school dilemma. You are sitting in class and want to pass a note to a friend across the room. Unfortunately, the note must pass through the hands, and in front of the curious eyes, of many classmates before it reaches its final destination. And, of course, there is always the risk that the note could fall into enemy hands (the teacher’s). So you and your friend need to design a scheme for encoding the contents of your message. One approach is to simply turn the message into a sequence of numbers. You could choose a number to correspond to each letter of the alphabet and use the numbers in place of letters. Without too much
CHAPTER 4. COMPUTING WITH STRINGS
imagination, you might use the numbers 1-26 to represent the letters a–z. Instead of the word “sourpuss,” you would write “18, 14, 20, 17, 15, 20, 18, 18.” To those who don’t know the code, this looks like a meaningless string of numbers. For you and your friend, however, it represents a word. This is how a computer represents strings. Each character is translated into a number, and the entire string is stored as a sequence of (binary) numbers in computer memory. It doesn’t really matter what number is used to represent any given character as long as the computer is consistent about the encoding/decoding process. In the early days of computing, different designers and manufacturers used different encodings. You can imagine what a headache this was for people transferring data between different systems. Consider the situation that would result if, say, PCs and MacIntosh computers each used their own encoding. If you type a term paper on a PC and save it as a text file, the characters in your paper are represented as a certain sequence of numbers. Then if the file was read into your instructor’s MacIntosh computer, the numbers would be displayed on the screen as different characters from the ones you typed. The result would look like gibberish! To avoid this sort of problem, computer systems today use industry standard encodings. One important standard is called ASCII (American Standard Code for Information Interchange). ASCII uses the numbers 0 through 127 to represent the characters typically found on an (American) computer keyboard, as well as certain special values known as control codes that are used to coordinate the sending and receiving of information. For example, the capital letters A–Z are represented by the values 65–90, and the lowercase versions have codes 97–122. One problem with the ASCII encoding, as its name implies, is that it is American-centric. It does not have symbols that are needed in many other languages. Extended ASCII encodings have been developed by the International Standards Organization to remedy this situation. Most modern systems are moving to support of UniCode a much larger standard that includes support for the characters of all written languages. Newer versions of Python include support for UniCode as well as ASCII. Python provides a couple built-in functions that allow us to switch back and forth between characters and the numeric values used to represent them in strings. The ord function returns the numeric (“ordinal”) code of a single-character string, while chr goes the other direction. Here are some interactive examples: >>> 97 >>> 65 >>> ’a’ >>> ’Z’
ord("a") ord("A") chr(97) chr(90)
4.3.2 Programming an Encoder Let’s return to the note-passing example. Using the Python ord and chr functions, we can write some simple programs that automate the process of turning messages into strings of numbers and back again. The algorithm for encoding the message is simple. get the message to encode for each character in the message: print the letter number of the character Getting the message from the user is easy, a raw input will take care of that for us. message = raw_input("Please enter the message to encode: ") Implementing the loop requires a bit more effort. We need to do something for each character of the message. Recall that a for loop iterates over a sequence of objects. Since a string is a kind of sequence, we can just use a for loop to run-through all the characters of the message. for ch in message:
4.3. STRINGS AND SECRET CODES
Finally, we need to convert each character to a number. The simplest approach is to use the ASCII number (provided by ord) for each character in the message. Here is the final program for encoding the message: # text2numbers.py # A program to convert a textual message into a sequence of # numbers, utlilizing the underlying ASCII encoding. def main(): print "This program converts a textual message into a sequence" print "of numbers representing the ASCII encoding of the message." print # Get the message to encode message = raw_input("Please enter the message to encode: ") print print "Here are the ASCII codes:" # Loop through the message and print out the ASCII values for ch in message: print ord(ch), # use comma to print all on one line. print main() We can use the program to encode important messages. This program converts a textual message into a sequence of numbers representing the ASCII encoding of the message. Please enter the message to encode: What a Sourpuss! Here are the ASCII codes: 87 104 97 116 32 97 32 83 111 117 114 112 117 115 115 33 One thing to notice about this result is that even the space character has a corresponding ASCII code. It is represented by the value 32.
4.3.3 Programming a Decoder Now that we have a program to turn a message into a sequence of numbers, it would be nice if our friend on the other end had a similar program to turn the numbers back into a readable message. Let’s solve that problem next. Our decoder program will prompt the user for a sequence of numbers representing ASCII codes and then print out the text message corresponding to those codes. This program presents us with a couple of challenges; we’ll address these as we go along. The overall outline of the decoder program looks very similar to the encoder program. One change in structure is that the decoding version will collect the characters of the message in a string and print out the entire message at the end of the program. To do this, we need to use an accumulator variable, a pattern we saw in the factorial program from the previous chapter. Here is the decoding algorithm: get the sequence of numbers to decode message = "" for each number in the input: convert the number to the appropriate character
CHAPTER 4. COMPUTING WITH STRINGS
add the character to the end of message print the message Before the loop, the accumulator variable message is initialized to be an empty string, that is a string that contains no characters (""). Each time through the loop a number from the input is converted into an appropriate character and appended to the end of the message constructed so far. The algorithm seems simple enough, but even the first step presents us with a problem. How exactly do we get the sequence of numbers to decode? We don’t even know how many numbers there will be. To solve this problem, we are going to rely on some more string manipulation operations. First, we will read the entire sequence of numbers as a single string using raw input. Then we will split the big string into a sequence of smaller strings, each of which represents one of the numbers. Finally, we can iterate through the list of smaller strings, convert each into a number, and use that number to produce the corresponding ASCII character. Here is the complete algorithm: get the sequence of numbers as a string, inString split inString into a sequence of smaller strings message = "" for each of the smaller strings: change the string of digits into the number it represents append the ASCII character for that number to message print message This looks complicated, but Python provides some functions that do just what we need. We saw in Chapter 3 that Python provides a standard math library containing useful functions for computing with numbers. Similarly, the string library contains many functions that are useful in stringmanipulation programs. For our decoder, we will make use of the split function. This function is used to split a string into a sequence of substrings. By default, it will split the string wherever a space occurs. Here’s an example: >>> import string >>> string.split("Hello string library!") [’Hello’, ’string’, ’library!’] You can see how split has turned the original string "Hello string library!" into a list of three strings: "Hello", "string" and "library!". By the way, the split function can be used to split a string at places other than spaces by supplying the character to split on as a second parameter. For example, if we have a string of numbers separated by commas, we could split on the commas. >>> string.split("32,24,25,57", ",") [’32’, ’24’, ’25’, ’57’] Since our decoder program should accept the same format that was produced by the encoder program, namely a sequence of numbers with spaces between, the default version of split works nicely. >>> string.split("87 104 97 116 32 97 32 83 111 117 114 112 117 115 115 33") [’87’, ’104’, ’97’, ’116’, ’32’, ’97’, ’32’, ’83’, ’111’, ’117’, ’114’, ’112’, ’117’, ’115’, ’115’, ’33’] Notice that the resulting list is not a sequence of numbers, it is a sequence of strings. It just so happens these strings contain only digits and could be interpreted as numbers. All that we need now is a way of converting a string containing digits into a Python number. One way to accomplish this is with the Python eval function. This function takes any string and evaluates it as if it were a Python expression. Here are some interactive examples of eval: >>> numStr = "500" >>> eval(numStr) 500
4.3. STRINGS AND SECRET CODES
>>> eval("345.67") 345.67 >>> eval("3+4") 7 >>> x = 3.5 >>> y = 4.7 >>> eval("x * y") 16.45 >>> x = eval(raw_input("Enter a number ")) Enter a number 3.14 >>> print x 3.14 The last pair of statements shows that the eval of a raw input produces exactly what we would expect from an input expression. Remember, input evaluates what the user types, and eval evaluates whatever string it is given. Using split and eval we can write our decoder program. # numbers2text.py # A program to convert a sequence of ASCII numbers into # a string of text. import string
# include string library for the split function.
def main(): print "This program converts a sequence of ASCII numbers into" print "the string of text that it represents." print # Get the message to encode inString = raw_input("Please enter the ASCII-encoded message: ") # Loop through each substring and build ASCII message message = "" for numStr in string.split(inString): asciiNum = eval(numStr) # convert digit string to a number message = message + chr(asciiNum) # append character to message print "The decoded message is:", message main() Study this program a bit, and you should be able to understand exactly how it accomplishes its task. The heart of the program is the loop. for numStr in string.split(inString): asciiNum = eval(numStr) message = message + chr(asciiNum) The split function produces a sequence of strings, and numStr takes on each successive (sub)string in the sequence. I called the loop variable numStr to emphasize that its value is a string of digits that represents some number. Each time through the loop, the next substring is converted to a number by evaling it. This number is converted to the corresponding ASCII character via chr and appended to the end of the accumulator, message. When the loop is finished, every number in inString has been processed and message contains the decoded text. Here is an example of the program in action:
CHAPTER 4. COMPUTING WITH STRINGS
>>> import numbers2text This program converts a sequence of ASCII numbers into the string of text that it represents. Please enter the ASCII-encoded message: 83 116 114 105 110 103 115 32 97 114 101 32 70 117 110 33 The decoded message is: Strings are Fun!
4.3.4 Other String Operations Now we have a couple programs that can encode and decode messages as sequences of ASCII values. These programs turned out to be quite simple due to the power both of Python’s string data type and its built-in operations as well as extensions that can be found in the string library. Python is a very good language for writing programs that manipulate textual data. Table 4.2 lists some of the other useful functions of the string library. Note that many of these functions, like split, accept additional parameters to customize their operation. Python also has a number of other standard libraries for text-processing that are not covered here. You can consult the online documentation or a Python reference to find out more. Function capitalize(s) capwords(s) center(s, width) count(s, sub) find(s, sub) join(list) ljust(s, width) lower(s) lstrip(s) replace(s,oldsub,newsub) rfind(s, sub) rjust(s,width) rstrip(s) split(s) upper(s)
Meaning Copy of s with only the first character capitalized Copy of s with first character of each word capitalized Center s in a field of given width Count the number of occurrences of sub in s Find the first position where sub occurs in s Concatenate list of strings into one large string Like center, but s is left-justified Copy of s in all lowercase characters Copy of s with leading whitespace removed Replace all occurrences of oldsub in s with newsub Like find, but returns the rightmost position Like center, but s is right-justified Copy of s with trailing whitespace removed Split s into a list of substrings (see text). Copy of s with all characters converted to upper case
Table 4.2: Some components of the Python string library
4.3.5 From Encoding to Encryption We have looked at how computers represent strings as a sort of encoding problem. Each character in a string is represented by a number that is stored in the computer in a binary representation. You should realize that there is nothing really secret about this code at all. In fact, we are simply using an industry-standard mapping of characters into numbers. Anyone with a little knowledge of computer science would be able to crack our code with very little effort. The process of encoding information for the purpose of keeping it secret or transmitting it privately is called encryption. The study of encryption methods is an increasingly important subfield of mathematics and computer science known as cryptography. For example, if you shop over the Internet, it is important that your personal information such as social security number or credit card number is transmitted using encodings that keep it safe from potential eavesdroppers on the network. Our simple encoding/decoding programs use a very weak form of encryption known as a substitution cipher. Each character of the original message, called the plaintext, is replaced by a corresponding symbol (in our case a number) from a cipher alphabet. The resulting code is called the ciphertext .
4.4. OUTPUT AS STRING MANIPULATION
Even if our cipher were not based on the well-known ASCII encoding, it would still be easy to discover the original message. Since each letter is always encoded by the same symbol, a code-breaker could use statistical information about the frequency of various letters and some simple trial and error testing to discover the original message. Such simple encryption methods may be sufficient for grade-school note passing, but they are certainly not up to the task of securing communication over global networks. Modern approaches to encryption start by translating a message into numbers, much like our encoding program. Then sophisticated mathematical algorithms are employed to transform these numbers into other numbers. Usually, the transformation is based on combining the message with some other special value called the key. In order to decrypt the message, the party on the receiving end needs to have the appropriate key so that the encoding can be reversed to recover the original message. Encryption approaches come in two flavors: private key and public key. In a private key system the same key is used for encrypting and decrypting messages. All parties that wish to communicate need to know the key, but it must be kept secret from the outside world. This is usual system that people think of when considering secret codes. In public key systems, there are separate but related keys for encrypting and decrypting. Knowing the encryption key does not allow you to decrypt messages or discover the decryption key. In a public key system, the encryption key can be made publicly available, while the decryption key is kept private. Anyone can safely send a message using the public key for encryption. Only the party holding the decryption key will be able to decipher it. For example, a secure web site can send your web browser its public key, and the browser can use it to encode your credit card information before sending it on the Internet. Then only the company that is requesting the information will be able to decrypt and read it using the proper private key.
4.4 Output as String Manipulation Even programs that we may not view as primarily doing text-manipulation often need to make use of string operations. For example, a program to do a financial analysis must produce a nicely formatted report of the results. Much of this report will be in the form of text that is used to label and explain numbers, charts, tables and figures. In this section, we’ll look at techniques for generating nicely formatted text-based output.
4.4.1 Converting Numbers to Strings In the ASCII decoding program, we used the eval function to convert from a string data type into a numeric data type. Recall that eval evaluates a string as a Python expression. It is very general and can be used to turn strings into nearly any other Python data type. It is also possible to go the other direction and turn many Python data types into strings using the str function. Here are a couple of simple examples. >>> str(500) ’500’ >>> value = 3.14 >>> str(value) ’3.14’ >>> print "The value is", str(value) + "." The value is 3.14. Notice particularly the last example. By turning value into a string, we can use string concatenation to put a period at the end of a sentence. If we didn’t first turn value into a string, Python would interpret the + as a numerical operation and produce an error, because “.” is not a number. Adding eval and str to the type-conversion operations discussed in Chapter 3, we now have a complete set of operations for converting values among various Python data types. Table 4.3 summarizes these five Python type conversion functions. One common reason for converting a number into a string is so that string operations can be used to control the way the value is printed. For example, in the factorial program from last chapter we saw that Python long ints have the letter “L” appended to them. In versions of Python prior to 2.0, the “L” showed up
CHAPTER 4. COMPUTING WITH STRINGS
50 Function float() int() long( str() eval()
Meaning Convert expr to a floating point value. Convert expr to an integer value. Convert expr to a long integer value. Return a string representation of expr. Evaluate string as an expression.
Table 4.3: Type Conversion Functions
whenever a long int was printed. However, it is easy to remove this artifact using some straightforward string manipulation. factStr = str(fact) print factStr[0:len(factStr)-1] Can you see how this code turns the long int into a string and then uses slicing to remove the “L?” The print statement prints every position in the string up to, but not including, the final “L,” which is in position length - 1. As an aside, Python also allows sequences to be indexed from the back by using negative numbers as indexes. Thus -1 is the last position in a string, -2 is the second to last, etc. Using this convention, we can slice off the last character without first computing the length of the string. print str(fact)[:-1] This version uses str to turn fact into a string and then immediately slices it “in place” from the beginning (0 is the default start) up to, but not including, the last position.
4.4.2 String Formatting As you have seen, basic string operations can be used to build nicely formatted output. This technique is useful for simple formatting, but building up a complex output through slicing and concatenation of smaller strings can be tedious. Python provides a powerful string formatting operation that makes the job much easier. Let’s start with a simple example. Here is a run of the change counting program from last chapter. Change Counter Please enter the count of each coin type. How many quarters do you have? 6 How many dimes do you have? 0 How many nickels do you have? 0 How many pennies do you have? 0 The total value of your change is 1.5 Notice that the final value is given as a fraction with only one decimal place. This looks funny, since we expect the output to be something like $1.50. We can fix this problem by changing the very last line of the program as follows. print "The total value of your change is $%0.2f" % (total) Now the program prints this message: The total value of your change is $1.50 Let’s try to make some sense of this. The percent sign % is Python’s string formatting operator. In general, the string formatting operator is used like this: % ()
4.4. OUTPUT AS STRING MANIPULATION
Percent signs inside the template-string mark “slots” into which the values are inserted. There must be exactly one slot for each value. Each of the slots is described by a format specifier that tells Python how the value for that slot should appear. Returning to the example, the template contains a single specifier at the end: %0.2f. The value of total will be inserted into the template in place of the specifier. The specifier also tells Python that total is a floating point number that should be rounded to two decimal places. To understand the formatting, we need to look at the structure of the specifier. A formatting specifier has this general form: %. The specifier starts with a % and ends with a character that indicates the data type of the value being inserted. We will use three different format types: decimal, float, and string. Decimal mode is used to display ints as base-10 numbers. (Python allows ints to be printed using a number of different bases; we will only use the normal decimal representation.) Float and string formats are obviously used for the corresponding data types. The width and precision portions of a specifier are optional. If present, width tells how many spaces to use in displaying the value. If a value requires more room than is given in width, Python will just expand the width so that the value fits. You can use a 0 width to indicate “use as much space as needed.” Precision is used with floating point values to indicate the desired number of digits after the decimal. The example specifier %0.2f tells Python to insert a floating point value using as much space as necessary and rounding it to two decimal places. The easiest way to get the hang of formatting is just to play around with some examples in the interactive environment. >>> "Hello %s %s, you may have won $%d!" % ("Mr.", "Smith", 10000) ’Hello Mr. Smith, you may have already won $10000!’ >>> ’This int, %5d, was placed in a field of width 5’ % (7) ’This int, 7, was placed in a field of width 5’ >>> ’This int, %10d, was placed in a field of width 10’ % (7) ’This int, 7, was placed in a field of width 10’ >>> ’This float, %10.5f, has width 10 and precision 5.’ % (3.1415926) ’This float, 3.14159, has width 10 and precision 5.’ >>> ’This float, %0.5f, has width 0 and precision 5.’ % (3.1415926) ’This float, 3.14159, has width 0 and precision 5.’ >>> "Compare %f and %0.20f" % (3.14, 3.14) ’Compare 3.140000 and 3.14000000000000012434’ A couple points are worth noting here. If the width in the specifier is larger than needed, the value is right-justified in the field by default. You can left-justify the value in the field by preceding the width with a minus sign (e.g., %-8.3f). The last example shows that if you print enough digits of a floating point number, you will almost always find a “surprise.” The computer can’t represent 3.14 exactly as a floating point number. The closest value it can represent is ever so slightly larger than 3.14. If not given an explicit precision, Python will print the number out to a few decimal places. The slight extra extra amount shows up if you print lots of digits. Generally, Python only displays a closely rounded version of a float. Using explicit formatting allows you to see the full result down to the last bit.
4.4.3 Better Change Counter Let’s close our formatting discussion with one more example program. Given what you have learned about floating point numbers, you might be a little uneasy about using them to represent money.
CHAPTER 4. COMPUTING WITH STRINGS
Suppose you are writing a computer system for a bank. Your customers would not be too happy to learn that a check went through for an amount “very close to $107.56.” They want to know that the bank is keeping precise track of their money. Even though the amount of error in a given value is very small, the small errors can be compounded when doing lots of calculations, and the resulting error could add up to some real cash. That’s not a satisfactory way of doing business. A better approach would be to make sure that our program used exact values to represent money. We can do that by keeping track of the money in cents and using an int (or long int) to store it. We can then convert this into dollars and cents in the output step. If total represents the value in cents, then we can get the number of dollars by total / 100 and the cents from total % 100. Both of these are integer calculations and, hence, will give us exact results. Here is the updated program: # change2.py # A program to calculate the value of some change in dollars # This version represents the total cash in cents. def main(): print "Change Counter" print print "Please enter the count of each coin type." quarters = input("Quarters: ") dimes = input("Dimes: ") nickels = input("Nickels: ") pennies = input("Pennies: ") total = quarters * 25 + dimes * 10 + nickels * 5 + pennies print print "The total value of your change is $%d.%02d" \ % (total/100, total%100) main() I have split the final print statement across two lines. Normally a statement ends at the end of the line. Sometimes it is nicer to break a long statement into smaller pieces. A backslash at the end of a line is one way to indicate that a statement is continued on the following line. Notice that the backslash must appear outside of the quotes; otherwise, it would be considered part of the string literal. The string formatting in the print statement contains two slots, one for dollars as an int and one for cents as an int. This example also illustrates one additional twist on format specifiers. The value of cents is printed with the specifier %02d. The zero in front of the width tells Python to pad the field (if necessary) with zeroes instead of spaces. This ensures that a value like 10 dollars and 5 cents prints as $10.05 rather than $10. 5.
4.5 File Processing I began the chapter with a reference to word-processing as an application of the string data type. One critical feature of any word processing program is the ability to store and retrieve documents as files on disk. In this section, we’ll take a look at file input and output, which, as it turns out, is really just another form of string processing.
4.5.1 Multi-Line Strings Conceptually, a file is a sequence of data that is stored in secondary memory (usually on a disk drive). Files can contain any data type, but the easiest files to work with are those that contain text. Files of text have the advantage that they can be read and understood by humans, and they are easily created and edited using general-purpose text editors and word processors. In Python, text files can be very flexible, since it is easy to convert back and forth between strings and other types.
4.5. FILE PROCESSING
You can think of a text file as a (possibly long) string that happens to be stored on disk. Of course, a typical file generally contains more than a single line of text. A special character or sequence of characters is used to mark the end of each line. There are numerous conventions for end-of-line markers. Python uses a single character called newline as a marker. You can think of newline as the character produced when you press the Enter key on your keyboard. Although a newline is a single character, it is represented in Python (and many other computer languages) using the special notation ’ n’. Other special characters are represented using a similar notation (i.e., ’ t’ for Tab ). Let’s take a look at a concrete example. Suppose you type the following lines into a text editor exactly as shown here. Hello World Goodbye 32 When stored to a file, you get this sequence of characters. Hello\nWorld\n\nGoodbye 32\n Notice that the blank line becomes a bare newline in the resulting file/string. By the way, by embedding newline characters into output strings, you can produce multiple lines of output with a single print statement. Here is the example from above printed interactively. >>> print "Hello\nWorld\n\nGoodbye 32\n" Hello World Goodbye 32 >>> If you simply ask Python to evaluate a string containing newline characters, you will just get the embedded newline representation back again. >>>"Hello\nWorld\n\nGoodbye 32\n" ’Hello\nWorld\n\nGoodbye 32\n’ It’s only when a string is printed that the special characters affect how the string is displayed.
4.5.2 File Processing The exact details of file-processing differ substantially among programming languages, but virtually all languages share certain underlying file manipulation concepts. First, we need some way to associate a file on disk with a variable in a program. This process is called opening a file. Once a file has been opened, it is manipulated through the variable we assign to it. Second, we need a set of operations that can manipulate the file variable. At the very least, this includes operations that allow us to read the information from a file and write new information to a file. Typically, the reading and writing operations for text files are similar to the operations for text-based, interactive input and output. Finally, when we are finished with a file, it is closed. Closing a file makes sure that any bookkeeping that was necessary to maintain the correspondence between the file on disk and the file variable is finished up. For example, if you write information to a file variable, the changes might not show up on the disk version until the file has been closed. This idea of opening and closing files is closely related to how you might work with files in an application program like a word processor. However, the concepts are not exactly the same. When you open a file in a program like Microsoft Word, the file is actually read from the disk and stored into RAM. In programming
CHAPTER 4. COMPUTING WITH STRINGS
terminology, the file is opened for reading and the the contents of the file are then read into memory via file reading operations. At this point, the file is closed (again in the programming sense). As you “edit the file,” you are really making changes to data in memory, not the file itself. The changes will not show up in the file on the disk until you tell the application to “save” it. Saving a file also involves a multi-step process. First, the original file on the disk is reopened, this time in a mode that allows it to store information—the file on disk is opened for writing. Doing so actually erases the old contents of the file. File writing operations are then used to copy the current contents of the in-memory version into the new file on the disk. From your perspective, it appears that you have edited an existing file. From the program’s perspective, you have actually opened a file, read its contents into memory, closed the file, created a new file (having the same name), written the (modified) contents of memory into the new file, and closed the new file. Working with text files is easy in Python. The first step is to associate a file with a variable using the open function. = open(, ) Here name is a string that provides the name of the file on the disk. The mode parameter is either the string "r" or "w" depending on whether we intend to read from the file or write to the file. For example, to open a file on our disk called “numbers.dat” for reading, we could use a statement like the following. infile = open("numbers.dat", "r") Now we can use the variable infile to read the contents of numbers.dat from the disk. Python provides three related operations for reading information from a file: .read() .readline() .readlines() The read operation returns the entire contents of the file as a single string. If the file contains more than one line of text, the resulting string has embedded newline characters between the lines. Here’s an example program that prints the contents of a file to the screen. # printfile.py # Prints a file to the screen. def main(): fname = raw_input("Enter filename: ") infile = open(fname,’r’) data = infile.read() print data main() The program first prompts the user for a filename and then opens the file for reading through the variable infile. You could use any name for the variable, I used infile to emphasize that the file was being used for input. The entire contents of the file is then read as one large string and stored in the variable data. Printing data causes the contents to be displayed. The readline operation can be used to read one line from a file; that is, it reads all the characters up through the next newline character. Each time it is called, readline returns the next line from the file. This is analogous to raw input which reads characters interactively until the user hits the Enter key; each call to raw input get another line from the user. One thing to keep in mind, however, is that the string returned by readline will always end with a newline character, whereas raw input discards the newline character. As a quick example, this fragment of code prints out the first five lines of a file.
4.5. FILE PROCESSING
infile = open(someFile, ’r’) for i in range(5): line = infile.readline() print line[:-1] Notice the use of slicing to strip off the newline character at the end of the line. Since print automatically jumps to the next line (i.e., it outputs a newline), printing with the explicit newline at the end would put an extra blank line of output between the lines of the file. As an alternative to readline, when you want to loop through all the (remaining) lines of a file, you can use readlines. This operation returns a sequence of strings representing the lines of the file. Used with a for loop, it is a particularly handy way to process each line of a file. infile = open(someFile, ’r’) for line in infile.readlines(): # process the line here infile.close() Opening a file for writing prepares that file to receive data. If no file with the given name exists, a new file will be created. A word of warning: if a file with the given name does exist, Python will delete it and create a new, empty file. When writing to a file, make sure you do not clobber any files you will need later! Here is an example of opening a file for output. outfile = open("mydata.out", "w") We can put data into a file, using the write operation. .write() This is similar to print, except that write is a little less flexible. The write operation takes a single parameter, which must be a string, and writes that string to the file. If you want to start a new line in the file, you must explicitly provide the newline character. Here’s a silly example that writes two lines to a file. outfile = open("example.out", ’w’) count = 1 outfile.write("This is the first line\n") count = count + 1 outfile.write("This is line number %d" % (count)) outfile.close() Notice the use of string formatting to write out the value of the variable count. If you want to output something that is not a string, you must first convert it; the string formatting operator is often a handy way to do this. This code will produce a file on disk called “example.out” containing the following two lines: This is the first line This is line number 2 If “example.out” existed before executing this fragment, it’s old contents were destroyed.
4.5.3 Example Program: Batch Usernames To see how all these pieces fit together, let’s redo the username generation program. Our previous version created usernames interactively by having the user type in his or her name. If we were setting up accounts for a large number of users, the process would probably not be done interactively, but in batch mode. In batch processing, program input and output is done through files. Our new program is designed to process a file of names. Each line of the input file will contain the first and last names of a new user separated by one or more spaces. The program produces an output file containing a line for each generated username.
CHAPTER 4. COMPUTING WITH STRINGS
# userfile.py # Program to create a file of usernames in batch mode. import string def main(): print "This program creates a file of usernames from a" print "file of names." # get the file names infileName = raw_input("What file are the names in? ") outfileName = raw_input("What file should the usernames go in? ") # open the files infile = open(infileName, ’r’) outfile = open(outfileName, ’w’) # process each line of the input file for line in infile.readlines(): # get the first and last names from line first, last = string.split(line) # create the username uname = string.lower(first+last[:7]) # write it to the output file outfile.write(uname+’\n’) # close both files infile.close() outfile.close() print "Usernames have been written to", outfileName main() There are a few things worth noticing in this program. I have two files open at the same time, one for input (infile) and one for output (outfile). It’s not unusual for a program to operate on several files simultaneously. Also, when creating the username, I used the lower function from the string library. This ensures that the username is all lower case, even if the input names are mixed case. Finally, you should also notice the line that writes the username to the file. outfile.write(uname+’\n’) Concatenating the newline character is necessary to indicate the end of line. Without this, all of the usernames would run together in one giant line.
4.5.4 Coming Attraction: Objects Have you noticed anything strange about the syntax of the file processing examples? To apply an operation to a file, we use dot notation. For example, to read from infile we type infile.read(). This is different from the normal function application that we have used before. Afterall, to take the absolute value of a variable x, we type abs(x), not x.abs(). In Python, a file is an example of an object. Objects combine both data and operations together. An object’s operations, called methods, are invoked using the dot notation. That’s why the syntax looks a bit different.
For completeness, I should mention that strings are also objects in Python. If you have a relatively new version of Python (2.0 or later), you can use string methods in place of the string library functions that we discussed earlier. For example, myString.split() is equivalent to string.split(myString) If this object stuff sounds confusing right now, don’t worry; Chapter 5 is all about the power of objects (and pretty pictures, too).
4.6 Exercises 1. Given the initial statements: import string s1 = "spam" s2 = "ni!" Show the result of evaluating each of the following string expressions. (a) "The Knights who say, " + s2 (b) 3 * s1 + 2 * s2 (c) s1 (d) s1[1:3] (e) s1 + s2[:2] (f) s1 + s2[-1] (g) string.upper(s1) (h) string.ljust(string.upper(s2),4) * 3 2. Given the same initial statements as in the previous problem, show a Python expression that could construct each of the following results by performing string operations on s1 and s2. (a) "NI" (b) "ni!spamni!" (c) "Spam Ni!
(d) "span" (e) ["sp","m"] (f) "spm" 3. Show the output that would be generated by each of the following program fragments. (a) for ch in "aardvark": print ch (b) for w in string.split("Now is the winter of our discontent..."): print w (c) for w in string.split("Mississippi", "i"): print w,
CHAPTER 4. COMPUTING WITH STRINGS
(d) msg = "" for s in string.split("secret","e"): msg = msg + s print msg (e) msg = "" for ch in "secret": msg = msg + chr(ord(ch)+1) print msg 4. Show the string that would result from each of the following string formatting operations. If the operation is not legal, explain why. (a) "Looks like %s and %s for breakfast" % ("spam", "eggs") (b) "There is %d %s %d %s" % (1,"spam", 4, "you") (c) "Hello %s" % ("Suzie", "Programmer") (d) "%0.2f %0.2f" % (2.3, 2.3468) (e) "%7.5f %7.5f" % (2.3, 2.3468) (f) "Time left %02d:%05.2f" % (1, 37.374) (g) "%3d" % ("14") 5. Explain why public key encryption is more useful for securing communications on the Internet than private (shared) key encryption. 6. A certain CS professor gives 5-point quizzes that are graded on the scale 5-A, 4-B, 3-C, 2-D, 1-F, 0-F. Write a program that accepts a quiz score as an input and prints out the corresponding grade. 7. A certain CS professor gives 100-point exams that are graded on the scale 90–100:A, 80–89:B, 70– 79:C, 60–69:D, 60:F. Write a program that accepts an exam score as input and prints out the corresponding grade. 8. An acronym is a word formed by taking the first letters of the words in a phrase and making a word from them. For example, RAM is an acronym for “random access memory.” Write a program that allows the user to type in a phrase and outputs the acronym for that phrase. Note: the acronym should be all uppercase, even if the words in the phrase are not capitalized. 9. Numerologists claim to be able to determine a person’s character traits based on the “numeric value” of a name. The value of a name is determined by summing up the values of the letters of the name where ’a’ is 1, ’b’ is 2, ’c’ is 3 etc., up to ’z’ being 26. For example, the name “Zelle” would have the value 26 5 12 12 5 60 (which happens to be a very auspicious number, by the way). Write a program that calculates the numeric value of a single name provided as input.
10. Expand your solution to the previous problem to allow the calculation of a complete name such as “John Marvin Zelle” or “John Jacob Jingleheimer Smith.” The total value is just the sum of the numeric value for each name. 11. A Caesar cipher is a simple substitution cipher based on the idea of shifting each letter of the plaintext message a fixed number (called the key) of positions in the alphabet. For example, if the key value is 2, the word “Sourpuss” would be encoded as “Uqwtrwuu.” The original message can be recovered by “reencoding” it using the negative of the key. Write a program that can encode and decode Caesar ciphers. The input to the program will be a string of plaintext and the value of the key. The output will be an encoded message where each character in the original message is replaced by shifting it key characters in the ASCII character set. For example, if ch is a character in the string and key is the amount to shift, then the character that replaces ch can be calculated as: chr(ord(ch) + key).
12. One problem with the previous exercise is that it does not deal with the case when we “drop off the end” of the alphabet (or ASCII encodings). A true Caesar cipher does the shifting in a circular fashion where the next character after “z” is “a”. Modify your solution to the previous problem to make it circular. You may assume that the input consists only of letters and spaces. 13. Write a program that counts the number of words in a sentence entered by the user. 14. Write a program that calculates the average word length in a sentence entered by the user. 15. Write an improved version of the Chaos program from Chapter 1 that allows a user to input two initial values and the number of iterations and then prints a nicely formatted table showing how the values change over time. For example, if the starting values were .25 and .26 with 10 iterations, the table might look like this: index 0.25 0.26 ---------------------------1 0.731250 0.750360 2 0.766441 0.730547 3 0.698135 0.767707 4 0.821896 0.695499 5 0.570894 0.825942 6 0.955399 0.560671 7 0.166187 0.960644 8 0.540418 0.147447 9 0.968629 0.490255 10 0.118509 0.974630 16. Write an improved version of the future value program from Chapter 2. Your program will prompt the user for the amount of the investment, the annualized interest rate, and the number of years of the investment. The program will then output a nicely formatted table that tracks the value of the investment year by year. Your output might look something like this: Years Value ---------------0 $2000.00 1 $2200.00 2 $2420.00 3 $2662.00 4 $2928.20 5 $3221.02 6 $3542.12 7 $3897.43 17. Redo any of the previous programming problems to make them batch oriented (using text files for input and output). 18. Word count. A common utility on Unix/Linux systems is a small program called “wc.” This program analyzes a file to determine the number of lines, words, and characters contained therein. Write your own version of wc. The program should accept a file name as input and then print three numbers showing the count of lines, words, and characters in the file.
CHAPTER 4. COMPUTING WITH STRINGS
Objects and Graphics So far we have been writing programs that use the built-in Python data types for numbers and strings. We saw that each data type could represent a certain set of values, and each had a set of associated operations. Basically, we viewed the data as passive entities that were manipulated and combined via active operations. This is a traditional way to view computation. To build complex systems, however, it helps to take a richer view of the relationship between data and operations. Most modern computer programs are built using an object-oriented (OO) approach. Object orientation is not easily defined. It encompasses a number of principles for designing and implementing software, principles that we will return to numerous times throughout course of this book. This chapter provides a basic introduction to object concepts by way of some computer graphics.
5.1 The Object of Objects The basic idea of object-oriented development is to view a complex system as the interaction of simpler objects. The word objects is being used here in a specific technical sense. Part of the challenge of OO programming is figuring out the vocabulary. You can think of an OO object as a sort of active data type that combines both data and operations. To put it simply, objects know stuff (they contain data), and they can do stuff (they have operations). Objects interact by sending each other messages. A message is simply a request for an object to perform one of its operations. Consider a simple example. Suppose we want to develop a data processing system for a college or university. We will need to keep track of considerable information. For starters, we must keep records on the students who attend the school. Each student could be represented in the program as an object. A student object would contain certain data such as name, ID number, courses taken, campus address, home address, GPA, etc. Each student object would also be able to respond to certain requests. For example, to send out a mailing, we would need to print an address for each student. This task might be handled by a printCampusAddress operation. When a particular student object is sent the printCampusAddress message, it prints out its own address. To print out all the addresses, a program would loop through the collection of student objects and send each one in turn the printCampusAddress message. Objects may refer to other objects. In our example, each course in the college might also be represented by an object. Course objects would know things such as who the instructor is, what students are in the course, what the prerequisites are, and when and where the course meets. One example operation might be addStudent, which causes a student to be enrolled in the course. The student being enrolled would be represented by the appropriate student object. Instructors would be another kind of object, as well as rooms, and even times. You can see how successive refinement of these ideas could lead to a rather sophisticated model of the information structure of the college. As a beginning programmer, you’re probably not yet ready to tackle a college information system. For now, we’ll study objects in the context of some simple graphics programming. 61
CHAPTER 5. OBJECTS AND GRAPHICS
5.2 Graphics Programming Modern computer applications are not limited to the sort of textual input and output that we have been using so far. Most of the applications that you are familiar with probably have a so-called Graphical User Interface (GUI) that provides visual elements like windows, icons (representative pictures), buttons and menus. Interactive graphics programming can be very complicated; entire textbooks are devoted to the intricacies of graphics and graphical interfaces. Industrial-strength GUI applications are usually developed using a dedicated graphics programming framework. Python comes with its own standard GUI module called Tkinter. As GUI frameworks go, Tkinter is one of the simplest to use, and Python is great language for developing real-world GUIs. Even so, taking the time to learn Tkinter would detract from the more fundamental task of learning the principles of programming and design that are the focus of this book. To make learning easier, I have written a graphics library (graphics.py) for use with this book. This library is freely available as a Python module file1 and you are welcome to use it as you see fit. Using the library is as easy as placing a copy of the graphics.py file in the same folder as your graphics program(s). Alternatively, you can put graphics.py in the system directory where other Python libraries are stored so that it can be used from any folder on the system. The graphics library makes it easy to write simple graphics programs. As you do, you will be learning principles of object-oriented programming and computer graphics that can be applied in more sophisticated graphical programming environments. The details of the graphics module will be explored in later sections. Here we’ll concentrate on a basic hands-on introduction to whet your appetite. As usual, the best way to start learning new concepts is to roll up your sleeves and try out some examples. The first step is to import the graphics module. Assuming you have placed graphics.py in an appropriate place, you can import the graphics commands into an interactive Python session. >>> import graphics Next we need to create a place on the screen where the graphics will appear. That place is a graphics window or GraphWin, which is provided by the graphics module. >>> win = graphics.GraphWin() This command creates a new window on the screen. The window will have the title “Graphics Window.” The GraphWin may overlap your Python interpreter window, so you might have to resize the Python window to make both fully visible. Figure 5.1 shows an example screen view. The GraphWin is an object, and we have assigned it to the the variable called win. We can manipulate the window object through this variable, similar to the way that file objects are manipulated through file variables. For example, when we are finished with a window, we can destroy it. This is done by issuing the close command. >>> win.close() Typing this command causes the window to vanish from the screen. We will be working with quite a few commands from the graphics library, and it gets tedious having to type the graphics. notation every time we use one. Python has an alternative form of import that can help out. from graphics import * The from statement allows you to load specific definitions from a library module. You can either list the names of definitions to be imported or use an asterisk, as shown, to import everything defined in the module. The imported commands become directly available without having to preface them with the module name. After doing this import, we can create a GraphWin more simply. win = GraphWin() 1 See
Appendix A for information on how to obtain the graphics library and other supporting materials for this book.
5.2. GRAPHICS PROGRAMMING
Figure 5.1: Screen shot with a Python window and a GraphWin
All of the rest of the graphics examples will assume that the entire graphics module has been imported using from. Let’s try our hand at some drawing. A graphics window is actually a collection of tiny points called pixels (short for picture elements). By controlling the color of each pixel, we control what is displayed in the window. By default, a GraphWin is 200 pixels tall and 200 pixels wide. That means there are 40,000 pixels in the GraphWin. Drawing a picture by assigning a color to each individual pixel would be a daunting challenge. Instead, we will rely on a library of graphical objects. Each type of object does its own bookkeeping and knows how to draw itself into a GraphWin. The simplest object in the graphics module is a Point. In geometry, a point is a dimensionless location in space. A point is located by reference to a coordinate system. Our graphics object Point is similar; it can represent a location in a GraphWin. We define a point by supplying x and y coordinates x y . The x value represents the horizontal location of the point, and the y value represents the vertical. Traditionally, graphics programmers locate the point 0 0 in the upper-left corner of the window. Thus x values increase from left to right, and y values increase from top to bottom. In the default 200 x 200 GraphWin, the lower-right corner has the coordinates 199 199 . Drawing a Point sets the color of the corresponding pixel in the GraphWin. The default color for drawing is black. Here is a sample interaction with Python illustrating the use of Points.
The first line creates a Point located at 50 60 . After the Point has been created, its coordinate values can be accessed by the operations getX and getY. A Point is drawn into a window using the draw operation. In this example, two different point objects (p and p2) are created and drawn into the GraphWin called win. Figure 5.2 shows the resulting graphical output. In addition to points, the graphics library contains commands for drawing lines, circles, rectangles, ovals,
CHAPTER 5. OBJECTS AND GRAPHICS
Figure 5.2: Graphics window with two points drawn.
polygons and text. Each of these objects is created and drawn in a similar fashion. Here is a sample interaction to draw various shapes into a GraphWin. >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>>
#### Open a graphics window win = GraphWin(’Shapes’) #### Draw a red circle centered at point (100,100) with radius 30 center = Point(100,100) circ = Circle(center, 30) circ.setFill(’red’) circ.draw(win) #### Put a textual label in the center of the circle label = Text(center, "Red Circle") label.draw(win) #### Draw a square using a Rectangle object rect = Rectangle(Point(30,30), Point(70,70)) rect.draw(win) #### Draw a line segment using a Line object line = Line(Point(20,30), Point(180, 165)) line.draw(win) #### Draw an oval using the Oval object oval = Oval(Point(20,150), Point(180,199)) oval.draw(win)
Try to figure out what each of these statements does. If you type them in as shown, the final result will look like Figure 5.3.
5.3 Using Graphical Objects Some of the examples in the above interactions may look a bit strange to you. To really understand the graphics module, we need to take an object-oriented point of view. Recall, objects combine data with operations. Computation is performed by asking an object to carry out one of its operations. In order to make use of objects, you need to know how to create them and how to request operations. In the interactive examples above, we manipulated several different kinds of objects: GraphWin, Point, Circle, Oval, Line, Text, and Rectangle. These are examples of classes. Every object is an instance of some class, and the class describes the properties the instance will have. Borrowing a biological metaphor, when we say that Fido is a dog, we are actually saying that Fido is a specific individual in the larger class of all dogs. In OO terminology, Fido is an instance of the dog class.
5.3. USING GRAPHICAL OBJECTS
Figure 5.3: Various shapes from the graphics module.
Because Fido is an instance of this class, we expect certain things. Fido has four legs, a tail, a cold, wet nose and he barks. If Rex is a dog, we expect that he will have similar properties, even though Fido and Rex may differ in specific details such as size or color. The same ideas hold for our computational objects. We can create two separate instances of Point, say p and p2. Each of these points has an x and y value, and they both support the same set of operations like getX and draw. These properties hold because the objects are Points. However, different instances can vary in specific details such as the values of their coordinates. To create a new instance of a class, we use a special operation called a constructor. A call to a constructor is an expression that creates a brand new object. The general form is as follows. (, , ...) Here is the name of the class that we want to create a new instance of, e.g., Circle or Point. The expressions in the parentheses are any parameters that are required to initialize the object. The number and type of the parameters depends on the class. A Point requires two numeric values, while a GraphWin can be constructed without any parameters. Typically, a constructor is used on the right side of an assignment statement, and the resulting object is immediately assigned to a variable on the left side that is then used to manipulate the object. To take a concrete example, let’s look at what happens when we create a graphical point. Here is a constructor statement from the interactive example above. p = Point(50,60) The constructor for the Point class requires two parameters giving the x and y coordinates for the new point. These values are stored as instance variables inside of the object. In this case, Python creates an instance of Point having an x value of 50 and a y value of 60. The resulting point is then assigned to the variable p. A conceptual diagram of the result is shown in Figure 5.4. Note that, in this diagram as well as similar ones later on, only the most salient details are shown. Points also contain other information such as their color and which window (if any) they are drawn in. Most of this information is set to default values when the Point is created. To perform an operation on an object, we send the object a message. The set of messages that an object responds to are called the methods of the object. You can think of methods as functions that live inside of the object. A method is invoked using dot-notation.