CS105			Review for Exam #1


Exam #1  may involve some  questions that are in some ways like some of
these questions (but no promises - there can also be things that are not
like anything on this review, and some things on this review may not
appear on the exam).

1)  Combine several if statements that do not have "else" clauses or use
&& or ||, to produce a function that is equivalent to the following:

void test(int a, int b, int c, int d)
{
	if (a > 0 || (b < c && c < d))
		cout << "hello";
	else if (a > -50)
		cout << "goodbye";
}







2) Rewrite the following function to avoid using a "do-while" loop.  You
may use recursion, while loops, for loops, if, or anything else, as long
as  (1) you don't have a do-while loop in your answer, and (2) you never
use the value of a variable that hasn't had a value put in it yet, and
(3) your answer does the same thing as the given program.

void check_password()
{
	cpstring password;
	do {
		cout << "Enter password: " << endl;
		cin >> password;
	} while (password != "joshua");
}

3) Draw a "tree" diagrams showing the function calls performed for the
function calls power(3,5) and  A(2,2), where the functions A and power
are defined as follows:

int power(int b, int e)  // b to the e power, e>0
{
	if (e == 1)
		return b;
	else if (e % 2 == 0) // e is even
		return power(b,e/2) * power(b,e/2);
	else
		return b*power(b,e-1);
}

int A(int x, int y)  // the famous "Ackerman's Function"
{
	if (x == 0)
		return y+1;
	else if (y==0)
		return A(x-1,1);
	else
		return A(x-1,A(x,y-1));
}
  4) What is the output of the program below:

void funky(int x, int &y)
{
	if (y > 0)
	{
		y = y - 1;
		x = x * 2;
		funky(x, y);
	}
	cout << x << " " << y << endl;
}

int main()
{
	int a, b;
	a = 3;
	b = 2;
	funky(a, b);
	return 0;
}



5) Write a recursive function that prints out all possible six-letter
sequences of "X" and "O" (you may, if necessary, rely on a "starter"
function to start your main recursive function).
 6) Give the appropriate  loop invariant for the following loop, next
to the comment "INVARIANT", and then answer the following questions.
a) If we changed every "else if" to "if", would your invariant still be
correct? ________
    Could the assertion after the loop ever fail? ________
b) If instead we eliminated the last "else if" and all the statements it
controls,
    Would your loop invariant still be correct?  _______
    Could the assertion after the loop ever fail?  _______
    Would the loop still be correct?   _______
    If the loop is not correct, which step of our proof would fail if we
try to prove it is correct?
    

change0=change;
quarters=dimes=nickels=pennies=0;
while(change>0)
{
	// INVARIANT:
	//
	//
	
	if (change >= 25)
	{
		quarters = quarters+1;
		change=change-25;
	}
	else if (change >= 10)
	{
		dimes = dimes+1;
		change=change-10;
	}
	else if (change >= 5)
	{
		nickels = nickels+1;
		change=change-10;
	}
	else if (change >= 1)
	{
		pennies = pennies+1;
		change=change-1;
	}
}
assert(change == 0 &&
	  25*quarters+10*dimes+5*nickels+1*pennies == change0);