lang/C/the.ansi.c.programming.language/c.programming.notes/homework/PS3a.html

   1 <!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
   2 <!-- This collection of hypertext pages is Copyright 1995-7 by Steve Summit. -->
   3 <!-- This material may be freely redistributed and used -->
   4 <!-- but may not be republished or sold without permission. -->
   5 <html>
   6 <head>
   7 <link rev="owner" href="mailto:scs@eskimo.com">
   8 <link rev="made" href="mailto:scs@eskimo.com">
   9 <title>Assignment #3 Answers</title>
  10 </head>
  11 <body>
  12 <H1>Assignment #3 Answers</H1>
  13
  14
  15
  16
  17
  18 <B>Introductory C Programming
  19 <br>
  20 <br>
  21 UW Experimental College
  22 <br>
  23 <br>
  24 Assignment #3 ANSWERS
  25 </B><br>
  26 <br>
  27 <p>Question 1.
  28 <I>How many elements does the array
  29 </I><TT>int a[5]
  30 </TT><I>contain?
  31 Which is the first element?
  32 The last?
  33 </I><p>The array has 5 elements.
  34 The first is <TT>a[0]</TT>;
  35 the last is <TT>a[4]</TT>.
  36 <p>Question 2.
  37 <I>What's wrong with the scrap of code in the question?
  38 </I><p>The array is of size 5, but the loop is from 1 to 5,
  39 so an attempt will be made to access the nonexistent element <TT>a[5]</TT>.
  40 A correct loop over this array would run from 0 to 4.
  41 <p>Question 3.
  42 <I>How might you rewrite the dice-rolling program
  43 without arrays?
  44 </I><p>About all I can think of would be to declare 11 different variables:
  45 <pre>
  46         int roll2, roll3, roll4, roll5, roll6, roll7, roll8, roll9,
  47                 roll10, roll11, roll12;
  48
  49         sum = d1 + d2;  /* sum two die rolls */
  50
  51         if(sum == 2)
  52                 roll2 = roll2 + 1;
  53         else (sum == 3)
  54                 roll3 = roll3 + 1;
  55         else (sum == 4)
  56                 roll4 = roll4 + 1;
  57         else (sum == 5)
  58                 roll5 = roll5 + 1;
  59         ...
  60 </pre>
  61 What a nuisance!
  62 (Fortunately, we never have to write code like this;
  63 we just use arrays,
  64 since this
  65 sort of
  66 situation
  67 is exactly what arrays are for.)
  68 <p>Question 4.
  69 <I>What is the difference between a defining instance and an external declaration?
  70 </I><p>A <dfn>defining instance</dfn>
  71 is a declaration of a variable or function
  72 that actually defines and allocates space for that variable or function.
  73 In the case of a variable,
  74 the defining instance may also supply an initial value,
  75 using an <dfn>initializer</dfn> in the declaration.
  76 In the case of a function,
  77 the defining instance supplies the body of the function.
  78 <p>An <dfn>external declaration</dfn>
  79 is a declaration which mentions the name and type of a variable
  80 or function which is defined elsewhere.
  81 An external declaration does not allocate space;
  82 it cannot supply the initial value of a variable;
  83 it does not need to supply the size of an array;
  84 it does not supply the body of a function.
  85 (In the case of functions, however,
  86 an external declaration may include argument type information;
  87 in this case it is an <dfn>external prototype declaration</dfn>.)
  88 <p>Question 5.
  89 <I>What are the four important parts of a function?
  90 Which three does a caller need to know?
  91 </I><p>The name, the number and type of the arguments,
  92 the return type,
  93 and the body.
  94 The caller needs to know the first three.
  95 <p>Tutorial 3.
  96 <I>Modify the array-of-squares program to also print cubes.
  97 </I><p><pre>
  98 #include &lt;stdio.h&gt;
  99
 100 int main()
 101 {
 102         int i;
 103         int squares[11];        /* [0..10]; [0] ignored */
 104         int cubes[11];
 105         /* fill arrays: */
 106         for(i = 1; i &lt;= 10; i = i + 1)
 107                 {
 108                 squares[i] = i * i;
 109                 cubes[i] = i * i * i;
 110                 }
 111         /* print table: */
 112         printf("n\tsquare\tcube\n");
 113         for(i = 1; i &lt;= 10; i = i + 1)
 114                 printf("%d\t%d\t%d\n", i, squares[i], cubes[i]);
 115         return 0;
 116 }
 117 </pre>
 118
 119 <p>Tutorial 4.
 120 <I>Rewrite the simple graphics program to print ``open'' boxes.
 121 </I><p>I made a new version of the original <TT>printsquare</TT> function
 122 called <TT>printbox</TT>, like this:
 123 <pre>
 124 int printbox(int n)
 125 {
 126         int i, j;
 127         for(j = 0; j &lt; n; j = j + 1)
 128                 printf("*");
 129         printf("\n");
 130         for(i = 0; i &lt; n-2; i = i + 1)
 131                 {
 132                 printf("*");
 133                 for(j = 0; j &lt; n-2; j = j + 1)
 134                         printf(" ");
 135                 printf("*\n");
 136                 }
 137         for(j = 0; j &lt; n; j = j + 1)
 138                 printf("*");
 139         printf("\n");
 140         return 0;
 141 }
 142 </pre>
 143 A box of size 1 or 2 doesn't have all three parts.
 144 If you want the function to handle those sizes more appropriately,
 145 here are the
 146 necessary
 147
 148 modifications:
 149 <pre>
 150 int printbox(int n)
 151 {
 152         int i, j;
 153         for(j = 0; j &lt; n; j = j + 1)
 154                 printf("*");
 155         printf("\n");
 156         for(i = 0; i &lt; n-2; i = i + 1)
 157                 {
 158                 printf("*");
 159                 for(j = 0; j &lt; n-2; j = j + 1)
 160                         printf(" ");
 161                 if(n &gt; 1)
 162                         printf("*\n");
 163                 }
 164         if(n &gt; 1)
 165                 {
 166                 for(j = 0; j &lt; n; j = j + 1)
 167                         printf("*");
 168                 printf("\n");
 169                 }
 170         return 0;
 171 }
 172 </pre>
 173 <p>Exercise 1.
 174 <I>Write code to sum the elements of an array of <TT>int</TT>.
 175 </I><p>Here is a little array-summing function:
 176 <pre>
 177 int sumnum(int a[], int n)
 178 {
 179         int i;
 180         int sum = 0;
 181         for(i = 0; i &lt; n; i = i + 1)
 182                 sum = sum + a[i];
 183         return sum;
 184 }
 185 </pre>
 186 Here is a test program to call it:
 187 <pre>
 188 #include &lt;stdio.h&gt;
 189
 190 int a[] = {1, 2, 3, 4, 5, 6};
 191
 192 int sumnum(int [], int);
 193
 194 int main()
 195 {
 196         printf("%d\n", sumnum(a, 6));
 197         return 0;
 198 }
 199 </pre>
 200 <p>Exercise 2.
 201 <I>Write a loop to call the <TT>multbytwo</TT> function
 202 on the numbers 1-10.
 203 </I><br><pre>
 204 #include &lt;stdio.h&gt;
 205
 206 int multbytwo(int);
 207
 208 int main()
 209 {
 210         int i;
 211         for(i = 1; i &lt;= 10; i++)
 212                 printf("%d  %d\n", i, multbytwo(i));
 213         return 0;
 214 }
 215 </pre>
 216 <p>Exercise 3.
 217 <I>Write a <TT>square()</TT> function
 218 and use it to print the squares of the numbers 1-10.
 219 </I><p>The squaring function is quite simple:
 220 <pre>
 221 int square(int x)
 222 {
 223         return x * x;
 224 }
 225 </pre>
 226 Here is a loop and main program to call it:
 227 <pre>
 228 #include &lt;stdio.h&gt;
 229
 230 int square(int);
 231
 232 int main()
 233 {
 234         int i;
 235
 236         for(i = 1; i &lt;= 10; i = i + 1)
 237                 printf("%d  %d\n", i, square(i));
 238
 239         return 0;
 240 }
 241 </pre>
 242 <p>Exercise 4.
 243 <I>Write a <TT>printnchars</TT> function,
 244 and use it to rewrite the triangle-printing program.
 245 </I><p>Here is the function:
 246 <pre>
 247 void printnchars(int ch, int n)
 248 {
 249         int i;
 250
 251         for(i = 0; i &lt; n; i++)
 252                 printf("%c", ch);
 253 }
 254 </pre>
 255 Here is the rewritten triangle-printing program:
 256 <pre>
 257 #include &lt;stdio.h&gt;
 258
 259 int main()
 260 {
 261         int i;
 262
 263         for(i = 1; i &lt;= 10; i = i + 1)
 264                 {
 265                 printnchars('*', i);
 266                 printf("\n");
 267                 }
 268
 269         return 0;
 270 }
 271 </pre>
 272 <p>Exercise 5.
 273 <I>Write a function to compute the factorial of a number,
 274 and use it to print the factorials of the numbers 1-7.
 275 </I><p>Here is the function:
 276 <pre>
 277 int factorial(int x)
 278 {
 279         int i;
 280         int fact = 1;
 281         for(i = 2; i &lt;= x; i = i + 1)
 282                 fact = fact * i;
 283         return fact;
 284 }
 285 </pre>
 286 Here is a driver program:
 287 <pre>
 288 #include &lt;stdio.h&gt;
 289
 290 int factorial(int);
 291
 292 int main()
 293 {
 294         int i;
 295
 296         for(i = 1; i &lt;= 7; i = i + 1)
 297                 printf("%d   %d\n", i, factorial(i));
 298
 299         return 0;
 300 }
 301 </pre>
 302 <p>The answer to the ``extra credit'' problem is that to
 303 portably compute factorials beyond <TT>factorial(7)</TT>,
 304 it would be necessary to declare the <TT>factorial()</TT>
 305 function as returning <TT>long int</TT>
 306 (and to declare its local <TT>fact</TT> variable as
 307 <TT>long int</TT> as well,
 308 and to use <TT>%ld</TT> in the call to <TT>printf</TT>).
 309 8! (``eight factorial'') is 40320,
 310 but remember,
 311 type <TT>int</TT> is only guaranteed to hold integers up to 32767.
 312 <p>(Some machines, but not all,
 313 have <TT>int</TT>s that can hold more than 32767,
 314 so computing larger factorials on those machines would happen to work,
 315 but not portably.
 316 Some textbooks would tell you to
 317 ``use <TT>long int</TT>
 318 if your machine has 16-bit <TT>int</TT>s,''
 319 but why write code two different ways depending on what kind of
 320 machine you happen to be using today?
 321 I prefer to say,
 322 ``Use <TT>long int</TT>
 323 if you would like results greater than 32767.'')
 324 <p>Exercise 6.
 325 <I>Write a function <TT>celsius()</TT>
 326 to convert degrees Fahrenheit to degrees Celsius.
 327 Use it to print a Fahrenheit-to-Centigrade table
 328 for -40 to 220 degrees Fahrenheit, in increments of 10 degrees.
 329 </I><p>Here is the function:
 330 <pre>
 331 double celsius(double f)
 332 {
 333         return 5. / 9. * (f - 32);
 334 }
 335 </pre>
 336 Here is the driver program:
 337 <pre>
 338 #include &lt;stdio.h&gt;
 339
 340 double celsius(double);
 341
 342 int main()
 343 {
 344         double f;
 345
 346         for(f = -40; f &lt;= 220; f = f + 10)
 347                 printf("%f\t%f\n", f, celsius(f));
 348
 349         return 0;
 350 }
 351 </pre>
 352 <p>Exercise 7.
 353 <I>Modify the dice-rolling program
 354 so that it computes the average
 355 (and, optionally, the standard deviation)
 356 of all the rolls of the pair of dice.
 357 </I><p>The new code involves declaring new variables
 358 <TT>sum</TT>, <TT>n</TT>, and <TT>mean</TT>
 359 (and, for the extra credit problem, <TT>sumsq</TT> and <TT>stdev</TT>),
 360 adding code in the main dice-rolling loop to update <TT>sum</TT> and <TT>n</TT>
 361 (and maybe also <TT>sumsq</TT>),
 362 and finally adding code at the end to compute the mean
 363 (and standard deviation)
 364 and print them out.
 365 <pre>
 366 #include &lt;stdio.h&gt;
 367 #include &lt;stdlib.h&gt;
 368 #include &lt;math.h&gt;
 369
 370 int main()
 371 {
 372         int i;
 373         int d1, d2;
 374         int a[13];      /* uses [2..12] */
 375         double sum = 0;
 376         double sumsq = 0;
 377         int n = 0;
 378         double mean;
 379         double stdev;
 380
 381         for(i = 2; i &lt;= 12; i = i + 1)
 382                 a[i] = 0;
 383
 384         for(i = 0; i &lt; 100; i = i + 1)
 385                 {
 386                 d1 = rand() % 6 + 1;
 387                 d2 = rand() % 6 + 1;
 388                 a[d1 + d2] = a[d1 + d2] + 1;
 389                 sum = sum + d1 + d2;
 390                 sumsq = sumsq + (d1 + d2) * (d1 + d2);
 391                 n = n + 1;
 392                 }
 393
 394         for(i = 2; i &lt;= 12; i = i + 1)
 395                 printf("%d: %d\n", i, a[i]);
 396
 397         printf("\n");
 398         mean = sum / n;
 399         stdev = sqrt((sumsq - sum * sum / n) / (n - 1));
 400         printf("average: %f\n", mean);
 401         printf("std. dev.: %f\n", stdev);
 402
 403         return 0;
 404 }
 405 </pre>
 406 <p>Exercise 8.
 407 <I>Write a <TT>randrange</TT> function.
 408 </I><p>Here is a straightforward implementation
 409 of <TT>randrange2</TT>:
 410 <pre>
 411 #include &lt;stdlib.h&gt;
 412
 413 int randrange2(int m, int n)
 414 {
 415         return rand() % (n - m + 1) + m;
 416 }
 417 </pre>
 418 Here is one using the suggested ``better way of reducing the
 419 range of the <TT>rand</TT> function'':
 420 <pre>
 421 #include &lt;stdlib.h&gt;
 422
 423 int randrange2(int m, int n)
 424 {
 425         return rand() / (RAND_MAX / (n - m + 1) + 1) + m;
 426 }
 427 </pre>
 428 Notice that I've replaced N in the suggested general form
 429 with the expression <TT>n - m + 1</TT>.
 430 <p>You could implement the simpler <TT>randrange</TT> function either as
 431 <pre>
 432         int randrange(int n)
 433         {
 434                 return rand() % n + 1;
 435         }
 436 </pre>
 437 or, using the improvement,
 438 <pre>
 439         int randrange(int n)
 440         {
 441                 return rand() / (RAND_MAX / n + 1) + 1;
 442         }
 443 </pre>
 444 or,
 445 by writing it ``on top of''
 446 the more general <TT>randrange2</TT>
 447 you already wrote,
 448 <pre>
 449         int randrange(int n)
 450         {
 451                 return randrange2(1, n);
 452         }
 453 </pre>
 454 <p>The various ``fudge factors'' in these expressions
 455 deserve some explanation.
 456 The first
 457 one is straightforward:
 458 The <TT>+ 1</TT> in <TT>(n - m + 1)</TT>
 459 simply gives us the number of numbers in the range <TT>m</TT> to
 460 <TT>n</TT>, <em>including</em> <TT>m</TT> and <TT>n</TT>.
 461 (Leaving out the <TT>+ 1</TT> in this case is the classic
 462 example of a <dfn>fencepost error</dfn>,
 463 named after the old puzzle,
 464
 465 ``How many pickets are there in
 466 a picket fence ten feet long, with the pickets one foot apart?'')
 467 <p>The other <TT>+1</TT> is a bit trickier.
 468 First let's consider the second implementation of <TT>randrange</TT>.
 469 We want to divide <TT>rand</TT>'s output by some number
 470 so that the results will come out in the range 0 to <TT>n - </TT>1.
 471 (Then we'll add in 1 to get numbers in the range 1
 472 through <TT>n</TT>.)
 473 Left to its own devices,
 474 <TT>rand</TT> will return numbers in the range 0 to <TT>RAND_MAX</TT>
 475 (where <TT>RAND_MAX</TT> is a
 476
 477 constant defined for us in <TT>&lt;stdlib.h&gt;</TT>).
 478 The division, remember, is going to be integer division,
 479 which will truncate.
 480 So numbers which would have come out in the range
 481 0.0 to 0.99999... (if the division were exact) will all truncate to 0,
 482 numbers which would have come out in the range
 483 1.0 to 1.99999... will all truncate to 1,
 484 2.0 to 2.99999... will all truncate to 2,
 485 etc.
 486 If we were to divide <TT>rand</TT>'s output
 487 by the quantity
 488 <pre>
 489         RAND_MAX / n
 490 </pre>
 491 that is, if we were to write
 492 <pre>
 493         rand() / (RAND_MAX / n)
 494 </pre>
 495 then when <TT>rand</TT> returned <TT>RAND_MAX</TT>,
 496 the division
 497 could
 498 yield exactly
 499 <TT>n</TT>,
 500 which is one too many.
 501 (This wouldn't happen too often--only when <TT>rand</TT>
 502 returned that one value, its maximum value--but it would be a
 503 bug, and a hard one to find, because it wouldn't show up very
 504 often.)
 505 So if we add one to the denominator,
 506 that is,
 507 divide by the quantity
 508 <pre>
 509         RAND_MAX / n + 1
 510 </pre>
 511 then when <TT>rand</TT> returns <TT>RAND_MAX</TT>,
 512 the division will yield a number just shy of
 513 <TT>n</TT>,
 514 which will then be truncated to
 515 <TT>n - </TT>1,
 516 which is just what we want.
 517 We add in 1, and we're done.
 518 <p>In the case of the more general <TT>randrange2</TT>,
 519 everything we've said applies,
 520 with <TT>n</TT> replaced by <TT>n - m + 1</TT>.
 521 Dividing by
 522 <pre>
 523         RAND_MAX / (n - m + 1)
 524 </pre>
 525 would occasionally give us a number one too big
 526 (<TT>n + 1</TT>, after adding in <TT>m</TT>),
 527 so we divide by
 528 <pre>
 529         RAND_MAX / (n - m + 1) + 1
 530 </pre>
 531 instead.
 532 <p>Finally, just two lines in the dice-rolling program would need
 533 to be changed
 534 to make use of the new function:
 535 <pre>
 536                 d1 = randrange(6);
 537                 d2 = randrange(6);
 538 </pre>
 539 or
 540 <pre>
 541                 d1 = randrange2(1, 6);
 542                 d2 = randrange2(1, 6);
 543 </pre>
 544 <p>The answer to the extra-credit portion of the exercise
 545 is that under some compilers,
 546 the output of the <TT>rand</TT> function
 547 is not quite as random as you might wish.
 548 In particular, it's not uncommon for the <TT>rand</TT> funciton
 549 to produce alternately even and odd numbers,
 550 such that if you repeatedly compute <TT>rand % 2</TT>,
 551 you'll get the decidedly non-random sequence 0, 1, 0, 1, 0, 1, 0, 1... .
 552 It's for this reason that
 553 the slightly more elaborate range-reduction techniques
 554 involving the constant <TT>RAND_MAX</TT>
 555 are recommended.
 556 <p>Exercise 9.
 557 <I>Rewrite the dice-rolling program to also print a histogram.
 558 </I><br><pre>
 559 #include &lt;stdio.h&gt;
 560 #include &lt;stdlib.h&gt;
 561
 562 int main()
 563 {
 564         int i;
 565         int d1, d2;
 566         int a[13];      /* uses [2..12] */
 567
 568         for(i = 2; i &lt;= 12; i = i + 1)
 569                 a[i] = 0;
 570
 571         for(i = 0; i &lt; 100; i = i + 1)
 572                 {
 573                 d1 = rand() % 6 + 1;
 574                 d2 = rand() % 6 + 1;
 575                 a[d1 + d2] = a[d1 + d2] + 1;
 576                 }
 577
 578         for(i = 2; i &lt;= 12; i = i + 1)
 579                 {
 580                 printf("%d: %d\t", i, a[i]);
 581                 printnchars('*', a[i]);
 582                 printf("\n");
 583                 }
 584
 585         return 0;
 586 }
 587 </pre>
 588 The <TT>\t</TT> in the second-to-last call to <TT>printf</TT>
 589 prints a tab character,
 590 so that the histogram bars will all be lined up,
 591 regardless of the number of digits
 592 in the particular values of <TT>i</TT> or <TT>a[i]</TT>.
 593 Another possibility would be to use <TT>printf</TT>'s
 594 width specifier
 595 (which we haven't really covered yet)
 596 to keep the digits lined up.
 597 That approach might look like this:
 598 <pre>
 599                         printf("%2d: %3d  ", i, a[i])
 600 </pre>
 601 <hr>
 602 <hr>
 603 <p>
 604 This page by <a href="http://www.eskimo.com/~scs/">Steve Summit</a>
 605 // <a href="copyright.html">Copyright</a> 1995-9
 606 // <a href="mailto:scs@eskimo.com">mail feedback</a>
 607 </p>
 608 </body>
 609 </html>