Write
a program to declare a square matrix A[ ] [ ] of order N (N < 20).
Allow
the user to input positive integers into this matrix. Perform the following tasks
on the matrix:
i. Output the original matrix.
ii. Find the SADDLE POINT for the matrix.
A saddle point is an element of the matrix
such that it is minimum element for the
row to which it belongs and the maximum element for the column to which it
belongs. Saddle point for a given matrix is always unique.
If the matrix has no saddle point, output the
message “NO SADDLE POINT”.
iii. Sort the element along principal
diagonal in ascending order using insertion sort technique.
All
other elements should remain unchanged. Test your program for the following
data:
Entered Matrix:
2
5 6 9
8
4 12 3
5
7 3 1
12
24 2 11
NO SADDLE POINT
Matrix after sorting principal diagonal:
2
5 6 9
8
3 12 3
5
7 4 1
12
24 2 11
Entered Matrix:
4
16 12
2
8 14
1
3 6
Saddle Point=4
Matrix after sorting principal diagonal:
4
16 12
2
6 14
1
3 8
The logic of the program is quite simple:
1. Input the order and elements of the array satisfying the given conditions
2. Find the saddle points and print them. If there si no saddle point
print appropriate message.
3. Using insertion sort, sort the principal diagonal only
4. Print the matrix
For finding the saddle point, we at first find the minimum element of any row,
following this note the coloumn position of this element and in that coloumn
check whether it is the maximum element or not. If that element is the maximum
element in the respective coloumn then that element will be the saddle point.
This will be done for each row. If none of the rows has any saddle point, the flag will remain at false, which will be required to print the appropraite message.
Folowing is the code for it:
for(int i=0;i<order;i++) {
min=mat[i][0];
for(int j=0;j<order;j++) {
if(mat[i][j]<min) {
min=mat[i][j];
col = j; // marking the coloumn of minimum element in ith row
}
} // end of for loop-j
for(int k=0;k<order;k++)
if(mat[k][col]>max) {
max=mat[k][col]; // finding maximum element in the respective coloumn
} // end of for loop-k
if(max==min) { //checking for saddle point
System.out.println("Saddle Point="+max);
flag=true;
}
} //end of for loop-i
if(flag==false)
System.out.println("NO SADDLE POINT");
Now for step 3, remember that only the elements of principal diagonal need to be sorted
using insertion sort. Once you know the algorith of insertion sort, it is easy to implement.
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.
The resulting array after k iterations has the property where the first k + 1 entries are sorted ("+1" because the first entry is skipped). In each iteration the first remaining entry of the input is removed, and inserted into the result at the correct position, thus extending the result:
Below is the code of insertion sort used in the program:
public void principalDiagonalSort() {
for (int i = 1; i < order; ++i) { // using insertion sort
int key = mat[i][i];
int j = i - 1;
while (j >= 0 && mat[j][j] > key) {
mat[j + 1][j+1] = mat[j][j];
j = j - 1;
}
mat[j + 1][j+1] = key;
}
System.out.println("Matrix after sorting principal diagonal:");
display();
}
Also for proper formatted display of the matrix elements, I have found out the
maximum element in the matrix (MAX_MATRIX) then the length of this element ahs been calculated by converting it into string.
Then before printing any element I am checking whether the length of the element is
less than the length of MAX_MATRIX. If it is then I am adding extra spaces till the
length becomes equal to the length of MAX_MATRIX.
Also for proper formatted display of the matrix elements, I have found out the
maximum element in the matrix (MAX_MATRIX) then the length of this element ahs been calculated by converting it into string.
Then before printing any element I am checking whether the length of the element is
less than the length of MAX_MATRIX. If it is then I am adding extra spaces till the
length becomes equal to the length of MAX_MATRIX.
public void display() {
for(int p=0;p<order;p++)
for(int q=0;q<order;q++)
if(MAX_MATRIX < mat[p][q])
MAX_MATRIX = mat[p][q];
String s,element;
s=Integer.toString(MAX_MATRIX);
for(int i=0;i<order;i++) {
for(int j=0;j<order;j++) {
element=Integer.toString(mat[i][j]); // for formatted output
int tmp=element.length();
while(tmp !=s.length()) {
element +=" ";
tmp++;
}
System.out.print(element+" ");
}
System.out.println();
}
}
COMPLETE JAVA CODE
import java.util.*;
public class ISC2003Q3 {
public static void main(String[] args) {
int N;
Scanner in = new Scanner(System.in);
do {
System.out.println("Enter the order of the square matrix:");
N = in.nextInt();
if(N>=20)
System.out.println("INVALID INPUT,TRY AGAIN");
}while(N>=20);
SaddlePoint obj = new SaddlePoint(N);
obj.inputElements();
System.out.println("Entered Matrix:");
obj.display();
obj.findSaddlePoint();
obj.principalDiagonalSort();
in.close();
}
}
class SaddlePoint {
public void principalDiagonalSort() {
for (int i = 1; i < order; ++i) { // using
insertion sort
int key = mat[i][i];
int j = i - 1;
while (j >= 0
&& mat[j][j] > key) {
mat[j + 1][j+1] = mat[j][j];
j = j - 1;
}
mat[j + 1][j+1] = key;
}
System.out.println("Matrix after sorting
principal diagonal:");
display();
}
public void findSaddlePoint() {
max=0;
for(int i=0;i<order;i++) {
min=mat[i][0];
for(int j=0;j<order;j++) {
if(mat[i][j]<min) {
min=mat[i][j];
col = j;
}
} // end of for loop-j
for(int k=0;k<order;k++)
if(mat[k][col]>max) {
max=mat[k][col];
} // end of for loop-k
if(max==min) {
System.out.println("Saddle Point="+max);
flag=true;
}
} //end
of for loop-i
if(flag==false)
System.out.println("NO SADDLE POINT");
}
public void display() {
for(int p=0;p<order;p++)
for(int q=0;q<order;q++)
if(MAX_MATRIX < mat[p][q])
MAX_MATRIX = mat[p][q];
String s,element;
s=Integer.toString(MAX_MATRIX);
for(int i=0;i<order;i++) {
for(int j=0;j<order;j++) {
element=Integer.toString(mat[i][j]); // for formatted output
int tmp=element.length();
while(tmp !=s.length())
{
element +=" ";
tmp++;
}
System.out.print(element+" ");
}
System.out.println();
}
}
public void inputElements() {
Scanner in = new Scanner(System.in);
System.out.println("Enter the values of the matrix:");
for(int i=0;i<order;i++) {
for(int j=0;j<order;j++) {
mat[i][j]=in.nextInt();
if(mat[i][j]<=0) {
System.out.println("Enter only positive values,try again:");
j--;
}
}
}
in.close();
}
SaddlePoint(int N){
order = N;
mat = new int[order][order];
MAX_MATRIX =0;
flag=false;
}
private boolean flag;
private int MAX_MATRIX;
private int[][] mat;
private int order;
private int max;
private int min;
private int col;
}
No comments:
Post a Comment