/*----------------------------------------------------------------------------
FILE NAME:     3hmwk.cpp
               SOLUTION RECOMMENDATIONS to HMW 3, JAN 2003

AUTHOR:        Stefano Basagni

CREATED:       January 2003

DESCRIPTION:   Example of a simple C++ program to test functions on arrays.

---
Copyright (C) 2003 Stefano Basagni

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

To receive a copy of the GNU General Public License write to
the Free Software Foundation, Inc., 59 Temple Place - Suite
330, Boston, MA 02111-1307, USA.

Stefano Basagni can be contacted at basagni@ece.neu.edu.

----------------------------------------------------------------------------*/
// INCLUDE SECTION
#include <iostream.h>
#include <iomanip.h>
#include <math.h>
#include <algo.h>
#include <string>

// Pseudo-random number generation
#include "rstream.h"

// CONSTANT SECTION
const int MAXINT = 65536;

// PROTOTYPES
// Initialize and array with random integer numbers
void initR( int A[], int n, int lb, int ub );

void printArray( int A[], int n );

void minMax( int n, int &min, int &max, int A[] );

bool twentyThree( int A[], int n );

void seventhPower( int n );

int maxR( int j, int A[] );

int maxDC( int l, int r, int A[] );

int BC( int n, int n );

int countElem( int A[], int j, int i );

//---------------------------------------------------------------------
// MAIN
int main() {

  int nn = 10;
  int AA[ nn ];  

  // Testing minMax
  initR( AA, nn, 0, 100 ); 
  int mi; 
  int ma;
  cout << "The min and max of the array: ";
  printArray( AA, nn );
  minMax( nn, mi, ma, AA );
  cout << "are: " << mi << " and " << ma << " respectively." 
       << endl;

  // Testing twentyThree
  initR( AA, nn, 0, 50 );
  cout << "In the array:";
  printArray( AA, nn );
  if ( twentyThree( AA, nn ) )
    cout << "there are two elements whose sum is 23" << endl;
  else
    cout << "there are no two elements whose sum is 23" << endl;
  initR( AA, nn, 0, 30 );
  cout << "In the array:";
  printArray( AA, nn );
  if ( twentyThree( AA, nn ) )
    cout << "there are two elements whose sum is 23" << endl;
  else
    cout << "there are no two elements whose sum is 23" << endl;

  // Testing seventhPower
  int bound = 0;
  while ( bound < 1 ) {
    cout << "Type a number > 0: ";
    cin >> bound;
  }
  cout << "The powers of 7 up to " << bound << " are: ";
  seventhPower( bound );

  // Testing the max functions
  initR( AA, nn, 0, 237 );
  cout << "The maximum of the array:";
  printArray( AA, nn );
  cout << "is: " << maxR( nn - 1, AA ) << " (first method), which is also: "
       << maxDC( 0, nn - 1, AA ) << " (D&C method)." << endl;

  // Testing the binomial coefficient
  int bc1 = -1;
  int bc2 = -1;
  while ( ( bc1 < 0 ) || ( bc2 < 0 ) || ( bc2 > bc1 ) ) {
    cout << "Inser two number > 0: n and k, k <= n: ";     
    cin >> bc1 >> bc2;
  }
  cout << "The binomial coeffient `" << bc1 << " choose " << bc2 
       << "' is: " << BC( bc1, bc2 ) << endl;

  // Testing countElem
  int elem;
  initR( AA, nn, 0, 4 );
  cout << "This is the array: " << endl;
  printArray( AA, nn );
  cout << "Insert the element the occurrences of which you want to count: ";
  cin >> elem;
  cout << elem << " appears " << countElem( AA, nn - 1, elem )
       << " times in the given array." << endl;


  return 0;

}
  

//---------------------------------------------------------------------
// FUNCTION DEFS
//---------------------------------------------------------------------
// Initialize and array with random integer numbers
void initR( int A[], int n, int lb, int ub ) {
  // Random stream for the positions
  static Rstream aElem( 1965 );
  for( int a = 0; a < n ; a++ ) 
	 A[ a ] = aElem.uniform_discrete( lb, ub );
}

//---------------------------------------------------------------------
// Print an array of n elements 
void printArray( int A[], int n ) {
  for( int a = 0; a < n; a++ )
    cout << A[ a ] << " ";
  cout << endl;
}

//---------------------------------------------------------------------
// Find min and max with min number of comparisons = (3/2)*n 
// (Problem 1)
void minMax( int n, int &min, int &max, int A[] ) {
  int k;
  if ( ( n % 2 ) == 0 ) {
    max = ( A[ 0 ] > A [ 1 ] )?( A[ 0 ] ):( A[ 1 ] );
    min = ( A[ 0 ] > A [ 1 ] )?( A[ 1 ] ):( A[ 0 ] );
    k = 2;
  }
  else {
    min = A[ 0 ];
    max = A[ 0 ];
    k = 1;
  }
  for( int i = k; i < n - 1; i = i + 2 )
    if ( A[ i ] > A[ i + 1 ] ) {
      if ( max < A[ i ] )
        max = A[ i ];
      if ( min > A[ i + 1 ] )
        min = A[ i + 1 ];
    }
    else {
      if ( max < A[ i + 1 ] )
        max = A[ i + 1 ];
      if ( min > A[ i ] )
        min = A[ i ];
    }
}

//---------------------------------------------------------------------
// Check for elements whose sum is 23 (Problem 2)
bool twentyThree( int A[], int n ) {
  bool S[ 24 ];
  for( int a = 0; a < 24; a++ )
    S[ a ] = false;
  for( int b = 0; b < n; b++ )
    if ( A[ b ] < 24 )
      S[ A[ b ] ] = true;
  for( int c = 0; c < 24; c++ )
    for( int d = c + 1; d < 24; d++ )
      if ( S[ c ] && S[ d ] && ( c + d == 23 ) )
        return true;
  return false;
}

//---------------------------------------------------------------------
// Prints out the powers of 7 up to n (Problem 3)
void seventhPower( int n ) {
  int power = 1;
  while ( power < n + 1 ) {
    cout << power << " ";
    power *= 7;
  }
  cout << endl;
}

//---------------------------------------------------------------------
// Find the max of an array recursively (Problem 4)
int maxR( int j, int A[] ) {
  if ( j == 0 )
    return A[ 0 ];
  else 
    return max( A[ j ], maxR( j - 1, A ) );
}

//---------------------------------------------------------------------
// Find the max of an array: D&C method (Problem 4)
int maxDC( int l, int r, int A[] ) {
  if ( r - l <= 1 )
    return max( A[ l ], A[ r ] );
  else 
    return max( maxDC( l, ( ( l + r ) / 2 ), A ),
                maxDC( ( ( l + r ) / 2 ) + 1, r, A ) );
}

//---------------------------------------------------------------------
// Recursive computation of the binomial coeffient (Problem 5)
int BC( int n, int k ) {
  if ( ( k == 0 ) || ( k == n ) ) 
    return 1;
  else
    return BC( n - 1, k - 1 ) + BC( n - 1, k );
}


//---------------------------------------------------------------------
// Count the occurrences of i (Problem 6)
int countElem( int A[], int j, int i ) {
  if ( j == 0 ) {
    if ( A[ 0 ] == i )
      return 1;
    else 
      return 0;
  }
  else
    if ( A[ j ] == i )
      return countElem( A, j - 1, i ) + 1;
    else
      return countElem( A, j - 1, i );
}