📄 chapter06.html
字号:
<HTML><HEAD> <TITLE>Chapter 6</TITLE> <LINK REL="STYLESHEET" HREF="downey.css" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/downey.css"></HEAD><BODY><H2>Chapter 6</H2><H1>Iteration</H1><BR><BR><H3>6.1 Multiple assignment</H3><P>I haven't said much about it, but it is legal in C++ to make more than one assignment to the same variable. The effect of the second assignment is to replace the old value of the variable with a new value.</P><PRE> int fred = 5; cout << fred; fred = 7; cout << fred;</PRE><P>The output of this program is 57, because the first time we print <TT>fred</TT> his value is 5, and the second time his value is 7.</P><P>This kind of <B>multiple assignment</B> is the reason I described variables as a <I>container</I> for values. When you assign a value to a variable, you change the contents of the container, as shown in the figure:</P><P CLASS=1><IMG SRC="images/assign2.png" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/assign2.png" ALT="Assignment2 Image"></P><P>When there are multiple assignments to a variable, it is especially important to distinguish between an assignment statement and a statement of equality. Because C++ uses the <TT>=</TT> symbol for assignment, it is tempting to interpret a statement like <TT>a = b</TT> as a statement of equality. It is not!</P><P>First of all, equality is commutative, and assignment is not. For example, in mathematics if <TT>a = 7</TT> then <TT>7 = a</TT>. But in C++ the statement <TT>a = 7;</TT> is legal, and <TT>7 = a;</TT> is not.</P><P>Furthermore, in mathematics, a statement of equality is true for all time. If <TT>a = b</TT> now, then <TT>a</TT> will always equal <TT>b</TT>. In C++, anassignment statement can make two variables equal, but they don't have to stay that way!</P><PRE> int a = 5; int b = a; // a and b are now equal a = 3; // a and b are no longer equal</PRE><P>The third line changes the value of <TT>a</TT> but it does not change the value of <TT>b</TT>, and so they are no longer equal. In many programming languages an alternate symbol is used for assignment, such as <TT><-</TT> or <TT>:=</TT>, in order to avoid confusion.</P><P>Although multiple assignment is frequently useful, you should use it with caution. If the values of variables are changing constantly in different partsof the program, it can make the code difficult to read and debug.</P><BR><BR><H3>6.2 Iteration</H3><P>One of the things computers are often used for is the automation of repetitive tasks. Repeating identical or similar tasks without making errors is something that computers do well and people do poorly.</P><P>We have seen programs that use recursion to perform repetition, such as <TT>nLines</TT> and <TT>countdown</TT>. This type of repetition is called <B>iteration</B>, and C++ provides several language features that make it easier to write iterative programs.</P><P>The two features we are going to look at are the <TT>while</TT> statement and the <TT>for</TT> statement.</P><BR><BR><H3>6.3 The <TT>while</TT> statement</H3><P>Using a while</TT> statement, we can rewrite <TT>countdown</TT>:</P><PRE>void countdown (int n) { while (n > 0) { cout << n << endl; n = n-1; } cout << "Blastoff!" << endl;}</PRE><P>You can almost read a <TT>while</TT> statement as if it were English. What this means is, ``While <TT>n</TT> is greater than zero, continue displaying thevalue of <TT>n</TT> and then reducing the value of <TT>n</TT> by 1. When you get to zero, output the word `Blastoff!'''</P><P>More formally, the flow of execution for a <TT>while</TT> statement is as follows:</P><OL> <LI>Evaluate the condition in parentheses, yielding <TT>true</TT> or <TT>false</TT>.</LI> <LI>If the condition is false, exit the <TT>while</TT> statement and continue execution at the next statement.</LI> <LI>If the condition is true, execute each of the statements between the squiggly-braces, and then go back to step 1.</LI></OL><P>This type of flow is called a <B>loop</B> because the third step loops back around to the top. Notice that if the condition is false the first time throughthe loop, the statements inside the loop are never executed. The statements inside the loop are called the <B>body</B> of the loop.</P><P>The body of the loop should change the value of one or more variables so that, eventually, the condition becomes false and the loop terminates. Otherwise the loop will repeat forever, which is called an <B>infinite loop</B>. An endless source of amusement for computer scientists isthe observation that the directions on shampoo, ``Lather, rinse, repeat,'' arean infinite loop.</P><P>In the case of <TT>countdown</TT>, we can prove that the loop will terminatebecause we know that the value of <TT>n</TT> is finite, and we can see that thevalue of <TT>n</TT> gets smaller each time through the loop (each <B>iteration</B>), so eventually we have to get to zero. In other cases it is not so easy to tell:</P><PRE> void sequence (int n) { while (n != 1) { cout << n << endl; if (n%2 == 0) { // n is even n = n / 2; } else { // n is odd n = n*3 + 1; } } }</PRE><P>The condition for this loop is <TT>n != 1</TT>, so the loop will continue until <TT>n</TT> is 1, which will make the condition false.</P><P>At each iteration, the program outputs the value of <TT>n</TT> and then checks whether it is even or odd. If it is even, the value of <TT>n</TT> is divided by two. If it is odd, the value is replaced by <TT>3n+1</TT>. For example, if the starting value (the argument passed to sequence}) is 3, the resulting sequence is 3, 10, 5, 16, 8, 4, 2, 1.</P><P>Since <TT>n</TT> sometimes increases and sometimes decreases, there is noobvious proof that <TT>n</TT> will ever reach 1, or that the program will terminate. For some particular values of <TT>n</TT>, we can prove termination.For example, if the starting value is a power of two, then the value of <TT>n</TT> will be even every time through the loop, until we get to 1. The previous example ends with such a sequence, starting with 16.</P><P>Particular values aside, the interesting question is whether we can prove that this program terminates for <I>all</I> values of <TT>n</TT>. So far, no one has been able to prove it <I>or</I> disprove it!</P><BR><BR><H3>6.4 Tables</H3><P>One of the things loops are good for is generating tabular data. For example, before computers were readily available, people had to calculate logarithms, sines and cosines, and other common mathematical functions by hand.To make that easier, there were books containing long tables where you could find the values of various functions. Creating these tables was slow and boring,and the result tended to be full of errors.</P><P>When computers appeared on the scene, one of the initial reactions was, ``This is great! We can use the computers to generate the tables, so there will be no errors.'' That turned out to be true (mostly), but shortsighted. Soon thereafter computers and calculators were so pervasive that the tables became obsolete.</P><P>Well, almost. It turns out that for some operations, computers use tables ofvalues to get an approximate answer, and then perform computations to improve the approximation. In some cases, there have been errors in the underlying tables, most famously in the table the original Intel Pentium used to performfloating-point division.</P><P>Although a ``log table'' is not as useful as it once was, it still makes a good example of iteration. The following program outputs a sequence of values in the left column and their logarithms in the right column:</P><PRE> double x = 1.0; while (x < 10.0) { cout << x << "\t" << log(x) << "\n"; x = x + 1.0; }</PRE><P>The sequence <TT>\t</TT> represents a <B>tab</B> character. The sequence <TT>\n</TT> represents a newline character. These sequences can be included anywhere in a string, although in these examples the sequence is the whole string.</P><P>A tab character causes the cursor to shift to the right until it reaches oneof the <B>tab stops</B>, which are normally every eight characters. As we will see in a minute, tabs are useful for making columns of text line up.</P><P>A newline character has exactly the same effect as <TT>endl</TT>; it causes the cursor to move on to the next line. Usually if a newline character appearsby itself, I use <TT>endl</TT>, but if it appears as part of a string, I use <TT>\n</TT>.</P><P>The output of this program is</P><PRE>1 02 0.6931473 1.098614 1.386295 1.609446 1.791767 1.945918 2.079449 2.19722</PRE><P>If these values seem odd, remember that the <TT>log</TT> function uses base <TT>e</TT>. Since powers of two are so important in computer science, we often want to find logarithms with respect to base 2. To do that, we can use the following formula:</P><PRE> log<SUB>2</SUB> x = log<SUB>e</SUB> x / log<SUB>e</SUB> 2</PRE><P>Changing the output statement to</P><PRE> cout << x << "\t" << log(x) / log(2.0) << endl;</PRE><P>yields</P><PRE>1 02 13 1.584964 25 2.321936 2.584967 2.807358 39 3.16993</PRE><P>We can see that 1, 2, 4 and 8 are powers of two, because their logarithms base 2 are round numbers. If we wanted to find the logarithms of other powers of two, we could modify the program like this:</P><PRE> double x = 1.0; while (x < 100.0) { cout << x << "\t" << log(x) / log(2.0) << endl; x = x * 2.0; }</PRE><P>Now instead of adding something to x} each time through the loop, which yields an arithmetic sequence, we multiply <TT>x</TT> by something, yielding a <B>geometric</B> sequence. The result is:</P><PRE>1 02 14 28 316 432 564 6</PRE><P>Because we are using tab characters between the columns, the position of thesecond column does not depend on the number of digits in the first column.</P><P>Log tables may not be useful any more, but for computer scientists, knowing the powers of two is! As an exercise, modify this program so that it outputs the powers of two up to 65536 (that's <TT>2<SUP>16</SUP></TT>). Print it out and memorize it.</P><BR><BR><H3>6.5 Two-dimensional tables</H3><P>A two-dimensional table is a table where you choose a row and a column and read the value at the intersection. A multiplication table is a good example.Let's say you wanted to print a multiplication table for the values from 1 to 6.</P><P>A good way to start is to write a simple loop that prints the multiples of 2, all on one line.</P><PRE> int i = 1; while (i <= 6) { cout << 2*i << " "; i = i + 1; } cout << endl;</PRE><P>The first line initializes a variable named <TT>i</TT>, which is going to act as a counter, or <B>loop variable</B>. As the loop executes, the value of <TT>i</TT> increases from 1 to 6, and then when <TT>i</TT> is 7, the loop terminates. Each time through the loop, we print the value <TT>2*i</TT> followed by three spaces. By omitting the <TT>endl</TT> from the first output statement, we get all the output on a single line.</P><P>The output of this program is:</P><PRE>2 4 6 8 10 12</PRE><P>So far, so good. The next step is to <B>encapsulate</B> and <B>generalize</B>.</P><BR><BR><H3>6.6 Encapsulation and generalization</H3><P>Encapsulation usually means taking a piece of code and wrapping it up in a function, allowing you to take advantage of all the things functions are good for. We have seen two examples of encapsulation, when we wrote <TT>printParity</TT> in Section 4.3 and <TT>isSingleDigit</TT> in Section 5.8.</P><P>Generalization means taking something specific, like printing multiples of 2, and making it more general, like printing the multiples of any integer.</P><P>Here's a function that encapsulates the loop from the previous section and ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -