CSC212 Lab 9 Solutions 2014

--D. Thiebaut (talk) 15:46, 23 October 2014 (EDT)

---

Problem #1

public class Lab9 {

        private static int[] initSortedArray( int N ) {
                int[] array = new int[N];
                array[0] = 3;
                for ( int i=1; i<N; i++ ) 
                        array[ i ] = array[i-1] + (i*11)%7;
                
                return array;
        }
        
        private static int[] initArray( int N ) {
                int[] array = new int[N];
                array[0] = 3;
                for ( int i=1; i<N; i++ ) 
                        array[ i ] = (i+1) * 101 % 23;
                
                return array;
        }
        
        private static int fact( int n ) {
                // stopping condition
                if ( n==1 ) 
                        return 1;
                
                // recursive step
                return n * fact( n-1 );
        }
        
        private static int sum1( int[] A, int low, int high ) {
        	if ( low > high ) return 0;
        	if ( low == high ) return A[low];
        	int keep = A[low];
        	return keep + sum1( A, low+1, high );
        }

        private static int sum2( int[] A, int low, int high ) {
        	if ( low > high ) return 0;
        	if ( low == high ) return A[low];
        	int keep = A[high];
        	return keep + sum2( A, low, high-1 );
        }

        private static int sum3( int[] A, int low, int high ) {
        	if ( low > high ) return 0;
        	if ( low == high ) return A[low];
        	int mid = (low+high)/2;
 
        	return sum3( A, low, mid-1 ) + A[mid]+ sum3( A, mid+1, high );
        }

        private static int max( int[] A, int low, int high) {
        	if ( low==high ) return A[low ];
        	int keep = A[low];
        	int otherMax = max( A, low+1, high );
        	if ( keep > otherMax ) return keep;
        	return otherMax;
        }
        
        static int counter = 0;
        private static int binSearch(int key, int[] A, int low, int high ) {
        	if ( low > high ) return -1;
        	
        	int mid = ( low+high )/2;
        	counter++;
        	if ( key == A[mid] )
        		return mid;
        	
        	counter++;
        	if ( key < A[mid] )
        		return binSearch( key, A, low, mid-1 );
        	return binSearch( key, A, mid+1, high );
        }
        
        private static void displayArray( int[] A ) {
        	for ( int i=0; i<A.length; i++ )
        		System.out.print( A[i] + " " );
        	System.out.println();
        	
        }
        public static void main(String[] args) {
        	int N = 20; 
        	int A[] = initArray( N );
        	
        	displayArray( A );
        	
        	System.out.println( "Sum1 = " + sum1( A, 0, A.length-1) );
        	System.out.println( "Sum2 = " + sum2( A, 0, A.length-1) );
        	System.out.println( "Sum3 = " + sum3( A, 0, A.length-1) );
        	System.out.println( "max = " + max( A, 0, A.length-1) );
        	
        	A = initSortedArray( N );
        	int keys[] = new int[] { 3, 34, 63, 0, 100 };
    		displayArray( A );
        	for ( int i=0; i<keys.length; i++ ) {
        		System.out.println( "binSearch(" + keys[i] + " ) = " 
        				+ binSearch( keys[i], A, 0, A.length-1 ) );
        	}
        	
        	N=100000000;
        	System.out.println( "N = " + N );
        	A = initSortedArray( N );
        	for ( int i=0; i<keys.length; i++ ) {
        		counter = 0;
        		System.out.println( "binSearch(" + keys[i] + " ) = " 
        				+ binSearch( keys[i], A, 0, A.length-1 )
        				+ " " + counter + " probes");
        	}
        	
        }
}

Maze Problem

Playing With Directions

There are several ways to do this. One is to change the for loop:

         // original
         for ( int dir = 0; dir < 4; dir++ ) 
               switch ( dir ) {
                                case 0: newi = i-1; newj=j;   break;
                                case 1: newi = i;   newj=j+1; break; 
                                case 2: newi = i+1; newj=j;   break;
                                case 3: newi = i;   newj=j-1; break;
                             }

or

         // reverse the loop
         for ( int dir = 3; dir >=0; dir-- )  
              switch ( dir ) {
                                case 0: newi = i-1; newj=j;   break;
                                case 1: newi = i;   newj=j+1; break; 
                                case 2: newi = i+1; newj=j;   break;
                                case 3: newi = i;   newj=j-1; break;
                             }

or, create an array with preset directions: in this case, we want to go up first, down next, right, then left.

         // create an new array of directions:
         int[] dirs = new int[] { 0, 2, 1, 3 };
         for ( int k = 0; k <4; k++ )  {
               dir = dirs[ k ];
               switch ( dir ) {
                                case 0: newi = i-1; newj=j;   break;
                                case 1: newi = i;   newj=j+1; break; 
                                case 2: newi = i+1; newj=j;   break;
                                case 3: newi = i;   newj=j-1; break;
                             }

Cleaning Up The Maze at the End

       /**
         * clears the maze of 'b' (back-tracks) or '.'
         * and marks the path to the exit with '.'
         */
        private static void clearMaze() {
                for ( int i=0; i< maze.length; i++ ) 
                        for ( int j=0; j < maze[i].length; j++ )
                                if ( maze[i][j] == '.' || maze[i][j] == 'b' )   
                                        maze[i][j] = ' ';
                                else if ( maze[i][j] == '*' )
                                        maze[i][j] = '.';
        }