lab11exF2.cpp

//  lab11exF2.cpp
//
//  ENCM 339 Fall 2005 Lab 11 Exercise F
//
//  Second of two solutions.

#include <iostream>
#include <cassert>
using std::cout;

int strictly_increasing(const int *a, int n);

int main()
{
  int a[] = { 100 };
  int b[] = { 100, 200, 300, 400 };
  int c[] = { 400, 100, 200, 300 };
  int d[] = { 100, 400, 200, 300 };
  int e[] = { 100, 200, 200, 300 };
  int f[] = { 100, 200, 500, 300, 400 };
  int g[] = { 100, 200, 300, 500, 400 };

  assert( strictly_increasing(a, sizeof(a) / sizeof(int)) );
  assert( strictly_increasing(b, sizeof(b) / sizeof(int)) );
  assert( !strictly_increasing(c, sizeof(c) / sizeof(int)) );
  assert( !strictly_increasing(d, sizeof(d) / sizeof(int)) );
  assert( !strictly_increasing(e, sizeof(e) / sizeof(int)) );
  assert( !strictly_increasing(f, sizeof(f) / sizeof(int)) );
  assert( !strictly_increasing(g, sizeof(g) / sizeof(int)) );

  cout << "All tests passed.\n";
  cout << "This suggests that strictly_increasing is correct,\n";
  cout << "but it does NOT PROVE that it is correct.\n";

  return 0;
}

int strictly_increasing(const int *a, int n)
{
  int result, mid;
  assert(n > 0);
  if (n == 1)
    result = 1;
  else {
    mid = n / 2;
    result = (a[mid - 1] < a[mid]) 
      && strictly_increasing(a, mid) && strictly_increasing(a + mid, n - mid);
  }
  return result;
}