// ex04_18.cpp
#include <iostream>

using std::cout;
using std::endl;

int whatIsThis( int [], int );

int main()
{
   const int arraySize = 10;
   int a[ arraySize ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

   int result = whatIsThis( a, arraySize );

   cout << "Result is " << result << endl;
   return 0;
}

int whatIsThis( int b[], int size )
{
   if ( size == 1 )
      return b[ 0 ];
   else
      return b[ size - 1 ] + whatIsThis( b, size - 1 );
}

// ex04_21.cpp
#include <iostream>

using std::cout;
using std::endl;

void someFunction( int [], int );

int main()
{
   const int arraySize = 10;
   int a[ arraySize ] =
      32, 27, 64, 18, 95, 14, 90, 70, 60, 37 };

   cout << "The values in the array are:" << endl;
   someFunction( a, arraySize );
   cout << endl;
   return 0;
}

void someFunction( int b[], int size )
{
   if ( size > 0 ) {
      someFunction( &b[ 1 ], size - 1 );
      cout << b[ 0 ] << "  ";
   }
}

// Fig. 4.3: fig04_03.cpp
// initializing an array
#include <iostream>

using std::cout;
using std::endl;

#include <iomanip>

using std::setw;

int main()
{
   int i, n[ 10 ];

   for ( i = 0; i < 10; i++ )        // initialize array
      n[ i ] = 0;

   cout << "Element" << setw( 13 ) << "Value" << endl;

   for ( i = 0; i < 10; i++ )        // print array
      cout << setw( 7 ) << i << setw( 13 ) << n[ i ] << endl;

   return 0;
}

// Fig. 4.4: fig04_04.cpp
// Initializing an array with a declaration
#include <iostream>

using std::cout;
using std::endl;

#include <iomanip>

using std::setw;

int main()
{
   int n[ 10 ] = { 32, 27, 64, 18, 95, 14, 90, 70, 60, 37 };

   cout << "Element" << setw( 13 ) << "Value" << endl;

   for ( int i = 0; i < 10; i++ )
      cout << setw( 7 ) << i << setw( 13 ) << n[ i ] << endl;

   return 0;
}

// Fig. 4.5: fig04_05.cpp
// Initialize array s to the even integers from 2 to 20.
#include <iostream>

using std::cout;
using std::endl;

#include <iomanip>

using std::setw;

int main()
{
   const int arraySize = 10;
   int j, s[ arraySize ];

   for ( j = 0; j < arraySize; j++ )   // set the values
      s[ j ] = 2 + 2 * j;

   cout << "Element" << setw( 13 ) << "Value" << endl;

   for ( j = 0; j < arraySize; j++ )   // print the values
      cout << setw( 7 ) << j << setw( 13 ) << s[ j ] << endl;

   return 0;
}

// Fig. 4.6: fig04_06.cpp
// Using a properly initialized constant variable
#include <iostream>

using std::cout;
using std::endl;

int main()
{
   const int x = 7;  // initialized constant variable

   cout << "The value of constant variable x is: "
        << x << endl;

   return 0;
}

// Fig. 4.7: fig04_07.cpp
// A const object must be initialized

int main()
{
   const int x;  // Error: x must be initialized

   x = 7;        // Error: cannot modify a const variable

   return 0;
}

// Fig. 4.8: fig04_08.cpp
// Compute the sum of the elements of the array
#include <iostream>

using std::cout;
using std::endl;

int main()
{
   const int arraySize = 12;
   int a[ arraySize ] = { 1, 3, 5, 4, 7, 2, 99,
                          16, 45, 67, 89, 45 };
   int total = 0;

   for ( int i = 0; i < arraySize; i++ )
      total += a[ i ];

   cout << "Total of array element values is " << total << endl;
   return 0;
}

// Fig. 4.9: fig04_09.cpp
// Student poll program
#include <iostream>

using std::cout;
using std::endl;

#include <iomanip>

using std::setw;

int main()
{
   const int responseSize = 40, frequencySize = 11;
   int responses[ responseSize ] = { 1, 2, 6, 4, 8, 5, 9, 7, 8,
       10, 1, 6, 3, 8, 6, 10, 3, 8, 2, 7, 6, 5, 7, 6, 8, 6, 7,
       5, 6, 6, 5, 6, 7, 5, 6, 4, 8, 6, 8, 10 };
   int frequency[ frequencySize ] = { 0 };

   for ( int answer = 0; answer < responseSize; answer++ )
      ++frequency[ responses[answer] ];

   cout << "Rating" << setw( 17 ) << "Frequency" << endl;

   for ( int rating = 1; rating < frequencySize; rating++ )
      cout << setw( 6 ) << rating
           << setw( 17 ) << frequency[ rating ] << endl;

   return 0;
}

// Fig. 4.10: fig04_10.cpp
// Histogram printing program
#include <iostream>

using std::cout;
using std::endl;

#include <iomanip>

using std::setw;

int main()
{
   const int arraySize = 10;
   int n[ arraySize ] = { 19, 3, 15, 7, 11, 9, 13, 5, 17, 1 };

   cout << "Element" << setw( 13 ) << "Value"
        << setw( 17 ) << "Histogram" << endl;

   for ( int i = 0; i < arraySize; i++ ) {
      cout << setw( 7 ) << i << setw( 13 )
           << n[ i ] << setw( 9 );

      for ( int j = 0; j < n[ i ]; j++ )   // print one bar
         cout << '*';

      cout << endl;
   }

   return 0;
}

// Fig. 4.11: fig04_11.cpp
// Roll a six-sided die 6000 times
#include <iostream>

using std::cout;
using std::endl;

#include <iomanip>

using std::setw;

#include <cstdlib>
#include <ctime>

int main()
{
   const int arraySize = 7;
   int face, frequency[ arraySize ] = { 0 };

   srand( time( 0 ) );

   for ( int roll = 1; roll <= 6000; roll++ )
      ++frequency[ 1 + rand() % 6 ]; // replaces 20-line switch
                                     // of Fig. 3.8

   cout << "Face" << setw( 13 ) << "Frequency" << endl;

   // ignore element 0 in the frequency array
   for ( face = 1; face < arraySize; face++ )
      cout << setw( 4 ) << face
           << setw( 13 ) << frequency[ face ] << endl;

   return 0;
}

// Fig. 4_12: fig04_12.cpp
// Treating character arrays as strings
#include <iostream>

using std::cout;
using std::cin;
using std::endl;

int main()
{
   char string1[ 20 ], string2[] = "string literal";

   cout << "Enter a string: ";
   cin >> string1;
   cout << "string1 is: " << string1
        << "\nstring2 is: " << string2
        << "\nstring1 with spaces between characters is:\n";

   for ( int i = 0; string1[ i ] != '\0'; i++ )
      cout << string1[ i ] << ' ';

   cin >> string1;  // reads "there"
   cout << "\nstring1 is: " << string1 << endl;

   cout << endl;
   return 0;
}

// Fig. 4.13: fig04_13.cpp
// Static arrays are initialized to zero
#include <iostream>

using std::cout;
using std::endl;

void staticArrayInit( void );
void automaticArrayInit( void );

int main()
{
   cout << "First call to each function:\n";
   staticArrayInit();
   automaticArrayInit();

   cout << "\n\nSecond call to each function:\n";
   staticArrayInit();
   automaticArrayInit();
   cout << endl;

   return 0;
}

// function to demonstrate a static local array
void staticArrayInit( void )
{
   static int array1[ 3 ];
   int i;

   cout << "\nValues on entering staticArrayInit:\n";

   for ( i = 0; i < 3; i++ )
      cout << "array1[" << i << "] = " << array1[ i ] << "  ";

   cout << "\nValues on exiting staticArrayInit:\n";

   for ( i = 0; i < 3; i++ )
      cout << "array1[" << i << "] = "
           << ( array1[ i ] += 5 ) << "  ";
}

// function to demonstrate an automatic local array
void automaticArrayInit( void )
{
   int i, array2[ 3 ] = { 1, 2, 3 };

   cout << "\n\nValues on entering automaticArrayInit:\n";

   for ( i = 0; i < 3; i++ )
      cout << "array2[" << i << "] = " << array2[ i ] << "  ";

   cout << "\nValues on exiting automaticArrayInit:\n";

   for ( i = 0; i < 3; i++ )
      cout << "array2[" << i << "] = "
           << ( array2[ i ] += 5 ) << "  ";
}

// Fig. 4.14: fig04_14.cpp
// Passing arrays and individual array elements to functions
#include <iostream>

using std::cout;
using std::endl;

#include <iomanip>

using std::setw;

void modifyArray( int [], int );  // appears strange
void modifyElement( int );

int main()
{
   const int arraySize = 5;
   int i, a[ arraySize ] = { 0, 1, 2, 3, 4 };

   cout << "Effects of passing entire array call-by-reference:"
        << "\n\nThe values of the original array are:\n";

   for ( i = 0; i < arraySize; i++ )
      cout << setw( 3 ) << a[ i ];

   cout << endl;

   // array a passed call-by-reference
   modifyArray( a, arraySize );

   cout << "The values of the modified array are:\n";

   for ( i = 0; i < arraySize; i++ )
      cout << setw( 3 ) << a[ i ];

   cout << "\n\n\n"
        << "Effects of passing array element call-by-value:"
        << "\n\nThe value of a[3] is " << a[ 3 ] << '\n';

   modifyElement( a[ 3 ] );

   cout << "The value of a[3] is " << a[ 3 ] << endl;

   return 0;
}

// In function modifyArray, "b" points to the original
// array "a" in memory.
void modifyArray( int b[], int sizeOfArray )
{
   for ( int j = 0; j < sizeOfArray; j++ )
      b[ j ] *= 2;
}

// In function modifyElement, "e" is a local copy of
// array element a[ 3 ] passed from main.
void modifyElement( int e )
{
   cout << "Value in modifyElement is "
        << ( e *= 2 ) << endl;
}

// Fig. 4.15: fig04_15.cpp
// Demonstrating the const type qualifier
#include <iostream>

using std::cout;
using std::endl;

void tryToModifyArray( const int [] );

int main()
{
   int a[] = { 10, 20, 30 };

   tryToModifyArray( a );
   cout << a[ 0 ] << ' ' << a[ 1 ] << ' ' << a[ 2 ] << '\n';
   return 0;
}

// In function tryToModifyArray, "b" cannot be used
// to modify the original array "a" in main.
void tryToModifyArray( const int b[] )
{
   b[ 0 ] /= 2;    // error
   b[ 1 ] /= 2;    // error
   b[ 2 ] /= 2;    // error
}

// Fig. 4.16: fig04_16.cpp
// This program sorts an array's values into
// ascending order
#include <iostream>

using std::cout;
using std::endl;

#include <iomanip>

using std::setw;

int main()
{
   const int arraySize = 10;
   int a[ arraySize ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
   int i, hold;

   cout << "Data items in original order\n";

   for ( i = 0; i < arraySize; i++ )
      cout << setw( 4 ) << a[ i ];

   for ( int pass = 0; pass < arraySize - 1; pass++ ) // passes

      for ( i = 0; i < arraySize - 1; i++ )      // one pass

         if ( a[ i ] > a[ i + 1 ] ) {      // one comparison
            hold = a[ i ];                 // one swap
            a[ i ] = a[ i + 1 ];
            a[ i + 1 ] = hold;
         }

   cout << "\nData items in ascending order\n";

   for ( i = 0; i < arraySize; i++ )
      cout << setw( 4 ) << a[ i ];

   cout << endl;
   return 0;
}

// Fig. 4.17: fig04_17.cpp
// This program introduces the topic of survey data analysis.
// It computes the mean, median, and mode of the data.
#include <iostream>

using std::cout;
using std::endl;
using std::ios;

#include <iomanip>

using std::setw;
using std::setiosflags;
using std::setprecision;

void mean( const int [], int );
void median( int [], int );
void mode( int [], int [], int );
void bubbleSort( int[], int );
void printArray( const int[], int );

int main()
{
   const int responseSize = 99;
   int frequency[ 10 ] = { 0 },
       response[ responseSize ] =
          { 6, 7, 8, 9, 8, 7, 8, 9, 8, 9,
            7, 8, 9, 5, 9, 8, 7, 8, 7, 8,
            6, 7, 8, 9, 3, 9, 8, 7, 8, 7,
            7, 8, 9, 8, 9, 8, 9, 7, 8, 9,
            6, 7, 8, 7, 8, 7, 9, 8, 9, 2,
            7, 8, 9, 8, 9, 8, 9, 7, 5, 3,
            5, 6, 7, 2, 5, 3, 9, 4, 6, 4,
            7, 8, 9, 6, 8, 7, 8, 9, 7, 8,
            7, 4, 4, 2, 5, 3, 8, 7, 5, 6,
            4, 5, 6, 1, 6, 5, 7, 8, 7 };

   mean( response, responseSize );
   median( response, responseSize );
   mode( frequency, response, responseSize );

   return 0;
}

void mean( const int answer[], int arraySize )
{
   int total = 0;

   cout << "********\n  Mean\n********\n";

   for ( int j = 0; j < arraySize; j++ )
      total += answer[ j ];

   cout << "The mean is the average value of the data\n"
        << "items. The mean is equal to the total of\n"
        << "all the data items divided by the number\n"
        << "of data items (" << arraySize
        << "). The mean value for\nthis run is: "
        << total << " / " << arraySize << " = "
        << setiosflags( ios::fixed | ios::showpoint )
        << setprecision( 4 )
        << static_cast< double >( total ) / arraySize << "\n\n";
}

void median( int answer[], int size )
{
   cout << "\n********\n Median\n********\n"
        << "The unsorted array of responses is";

   printArray( answer, size );
   bubbleSort( answer, size );
   cout << "\n\nThe sorted array is";
   printArray( answer, size );
   cout << "\n\nThe median is element " << size / 2
        << " of\nthe sorted " << size
        << " element array.\nFor this run the median is "
        << answer[ size / 2 ] << "\n\n";
}

void mode( int freq[], int answer[], int size )
{
   int rating, largest = 0, modeValue = 0;

   cout << "\n********\n  Mode\n********\n";

   for ( rating = 1; rating <= 9; rating++ )
      freq[ rating ] = 0;

   for ( int j = 0; j < size; j++ )
      ++freq[ answer[ j ] ];

   cout << "Response"<< setw( 11 ) << "Frequency"
        << setw( 19 ) << "Histogram\n\n" << setw( 55 )
        << "1    1    2    2\n" << setw( 56 )
        << "5    0    5    0    5\n\n";

   for ( rating = 1; rating <= 9; rating++ ) {
      cout << setw( 8 ) << rating << setw( 11 )
           << freq[ rating ] << "          ";

      if ( freq[ rating ] > largest ) {
         largest = freq[ rating ];
         modeValue = rating;
      }

      for ( int h = 1; h <= freq[ rating ]; h++ )
         cout << '*';

      cout << '\n';
   }

   cout << "The mode is the most frequent value.\n"
        << "For this run the mode is " << modeValue
        << " which occurred " << largest << " times." << endl;
}

void bubbleSort( int a[], int size )
{
   int hold;

   for ( int pass = 1; pass < size; pass++ )

      for ( int j = 0; j < size - 1; j++ )

         if ( a[ j ] > a[ j + 1 ] ) {
            hold = a[ j ];
            a[ j ] = a[ j + 1 ];
            a[ j + 1 ] = hold;
         }
}

void printArray( const int a[], int size )
{
   for ( int j = 0; j < size; j++ ) {

      if ( j % 20 == 0 )
         cout << endl;

      cout << setw( 2 ) << a[ j ];
   }
}

// Fig. 4.19: fig04_19.cpp
// Linear search of an array
#include <iostream>

using std::cout;
using std::cin;
using std::endl;

int linearSearch( const int [], int, int );

int main()
{
   const int arraySize = 100;
   int a[ arraySize ], searchKey, element;

   for ( int x = 0; x < arraySize; x++ )  // create some data
      a[ x ] = 2 * x;

   cout << "Enter integer search key:" << endl;
   cin >> searchKey;
   element = linearSearch( a, searchKey, arraySize );

   if ( element != -1 )
      cout << "Found value in element " << element << endl;
   else
      cout << "Value not found" << endl;

   return 0;
}

int linearSearch( const int array[], int key, int sizeOfArray )
{
   for ( int n = 0; n < sizeOfArray; n++ )
      if ( array[ n ] == key )
         return n;

   return -1;
}

// Fig. 4.20: fig04_20.cpp
// Binary search of an array
#include <iostream>

using std::cout;
using std::cin;
using std::endl;

#include <iomanip>

using std::setw;

int binarySearch( const int [], int, int, int, int );
void printHeader( int );
void printRow( const int [], int, int, int, int );

int main()
{
   const int arraySize = 15;
   int a[ arraySize ], key, result;

   for ( int i = 0; i < arraySize; i++ )
      a[ i ] = 2 * i;   // place some data in array

   cout << "Enter a number between 0 and 28: ";
   cin >> key;

   printHeader( arraySize );
   result = binarySearch( a, key, 0, arraySize - 1, arraySize );

   if ( result != -1 )
      cout << '\n' << key << " found in array element "
           << result << endl;
   else
      cout << '\n' << key << " not found" << endl;

   return 0;
}

// Binary search
int binarySearch( const int b[], int searchKey, int low, int high,
                  int size )
{
   int middle;

   while ( low <= high ) {
      middle = ( low + high ) / 2;

      printRow( b, low, middle, high, size );

      if ( searchKey == b[ middle ] )  // match
         return middle;
      else if ( searchKey < b[ middle ] )
         high = middle - 1;        // search low end of array
      else
         low = middle + 1;         // search high end of array
   }

   return -1;   // searchKey not found
}

// Print a header for the output
void printHeader( int size )
{
   int i;

   cout << "\nSubscripts:\n";

   for ( i = 0; i < size; i++ )
      cout << setw( 3 ) << i << ' ';

   cout << '\n';

   for ( i = 1; i <= 4 * size; i++ )
      cout << '-';

   cout << endl;
}

// Print one row of output showing the current
// part of the array being processed.
void printRow( const int b[], int low, int mid, int high, int size )
{
   for ( int i = 0; i < size; i++ )
      if ( i < low || i > high )
         cout << "    ";
      else if ( i == mid )           // mark middle value
         cout << setw( 3 ) << b[ i ] << '*';
      else
         cout << setw( 3 ) << b[ i ] << ' ';

   cout << endl;
}

// Fig. 4.22: fig04_22.cpp
// Initializing multidimensional arrays
#include <iostream>

using std::cout;
using std::endl;

void printArray( int [][ 3 ] );

int main()
{
   int array1[ 2 ][ 3 ] = { { 1, 2, 3 }, { 4, 5, 6 } },
       array2[ 2 ][ 3 ] = { 1, 2, 3, 4, 5 },
       array3[ 2 ][ 3 ] = { { 1, 2 }, { 4 } };

   cout << "Values in array1 by row are:" << endl;
   printArray( array1 );

   cout << "Values in array2 by row are:" << endl;
   printArray( array2 );

   cout << "Values in array3 by row are:" << endl;
   printArray( array3 );

   return 0;
}

void printArray( int a[][ 3 ] )
{
   for ( int i = 0; i < 2; i++ ) {

      for ( int j = 0; j < 3; j++ )
         cout << a[ i ][ j ] << ' ';

      cout << endl;
   }
}

// Fig. 4.23: fig04_23.cpp
// Double-subscripted array example
#include <iostream>

using std::cout;
using std::endl;
using std::ios;

#include <iomanip>

using std::setw;
using std::setiosflags;
using std::setprecision;

const int students = 3;   // number of students
const int exams = 4;      // number of exams

int minimum( int [][ exams ], int, int );
int maximum(int [][ exams ], int, int );
double average( int [], int );
void printArray( int [][ exams ], int, int );

int main()
{
   int studentGrades[ students ][ exams ] =
          { { 77, 68, 86, 73 },
            { 96, 87, 89, 78 },
            { 70, 90, 86, 81 } };

   cout << "The array is:\n";
   printArray( studentGrades, students, exams );
   cout << "\n\nLowest grade: "
        << minimum( studentGrades, students, exams )
        << "\nHighest grade: "
        << maximum( studentGrades, students, exams ) << '\n';

   for ( int person = 0; person < students; person++ )
      cout << "The average grade for student " << person << " is "
           << setiosflags( ios::fixed | ios::showpoint )
           << setprecision( 2 )
           << average( studentGrades[ person ], exams ) << endl;

   return 0;
}

// Find the minimum grade
int minimum( int grades[][ exams ], int pupils, int tests )
{
   int lowGrade = 100;

   for ( int i = 0; i < pupils; i++ )

      for ( int j = 0; j < tests; j++ )

         if ( grades[ i ][ j ] < lowGrade )
            lowGrade = grades[ i ][ j ];

   return lowGrade;
}

// Find the maximum grade
int maximum( int grades[][ exams ], int pupils, int tests )
{
   int highGrade = 0;

   for ( int i = 0; i < pupils; i++ )

      for ( int j = 0; j < tests; j++ )

         if ( grades[ i ][ j ] > highGrade )
            highGrade = grades[ i ][ j ];

   return highGrade;
}

// Determine the average grade for a particular student
double average( int setOfGrades[], int tests )
{
   int total = 0;

   for ( int i = 0; i < tests; i++ )
      total += setOfGrades[ i ];

   return static_cast< double >( total ) / tests;
}

// Print the array
void printArray( int grades[][ exams ], int pupils, int tests )
{
   cout << "                 [0]  [1]  [2]  [3]";

   for ( int i = 0; i < pupils; i++ ) {
      cout << "\nstudentGrades[" << i << "] ";

      for ( int j = 0; j < tests; j++ )
         cout << setiosflags( ios::left ) << setw( 5 )
              << grades[ i ][ j ];
   }
}