8.max-min problem

PROGRAM - VIII

(A) Problem Statement :

Write a program to implement maxmin problem by
using divide and conquer technique.

(B) Input and Output :

This program takes array of integers and gives the
maximum and minimum number in the array of integers.

(i) Enter no of elements in the list :5
Enter the element : 34
Enter the element : 67
Enter the element : 23
Enter the element : 56
Enter the element : 12
Maximum element is : 67
Minimum element is :12


(ii) Enter no of elements in the list :4
Enter the element :63
Enter the element : 72
Enter the element : 33
Enter the element : 56
Maximum element is : 72
Minimum element is : 33















(C) Examples :

(i)

- - 72 33







- - 12
12
-
- 67
23





23 56 56 23
12 - 12 12
34 67 67 34







33
56 56
33

(ii)






- - 67 12
63 72 72 63








(D)Algorithm:

Step 1: Start
Step 2: Read the n elements in to the array a.
Step 3: repeatedly do the following steps.
Step 4: if n is 1 then print max and min which is a[1] and
exit.
Step 5: if n is 2 then compare two elements and give max
and min values then print those values and exit.
Step 6: if n>2 then divide array into two sub arrays by
calculating mid = (beginning +end)/2
Step 7: find the maximum and minimum numbers in two
sub arrays in such way by dividing each array
into sub arrays until we can reach either step1 or
step2.
Step 8: combine sub arrays by giving maximum and
minimum numbers until we reach original array.
Step 9: Stop

(E) Program :

#include
#include
void maxmin(int a[],int i,int j,int *min,int *max)
{
int mid,max1,min1;
if(i==j) //if there is one element
*max=*min=a[i]; //min and max is same element
else if(i==j-1)
{ //if 2 elements
if(a[i]{
*max = a[j]; //and find min and max
*min = a[i];
}
else
{
*max = a[i];
*min = a[j];
}
}
else
{
// if p is not small, divide p into subproblems
// find where to spilt into the set
mid = (i+j)/2;
//solve the sub problems.
maxmin(a,i,mid,min,max);
maxmin(a,mid+1,j,&min1,&max1);
//combine the solutions
if(*max*max=max1;
if(*min>min1)
*min=min1;
}
}
void main()
{
int i,a[20],n,min,max;
clrscr(); //read no of elements in list
printf("\n enter the no of elements in the list:");
scanf("%d",&n);
for(i=1;i<=n;i++) //read elements
{
printf("\n enter the element:");
scanf("%d",&a[i]);
}
maxmin(a,1,n,&min,&max); //call maxmin function
printf("\n Maximum element is:%d",max); //print max
printf("\n Minimum element is:%d",min); //print min
getch();
}


(F) Testing :
This program can be tested to find maximum and
minimum value for the given list of size 20.


(G) Limitations:
(i) The maximum number of elements in the array is
restricted to 20 elements.