CS/CE218 --- Unix and C Programming. 25 October 91 Name: TA: HOMEWORK 5: C Functions Due: 6 November 1991 1. (EXTRA CREDIT ONLY, but you may want to do this one as a review) (a) Parenthesize the following expressions and compute their values; (That is, complete the following table.) Values should be computed assuming that the following declarations (with initializations) are in effect (for each line): int a = 2, b = -3, c = 5, d = -7, e = 11; expression fully parenthesized equivalent value -------------------------------------------------------------- a / b / c (a / b) / c 0 2 * a % - b + c + 1 a += b += c += 1 + 2 7 - + ++ a % (3 + b) error! (b) Why does the expression 7 - + ++ a % (3 + b) give an error at run-time? (c) Parenthesize the following expressions and compute their values; (That is, complete the following table.) Values should be computed assuming that the following declarations (with initializations) are in effect (for each line): int a = 1, b = 2, c = 3; double x = 1.0; expression fully parenthesized equivalent value ------------------------------------------------------------- a > b && c < d (a > b) && (c < d) 0 a < ! b || ! ! a a + b < ! c + c a - x || b * c && b / a (d) If you know enough Pascal, translate the following Pascal code into ANSI C (see chapter 2 of "The C Programming Language"). type suit = {clubs, diamonds, hearts, spades}; var i, j, k: integer; r: real; 2. (6 points) Do exercise 1-15 on page 27 of "The C Programming Language (2nd edition)". (To save typing, the original code (from page 15, slightly altered) is in the file $PUB/hw5/temp_convert.c on Zippy and Zaphod.) 3. (10 points) (The following is adapted from exercise 1-19 on page 31 of "The C Programming Language (2nd edition)".) (a) Write a function void reverse(char s[]) that reverses its argument, s, in place. Your function should use the standard library function strlen (see page 38). (Hint: what is the index of the last non-null character in a string of length 9?) (b) Use your answer to part (a) to write a program that reverses its input a line at a time. (Hint: the code for the program on page 29, slightly altered, is in the file $PUB/hw5/longest_line.c on Zippy and Zaphod.) For example: $ reverse_lines some input tupni emos palindrome emordnilap ^D $ echo $? 0 Note that the following is wrong: $ reverse_lines some input tupni emospalindrome emordnilap ^D $ To cure this problem, make a version of getline that does not return the newline character in the line it reads. 4. In this exercise you will write a function, and then a program, and then divide up your files to do separate compilation. It may save you some time if you think about how to separately compile the functions before you finish parts (a) and (b); or you may feel more comfortable ignoring separate compilation until you're done with parts (a) and (b). (a) (10 points) Do exercise 3-2 on page 60 of "The C Programming Language (2nd edition)". You should handle all the escape sequences in noted in the left-hand column of the table on page 38, except '\n'; your function should also change \ to \\ as it copies. Your escape function should have the heading: void escape(char s[], char t[]) /* requires: the copy plus enough backslashes will fit in t */ /* modifies: t */ /* effect: copy s to t, changing invisible characters and \ to escape sequences */ You don't have to write the function that goes the other way (from \n to a newline), although you can do that as extra credit if you wish. (b) (5 points) Use your answer from part (a) to do exercise 1-10 on page 20 of "The C Programming Language (2nd edition)". Note that it will be easiest if your program works line-by-line, using the getline function in $PUB/hw5/longest_line.c (c) (3 points) Describe how you would organize your code for parts (a) and (b) into separate files; give the commands that you would use to compile these files separately, and also the commands that you would use to link these files. 5. (EXTRA CREDIT ONLY) This problem is just fun with simple arithmetic in C. It concerns the Logistic Difference Equation (see, for example, James Gleick's book ``Chaos: Making a New Science'', Penguin Books, 1987.) An early inspiration for chaos theory comes from biology. (The following is loosely adapted from pages 62-64 of Gleick's book.) Biologists use the logistic difference equation to model the growth of a population over time. For simplicity, one can represent a population, say of fish in a pond, as a fraction between 0 and 1. The fraction 0 represents extinction, while 1 represents the greatest conceivable population of fish that will fit in the pond. A simple linear function, L(x) = r * x, that gives the population for the next year in terms of the current year's population, x, is inadequate, since it does not take limited resources into account. Instead, some biologists in the 1950s started to use a non-linear equation: the logistic difference equation: P_{r}(x) = r * x * (1.0 - x) This equation gives next year's population, P_{r}(x), in terms of this year's population, x, a parameter, r, that represents the amount of ``nonlinearity'', and a factor, 1-x, that keeps the population from getting too big. For example, if r is 2.7 and the population at year 0 is 0.2. The population at year 1 is: 0.05292 = 2.7 * 0.02 * (1 - 0.02). The population at year 2 is about 0.1353. If you keep computing, you'll see that the population eventually reaches an equilibrium of about 0.6296. To describe the process more concisely, I'll introduce a bit of notation. The notation is for iterations of a function, f. Let iterate(f, 0, x) = x, and for all integers k > 0, let iterate(f, k, x) = f(iterate(f, k-1, x. The claim above is that for sufficiently large k and x > 0, iterate(P_{2.7}, k, x) is approximately 0.6296. Does iterating the logistic difference equation always converge on a equilibrium population? Surprisingly, the answer is no! (a) (easy) Write a program that reads a value for r and x from standard input and prints P_{r}(x)$ on standard output. Hint: for reading values for double r, x; try the following code: prompt("value for r? "); scanf("%fl", &r,); prompt("value for x? "); scanf("%fl", &x); You will need to write your own prompt function; scanf is in the standard C library. ("%fl" means to read a double precision (l) floating point (f) number.) (b) (easy) Add error checking to your program; write error messages to standard error output and return a non-zero return code when your program detects an error. What's the maximum value of r that makes sense? (c) Modify your program to read an integer k, scanf("%d", &k); and print the values of iterate(P_{r}, 0, x), iterate(P_{r}, 1, x), ..., iterate(P_{r}, k, x) (on per line) on standard output. Note that you don't have to write a function iterate; this is just a notation used to state the problem. (d) Use your program to try larger and larger numbers for r. (Don't start with 100; start small, say around 2 and increase slowly so you can see what happens.) Can you see where the iterates no longer reach equilibrium? What do the iterates look like? What happens if you keep going higher? (e) (harder) Write a program that searches for the smallest r for which P_{r} does {\em not\/} reach equilibrium for a fixed x. (The value of x will be an input.) Be sure to watch out for infinite loops!