CSCI 2610
Spring 2000
Practice questions for quiz 2: Answers

  1. Which of the following is an invariant for the loop inside function one? (Hint: Look at the values that the variables n and m take on.)
    1. n > 0
    2. m = 14
    3. 2n+m = 14
    4. n = n - 1 
       int one()
   {
     int n,m;
     n = 4;
     m = 6;
     while(n > 0) {
       n = n - 1;
       m = m + 2;
     }
     return m;
   }
    Answer: c. If you look at the values that n and m take on each time the function reaches the top of the loop, you get
    n    m
    4    6
    3    8
    2    10
    1    12
    0    14
    An invariant is a fact that is true at every line of this table. Certainly, n > 0 is not an invariant, since it is false at the last line. Similarly, m = 14 is false at all but the last line. Notice that n = n-1 is false at every line. (It is not true, for example, that 4 = 4 - 1.) But 2n+m = 14 is true at every line. For example, 2(4) + 6 = 14.

  2. Given the following definition of function f, what are the values of f(1), f(f(1)) and f(f(f(1)))? 
       int f(int x)
   {
     if(x < 2) {
       return x + 1;
     }
     else {
       return 2*x + 1;
     }
   }
    Answer: 
       f(1)       = 1+1   = 2
   f(f(1))    = f(2)  = 2*2+1 = 5
   f(f(f(1))) = f(5)  = 2*5 + 1 = 11

  3. If function t is called, what is printed. Be very careful with this question. 
       void r(int a, int x, int &z)
   {
     cout << r: a = " << a << " x = " << x << " z = " << z << endl;
     a = 2;
     x = 5;
     z++;
   }

   void t()
   {
     int a, b, x, z;
     a = 9;
     b = 20;
     x = 67;
     z = 92;
     r(a,b,x);
     r(a,b,x);
     cout << "t: a = " << a << " b = " << b
          << " x = " << x << " z = " << z << endl;
   }
    Answer: The key to answering this question correctly is to be careful, and not to be sloppy. Be sure to keep the two functions separate. Their variables have the same names, but they are different variables. t starts by setting its variables as follows. 
             t
       ------
        a = 9
        b = 20
        x = 67
        z = 92
    Now t calls r(a,b,x). Notice that the first two parameters of r are call-by-value parameters, but the third is a call-by-reference parameter. After starting r, but before running r, the situation is as follows. 
             t                    r
       ------              -------
        a = 9              a = 9
        b = 20             x = 20
        x = 67             z = (reference to t's variable x)
        z = 92
    The first thing that r does is print the values of a, x and z. So the first line printed is 
      r: a = 9 x = 20 z = 67
    Now, after r runs, just before it returns, the situation is as follows. 
             t                    r
       ------              -------
        a = 9              a = 2
        b = 20             x = 5
        x = 68             z = (reference to t's variable x)
        z = 92
    Notice that, when r adds 1 to z, it actually adds one to t's variable x, since z is a reference to t's variable x. When r changes one of its call-by-value parameters, only its local memory is changed.

    Now r returns, leaving t looking like this. 

             t
       ------
        a = 9
        b = 20
        x = 68
        z = 92
    Now t again calls r(a,b,x). The effect is similar to the first call; it prints 
      r: a = 9 x = 20 z = 68
    then adds one to t's variable x. So now t looks like this. 
             t
       ------
        a = 9
        b = 20
        x = 69
        z = 92
    Finally, t prints 
      t: a = 9 b = 20 x = 69 z = 92
    In summary, what is printed is 
      r: a = 9 x = 20 z = 67
  r: a = 9 x = 20 z = 68
  t: a = 9 b = 20 x = 69 z = 92

  4. What is the value of mystery(4)? 
       int mystery(int n)
   {
     if(n == 0) return 0;
     else return mystery(n-1) + n;
   }
    Answer: Notice that, in order to compute mystery(4), we will need to know the value of mystery(3). But in order to compute mystery(3), we will need to know mystery(2). This keeps going on until we need to know the value of mystery(0). The easiest way to find mystery(4) is to start with mystery(0) and work up. 
       mystery(0) = 0
   mystery(1) = mystery(0) + 1 = 0 + 1 = 1
   mystery(2) = mystery(1) + 2 = 1 + 2 = 3
   mystery(3) = mystery(2) + 3 = 3 + 3 = 6
   mystery(4) = mystery(3) + 4 = 6 + 4 = 10
    To answer this question correctly, just keep your work well organized. Do not scrawl a bunch of values around the page so that you lose track of what you are doing.

  5. Write a recursive function sevens so that sevens(n) returns 1 if n has any sevens in its decimal representation, and returns 0 otherwise. For example, sevens(3701) = 1, sevens(777) = 1 and sevens(42) = 0. Assume that n is not negative.

    Note that you can get the rightmost digit of a number n by taking the remainder when you divide n by 10, and you can remove the rightmost digit by dividing n by 10.

    For this problem, do not use any form of loop, and do not alter the value of any variable that already has a meaningful value.

    Answer:An obvious case to try is 0 (where there are no more digits to look at.) Clearly, 0 contains no 7's. Another simple case is where the rightmost digit of n is a 7: then n obviously contains a 7.

    But what if n > 0, and the righmost digit is not a 7? Then just ask a friend whether any of the other digits are a 7. For example, to test whether 37829 contains a 7, you notice that the rightmost digit (9) is not a 7. So you ask a friend whether 3782 contains a 7. Your friend says yes. So you say yes, 37829 contains a 7. (Don't worry about how your friend figures out that 3782 contains a 7. That will take care of itself.) 

       int sevens(long n)
   {
     if(n == 0) return 0;
     else if(n % 10 == 7) return 1;
     else return sevens(n / 10);
   }
    Incidentally, what would happen if the test for n == 0 were left out, and the function were written as follows? 
       int sevens(long n)
   {
     if(n % 10 == 7) return 1;
     else return sevens(n / 10);
   }
    Remember, you MUST be sure to ask your friend to solve a smaller problem than the one you are asked to solve. If n is 0, then this solution asks your friend also to compute sevens(0). Your friend then asks his or her friend for sevens(0), and this goes on forever. The function never produces an answer. You must not ask your friend to solve the exact same problem as you are solving.