(Problem
1),
(10 pts)
Run
fig04_19.cpp
on page 269 and then:
(1) Use
rand()
to generate 100 random numbers, then place the random number to the
array.
(2)
Increase
the array size as large as possible until your computer can't handle it.
Hand
in the version you modified, which meets the following two conditions:
(a)
The array size is almost reach the limit. (b) It still works on the PC
in the Lab.
(Problem
2),
(10 pts)
Run
fig04_20.cpp
on page 271 and then:
(1) Use
rand()
to generate 15 random numbers (between 1 -100), place the random
number to an array.
(2) Use
hw-4-11(a)
to sort the 15 random numbers, and then search a number.
(Problem
3), 4-33,
on page 303. (10 pts)
A suggested
solution
is posted below Your job is to decrease the array
size
to 50, then use
rand() to
generate
50 random numbers, then place the random number to the array. And
then
do the linear
search.
(Problem
4), 4-34,
on page 303. (10 pts)
A suggested
solution
is posted below Your job is to increase the array
size
to 50, then use
rand() to
generate
50 random numbers, then place the random number to the array. And
then
use
hw-4-11(a)
to sort the 50 random numbers, And then do the Binary search.
using std::cout;
using std::endl;
using std::cin;
int linearSearch( const int [], int, int, int );
int main()
{
const int SIZE = 100;
int array[ SIZE ], searchKey, element;
for ( int loop = 0; loop < SIZE;
++loop
)
array[ loop ] = 2 *
loop;
cout << "Enter the integer
search key:
";
cin >> searchKey;
element = linearSearch( array, searchKey, 0, SIZE - 1 );
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 low,
int high )
{
if ( array[low] == key )
return low;
else if ( low == high )
return -1;
else
return linearSearch(
array,
key, low + 1, high );
}
// Exercise 4.34 Solution
#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <iomanip>
using std::setw;
const int SIZE = 15;
int binarySearch( const int [], int, int, int );
void printRow( const int [], int, int, int );
void printHeader( void );
int main()
{
int a[ SIZE ], key, result;
for ( int i = 0; i < SIZE; ++i )
a[ i ] = 2 * i;
cout << "Enter a number
between 0 and
28: ";
cin >> key;
printHeader();
result = binarySearch( a, key, 0, SIZE
-
1 );
if ( result != -1 )
cout << '\n'
<<
key << " found in array element " << result << endl;
else
cout << '\n'
<<
key << " not found" << endl;
return 0;
}
int binarySearch( const int b[], int searchKey,
int low,
int high )
{
int middle;
if ( low <= high ) {
middle = ( low +
high
) / 2;
printRow( b, low,
middle,
high );
if ( searchKey ==
b[ middle
] )
return
middle;
else if ( searchKey
<
b[ middle ] )
return
binarySearch( b, searchKey, low, middle - 1 );
else
return
binarySearch( b, searchKey, middle + 1, high );
}
return -1; // searchKey
not found
}
// Print a header for the output
void printHeader( void )
{
cout << "Subscripts:\n";
for ( int i = 0; i < SIZE; ++i )
cout << setw(
3
) << i << ' ';
cout << '\n';
for ( int k = 1; k <= 4 * SIZE;
++k )
cout << '-';
cout << '\n';
}
// 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
)
{
for ( int i = 0; i < SIZE; ++i )
if ( i < low || i
>
high )
cout
<< " ";
else if ( i == mid )
cout
<< setw( 3 ) << b[ i ] << '*'; //
mark
middle value
else
cout
<< setw( 3 ) << b[ i ] << ' ';
cout << '\n';
}