//Date: 2003.01.31
//Author: AOU
//File: areDistinct3.cpp
/*
develop searchSeq function
develop testSearchSeq function
incorporate searchSeq in areDistinct
*/
///////////////////////////////////////////////////////////
// include files
///////////////////////////////////////////////////////////
#include <iostream.h>
#include <stdlib.h>
///////////////////////////////////////////////////////////
// prototypes
///////////////////////////////////////////////////////////
bool areDistinct(int a[], int n);
void populate(int a[], int &n);
void display(int a[], int n);
void testAreDistinct(void);
bool searchSeq(int a[], int n, int x);
void testSearchSeq(void);
///////////////////////////////////////////////////////////
// constants
///////////////////////////////////////////////////////////
const int MAX_COUNT = 10; //maximum size of array
const int MAX_VALUE = 5;
///////////////////////////////////////////////////////////
// main function
///////////////////////////////////////////////////////////
void main(void)
{
testAreDistinct();
testSearchSeq();
}
///////////////////////////////////////////////////////////
// void testSearchSeq(void)
///////////////////////////////////////////////////////////
void testSearchSeq(void)
{
cout << "testSearchSeq\n";
cout << "=============\n";
int a[MAX_COUNT];
int n;
int x;
for (int p=1; p <= 10; p++)
{
cout << "Case #" << p << endl;
populate(a, n);
display(a, n);
x = rand()%(MAX_VALUE+1);
if (searchSeq(a, n, x))
cout << x << " is in the Array\n";
else
cout << x << " is NOT in the Array\n";
cout << "--------------------------------------\n";
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
/*
Algorithm:
do the following for i=0 to n-1
if x = a[i] then
return true
next i
return false
*/
bool searchSeq(int a[], int n, int x)
{
for (int i=0; i<=n-1; i++)
if (x == a[i])
return true;
return false;
}
///////////////////////////////////////////////////////////
// void testAreDistinct(void)
///////////////////////////////////////////////////////////
void testAreDistinct(void)
{
cout << "testAreDistinct\n";
cout << "===============\n";
int a[MAX_COUNT];
int n;
for (int p=1; p <= 10; p++)
{
cout << "Case #" << p << endl;
populate(a, n);
display(a, n);
if (areDistinct(a, n))
cout << "Array has distinct values\n";
else
cout << "Array does not have distinct values\n";
cout << "--------------------------------------\n";
}
}
///////////////////////////////////////////////////////////
// bool areDistinct(int a[], int n)
///////////////////////////////////////////////////////////
/* A function to check if all the values are unique/distinct
Algorithm
if n <= 1 then
return true
else
do the following for i=1 to n-1
do the following for j=0 to i-1
if a[i] = a[j] then
return false
next j
next i
return true
*/
bool areDistinct(int a[], int n)
{
if (n <= 1)
return true;
else
{
for (int i=1; i<=n-1; i++)
if (searchSeq(a, i, a[i]))
return false;
/*
for (j=0; j<=i-1; j++)
if (a[i] == a[j])
return false;
*/
return true;
}
}
///////////////////////////////////////////////////////////
// void populate(int a[], int &n)
///////////////////////////////////////////////////////////
//A function to fill an array (a) with random values
/*
Algorithm
n = random number between 0 to MAX_COUNT
do the following for i=0 to n-1
a[i] = random number between 0 to MAX_VALUE
*/
void populate(int a[], int &n)
{
n = rand()%(MAX_COUNT+1);
for (int i=0; i<=n-1; i++)
a[i] = rand()%(MAX_VALUE+1);
}
///////////////////////////////////////////////////////////
// void display(int a[], int n)
///////////////////////////////////////////////////////////
void display(int a[], int n)
{
cout << "a[" << n << "]=";
for (int i=0; i<=n-1; i++)
cout << a[i] << ' ';
cout << endl;
}
///////////////////////////////////////////////////////////
// SAMPLE OUTPUT
///////////////////////////////////////////////////////////
/*
testAreDistinct
===============
Case #1
a[8]=5 4 4 5 4 0 0 4
Array does not have distinct values
--------------------------------------
Case #2
a[0]=
Array has distinct values
--------------------------------------
Case #3
a[7]=5 1 3 1 5 1 2
Array does not have distinct values
--------------------------------------
Case #4
a[9]=0 3 0 2 3 4 4 3 2
Array does not have distinct values
--------------------------------------
Case #5
a[6]=5 5 0 5 0 3
Array does not have distinct values
--------------------------------------
Case #6
a[2]=5 1
Array has distinct values
--------------------------------------
Case #7
a[7]=0 5 3 2 3 3 2
Array does not have distinct values
--------------------------------------
Case #8
a[5]=1 5 4 5 2
Array does not have distinct values
--------------------------------------
Case #9
a[3]=3 3 1
Array does not have distinct values
--------------------------------------
Case #10
a[0]=
Array has distinct values
--------------------------------------
testSearchSeq
=============
Case #1
a[6]=1 4 4 5 2 0
0 is in the Array
--------------------------------------
Case #2
a[10]=4 2 4 4 2 3 2 3 4 2
0 is NOT in the Array
--------------------------------------
Case #3
a[4]=3 2 3 5
0 is NOT in the Array
--------------------------------------
Case #4
a[0]=
0 is NOT in the Array
--------------------------------------
Case #5
a[4]=4 2 5 4
0 is NOT in the Array
--------------------------------------
Case #6
a[0]=
2 is NOT in the Array
--------------------------------------
Case #7
a[4]=5 4 2 0
3 is NOT in the Array
--------------------------------------
Case #8
a[8]=3 5 1 0 0 0 3 2
5 is in the Array
--------------------------------------
Case #9
a[1]=5
5 is in the Array
--------------------------------------
Case #10
a[7]=4 0 3 5 3 3 0
4 is in the Array
--------------------------------------
Press any key to continue
*/
|