Saddle Point in Matrix Program in Java and Python
Saddle point in matrix program with algorithm, explanation, Java solution and simple Python solution for ISC students.
Question:
Write a program to input a square matrix and find its saddle point, if any. A saddle point is an element which is the smallest in its row and the largest in its column.
Algorithm:
Step 1: Start.
Step 2: Accept the order n of the square matrix.
Step 3: Input all elements of matrix A[n][n].
Step 4: Initialize found flag to 0.
Step 5: For each row i, assume A[i][0] is the row minimum and store column 0.
Step 6: Scan the row from column 1 to n - 1 and update minimum and column whenever a smaller value is found.
Step 7: Scan the stored column from row 0 to n - 1.
Step 8: If any element in that column is greater than the row minimum, stop checking that column.
Step 9: If the full column is checked without finding a greater value, display the saddle point and set found flag.
Step 10: If no saddle point is found after all rows, display No Saddle Point.
Step 11: Stop.
Explanation:
A saddle point must satisfy two conditions at the same time: it must be the smallest element in its row and the largest element in its column. The program checks these two conditions in that order.
For each row i, the program first assumes the first element of that row is the minimum. It then scans the remaining columns and updates min and col whenever a smaller value is found.
After finding the smallest value of the row, the program checks the column in which that value occurs. If any element in that column is greater than min, then the row minimum is not the largest in its column and cannot be a saddle point.
If the column scan completes without finding a greater element, the value is printed as the saddle point. The variable found records whether a saddle point has been found, so the program can display a suitable message when no saddle point exists.
A saddle point is an element that is the smallest in its row and the largest in its column, or as defined by the question. The program usually selects a candidate from each row by finding the row minimum. It then checks the same column to see whether that candidate satisfies the column condition. This avoids testing every element against every other element unnecessarily. The row and column indexes of the candidate must be preserved so that the column check is performed on the correct position.
Java Program:
/**
* The class SaddlePoint inputs a matrix of n*n size and finds its
* saddle point if any
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
* @Question Year : ISC 2003 Question 3 (Practical)
*/
import java.util.Scanner;
class SaddlePoint
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.print("Enter the order of the matrix : ");
int n=sc.nextInt();
int A[][]=new int[n][n];
System.out.println("Inputting the elements in the matrix");
System.out.println("******************************"); // Ignore these. They are just for styling
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
System.out.print("Enter Element at ["+i+"]["+j+"] : ");
A[i][j]=sc.nextInt();
}
}
/* Printing the Original Matrix */
System.out.println("******************************");
System.out.println("The Original Matrix is");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
System.out.print(A[i][j]+"\t");
}
System.out.println();
}
int max, min, x, f=0;
for(int i=0;i<n;i++)
{
/* Finding the minimum element of a row */
min = A[i][0]; // Initializing min with first element of every row
x = 0;
for(int j=0;j<n;j++)
{
if(A[i][j]<min)
{
min = A[i][j];
x = j; // Saving the column position of the minimum element of the row
}
}
/* Finding the maximum element in the column
* corresponding to the minimum element of row */
max = A[0][x]; // Initializing max with first element of that column
for(int k=0;k<n;k++)
{
if(A[k][x]>max)
{
max = A[k][x];
}
}
/* If the minimum of a row is same as maximum of the corresponding column,
then, we have that element as the Saddle point */
if(max==min)
{
System.out.println("********************");
System.out.println("Saddle point = "+max);
System.out.println("********************");
f=1;
}
}
if(f==0)
{
System.out.println("********************");
System.out.println("No saddle point");
System.out.println("********************");
}
}
}Equivalent Python Program:
# Read the matrix or array size and store the values for indexed processing.
# Nested loops are used because each row/column or array position must be checked.
# Print the processed array or matrix in the required output format.
n = int(input("Enter the order of the matrix: "))
A = []
print("Enter the elements:")
for i in range(n):
row = []
for j in range(n):
row.append(int(input()))
A.append(row)
found = 0
for i in range(n):
minimum = A[i][0]
col = 0
for j in range(1, n):
if A[i][j] < minimum:
minimum = A[i][j]
col = j
k = 0
while k < n:
if A[k][col] > minimum:
break
k = k + 1
if k == n:
print("Saddle Point =", minimum)
found = 1
break
if found == 0:
print("No Saddle Point")Output:
Leave a Reply
Your email address will not be published. Comments are reviewed before appearing publicly.