These puzzles involve arrays.
[E-6]
Write a function that evaluates to the maximum of an integer array.
Here is a framework:
#include <stdio.h>
#include <stdlib.h>
/* Puzzle 21 -- find the maximum element in an integer array */
int findLargest( int arr[], int size )
{
...
}
/* Functions from previous puzzles */
int randInt( int min, int max );
void printArray( int arr[], int size );
void fillArrayRandom( int arr[], int size, int low, int high );
int main(int argc, char *argv[])
{
const int SIZE = 60;
int x[ SIZE ];
int max;
srand( time(NULL) );
fillArrayRandom( x, SIZE, 0, 99 );
printArray( x, SIZE );
printf("\n");
max = findLargest( x, SIZE );
printf("Max = %d\n", max );
printf("\n\n");
system("pause");
return 0;
}
Here is sample output:
19 51 58 47 30 27 58 87 32 52 17 28 78 32 63 9 50 62 38 65 91 41 17 14 85 41 63 79 69 83 60 17 3 45 50 7 72 64 0 79 53 45 28 33 29 46 10 36 60 54 17 31 15 20 73 58 73 62 9 21 Max = 91
For any array with one or more elements there will be a largest element. If all elements are the same value, then that is the maximum. Be sure to consider the possibility that some or all elements are negative.
You will need a variable that holds the current maximum. How should it be initialized?
[E-10]
Write function, similar to the previous, that finds the
largest element in a sub-array of an integer array.
The sub-array consists of the array cells indexed
between
indices low and high, inclusive.
Here is the output of a testing program,
where low==10 and high==19.
34 59 69 19 83 25 99 23 36 33 17 36 35 1 72 28 69 30 9 85 59 64 33 37 49 19 88 13 99 33 73 28 85 59 26 34 8 63 88 34 25 44 9 86 82 43 85 6 80 53 83 96 57 2 65 89 97 14 55 64 Max = 85
[E-10]
Write a function that searches for the first instance of a target value in an
integer array. Return the index of the element if it is there, or -1 if the
element is not there. Here are two runs of the testing program:
0 1 2 3 4 5 6 7 8 9 Element 7 found at index 7 0 1 2 3 4 5 6 7 8 9 Element 99 not found
Here is a testing program. You might want to add code so that the target value comes from user input or from a command line argument:
int linearSearch( int arr[], int size, int x )
{
....
}
void printArray( int arr[], int size );
int main(int argc, char *argv[])
{
const int SIZE = 10;
int x[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int loc, target;
printArray( x, SIZE );
target = 7;
loc = linearSearch( x, SIZE, target );
if ( loc != -1 )
printf("Element %d found at index %d\n", target, loc );
else
printf("Element %d not found\n", target);
printf("\n");
system("pause");
return 0;
}
[E-5]
Write a function that searches for the first instance of
a target value
in an integer array that is at or beyond a particular index. Return the index
of the element if it is there, or -1 if the element is not there.
[M-15]
Write a function that searches for the value in an integer array
that is closest to a target value. Return the index of the element. If several
elements are equally close to the target, return the index of the first one.
Here is a testing program:
#include <stdio.h>
#include <stdlib.h>
/* Puzzle C25 -- find the element in an
| array closest to a particular value
*/
int linearSearchClosest( int arr[], int size, int target )
{
}
int main(int argc, char *argv[])
{
const int SIZE = 10;
int x[] = { -5, -3, 0, 6, 4, 16, -3, 0, 7, 9 };
int loc, target;
char input[32];
printf("target:");
scanf("%s", input );
while ( strcmp( input, "q" ) != 0 )
{
target = atoi( input );
loc = linearSearchClosest( x, SIZE, target );
printf("Closest element to %d found at index %d\n",
target, loc );
printf("target:");
scanf("%s", input );
}
system("pause");
return 0;
}
Here is sample output of the testing program. The user enters a value for the target after the prompt:
-5 -3 0 6 4 16 -3 0 7 9 target:6 Closest element to 6 found at index 3 target:5 Closest element to 5 found at index 3 target:3 Closest element to 3 found at index 4 target:-9 Closest element to -9 found at index 0 target:23 Closest element to 23 found at index 5 target:0 Closest element to 0 found at index 2 target:q
The testing program allows the user to enter targets. The user enters "q" to end the program.
[E-5]
Write a function that looks for x and y in sequence among the elements of an
integer array. Return the index of the first element x, or -1 if the sequence
is not found. Here is the output of a testing program.
The testing program is based on the previous one:
-5 -3 0 6 4 16 -3 0 7 9 x y: 6 4 6, 4 found at index 3 x y: 4 16 4, 16 found at index 4 x y: 6 0 sequence not found x y: -3 0 -3, 0 found at index 1 x y: 16 -3 16, -3 found at index 5 x y: q
Modifying the testing program will be harder than writing the actual search function.
[H-25]
Write a function that checks that both x and y are in an integer array, but
not necessarily one right after the other, and not necessarily
in order. Return the number of elements between x and y if they are both there,
and -1 if they are not both there. If there are several elements x or y, return
the number of elements between the x and y that are closest together.
If both x and y are the same value, then look for two instances of that value in the array. Here is a testing framework:
int distBetweenElts( int arr[], int size, int x, int y )
{
. . . .
}
void printArray( int arr[], int size );
/* Get user input, x and y. Return 0 if
| the user wants to quit, otherwise return 1
*/
int userInput( int *x, int *y )
{
char inputX[32], inputY[32];
printf("x y: ");
scanf("%s", inputX );
if ( !isdigit((int)inputX[0]) && inputX[0] != '-' )
return 0;
else
{
scanf("%s", inputY );
*x = atoi( inputX );
*y = atoi( inputY );
return 1;
}
}
int main(int argc, char *argv[])
{
const int SIZE = 10;
int arr[] = { -5, -3, 0, 6, 4, 16, -3, 0, 7, 9 };
int min, x, y;
printArray( arr, SIZE );
while ( userInput( &x, &y ) )
{
min = distBetweenElts( arr, SIZE, x, y );
if ( min != -1 )
printf("minimum distance %d\n", min );
else
printf("Failed to find both elements.\n");
}
system("pause");
return 0;
}
This puzzle is much more difficult than the previous puzzles. Here is sample output of a testing program:
-5 -3 0 6 4 16 -3 0 7 9 x y: 0 6 minimum distance 0 x y: 0 4 minimum distance 1 x y: 4 0 minimum distance 1 x y: 7 8 Failed to find both elements. x y: 8 8 Failed to find both elements. x y: 7 7 Failed to find both elements. x y: 0 7 minimum distance 0 x y: -3 -3 minimum distance 4 x y: -5 9 minimum distance 8 x y: q
[M-7]
Write a program that examines an integer array of N elements and determines
if all the integers 0..N-1 are in the array. The integers need not be in order.
Return the smallest integer in the range 0..N-1 that is not found in the array,
or -1 if all integers are there.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 99 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 Element 32 missing
Here is a testing framework:
#include <stdio.h>
#include <stdlib.h>
int fullArrayCheck( int arr[], int size )
{
. . .
}
void fillArrayInOrder( int arr[], int size, int first )
{
int j;
for ( j=0; j < size; j++ )
{
arr[j] = first+j;
}
}
void printArray( int arr[], int size )
{
const int N = 10;
int j;
for ( j=0; j < size; j++ )
{
if ( j%N == N-1 )
printf("%4d\n", arr[j] );
else
printf("%4d ", arr[j] );
}
}
#define SIZE 50
int main(int argc, char *argv[])
{
int x[SIZE] ;
int target ;
fillArrayInOrder( x, SIZE, 0 );
x[ 32 ] = 99 ;
printArray( x, SIZE );
printf("\n");
if ( (target = fullArrayCheck( x, SIZE )) == -1 )
printf("All elements present\n");
else
printf("Element %d missing\n", target);
system("pause");
return 0;
}
[E-7]
Write a function that deletes the element at index N in an array, and fills
the gap by moving elements above N downward by one. Put a 0 in the last element.
If index N does not exist, do nothing to the array. Return 1 if the deletion
was performed, 0 if not.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 delete at index:15 Failure 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 delete at index:14 Success 0 1 2 3 4 5 6 7 8 9 10 11 12 13 0 delete at index:6 Success 0 1 2 3 4 5 7 8 9 10 11 12 13 0 0 delete at index:
If asked to delete one of the zeros at the end of the array, the function does so, even though this has no effect. Here is a testing framework:
#include <stdio.h>
#include <stdlib.h>
int deleteElement( int arr[], int size, int n )
{
. . .
}
void printArray( int arr[], int size )
{
const int N = 10;
int j;
for ( j=0; j < size; j++ )
{
if ( j%N == N-1 )
printf("%4d\n", arr[j] );
else
printf("%4d ", arr[j] );
}
}
void fillArrayInOrder( int arr[], int size, int first )
{
int j;
for ( j=0; j < size; j++ )
{
arr[j] = first+j;
}
}
int main(int argc, char *argv[])
{
const int SIZE = 25;
int x[SIZE];
char input[32];
int del ;
fillArrayInOrder( x, SIZE, 0 );
printArray( x, SIZE );
printf("\ndelete at index:");
gets( input );
while ( strcmp( input, "q") != 0 )
{
del = atoi( input );
if ( deleteElement( x, SIZE, del ) )
printf("Success\n\n");
else
printf("Failure\n\n");
printArray( x, SIZE );
printf("\ndelete at index:");
gets( input );
}
system("pause");
return 0;
}
[E-7]
Write function that inserts a value at index N in an array. First it moves
all elements above index N upward. The last element is discarded. If index N
does not exist, do nothing to the array. Return 1 if the insertion was performed,
0 if not.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 value place: 99 0 Success 99 0 1 2 3 4 5 6 7 8 9 10 11 12 13 value place: 77 9 Success 99 0 1 2 3 4 5 6 7 77 8 9 10 11 12 value place:
— Return to the main contents page