Introduction to Programming (22C:16, 22C:106)

Solution to the Final Exam

Solution to Problem 1:

To the file dice.h we make the following changes:

• Add the following include statement to the beginning of the file:

  #include "vector.h"

• Add to the public portion of the interface of the Dice class, the following function header of the new constructor:

  Dice (Vector<int> & faces);

• Add to the private portion of the Dice class the following declaration:

  Vector<int> myFaces;

To the implementation of the Dice class, located in the file dice.cc make the following changes:

• The implementation of the new constructor:

   
  	Dice::Dice(Vector<int> & faces) : myFaces(faces.length())
  	{
  	 	int max = faces.length();
  	 	for (int i = 0; i < max; i++)
  			myFaces[i] = faces[i];
  		myRollCount = 0;
  		mySides= max;
  	}
  
  

• The old constructor needs to be rewritten as follows:

   
  	Dice::Dice(int sides) : myFaces(sides)
  	{
  	 	for (int i = 0; i < sides; i++)
  	 		myFaces[i] = i+1;
  		myRollCount = 0;
  		mySides = sides;
  	}
  
  

• The function Roll() needs to be rewritten as follows:

   
  	int Dice::Roll()
  	{
  		myRollCount++;
  		return myFaces[myGenerator.RandInt(1, mySides) - 1];
  	}
  
  

The other functions: NumSides() and NumRolls() stay the same.

Solution to Problem 2:

 
	int bitonic_max(Vector<int> sequence)
	{
		int left = 0;
		int right = sequence.length() - 1;
		int mid;
		while (1)
		{
			if (left == right)
				return left;
			if (left + 1 == right)
				if (sequence[left] < sequence[right])
					return right;
				else
					return left;
			 mid = (left + right) / 2;
			 if((sequence[mid-1]<sequence[mid])&&(sequence[mid]<sequence[mid+1]))
				left = mid + 1;
			else if((sequence[mid-1]>sequence[mid])&&(sequence[mid]>sequence[mid+1]))
				right = mid - 1;
			else
				return mid;
		}
	}

Solution to Problem 3:

 
	void add(string str1, string str2, string & str3)
	{
		int i = str1.length() - 1;
		int j = str2.length() - 1;
		int carry = 0, op1, op2;
		char result;
		while ((i >= 0) || (j >= 0))
		{
			if (i < 0)
			{
				op1 = 0; op2 = str2[j] - '0';
			}
			else if (j < 0)
			{
			 	op1 = str1[i] - '0'; op2 = 0;
			}
			else 
			{
				op1 = str1[i] - '0'; op2 = str2[j] - '0';
			}
			result = (op1 + op2 + carry) % 10 + '0';
			carry = (op1 + op2 + carry) / 10;
			str3 = result + str3;
			i--; j--;
		} //end-of-while

		if (carry != 0)
			str3 = (carry -'0') + str3;
	} // end-of-function

Solution to Problem 4:

(a)

 
		 Factorial of 5 is 120
		 Factorial of 4 is 24
		 Factorial of 3 is 6
		 Factorial of 2 is 2
		 Factorial of 1 is 1

(b)

 
		 Factorial of 5 is 16
		 Factorial of 1 is 8
		 Factorial of 1 is 4
		 Factorial of 1 is 2
		 Factorial of 1 is 1