I need help with a small C++ assignment

[Paschim]

I need to write a program in c++ to find the saddle point of a matrix, and the order of the matrix should be user defined.Plz can anyone help me?

 

[vandit]

Guys dont laugh on this one......

What is the saddle point of the matrix?

 

[Zeeshan Quireshi]

well saddle point is a point which is the smallest ion the row and largest in the column of a matrix .

 

[casanova]

@vandit
A saddle point is an element of the matrix which is both the smallest element in its row and the largest element in its column is called saddle point.

Dont forget to add to my repo. Here, it is

#include<iostream.h>
#include<conio.h>

void main()
{
clrscr();
int a[10][10],i,j,k,sp,minr,pos,flag=1,row,col,saddlepoints[10];
cout<<"Enter no of rows :: ";
cin>>row;
cout<<"Enter no of columns :: ";
cin>>col;
cout<<"Enter the contents of the array :: ";
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
cin>>a[j];
}
cout<<"The matrix representation of array is: ";
for(i=0;i<row;i++)
{
cout<<"\n";
for(j=0;j<col;j++)
cout<<a[j]<<" ";
}
cout<<endl;
for(i=0;i<row;i++)
{
flag=1;
sp=a[0],pos=0;
for(j=1;j<col;j++)
{
if(a[j]<sp)
{
sp=a[j];
pos=j;
}
}
for(k=0;k<row;k++)
{
if(a[k][pos]>sp)
{
flag=0;
break;
}
}
cout<<"The saddle point of row "<<i+1<<" is "<<sp<<endl;
saddlepoints=sp;
}
sp=saddlepoints[0];
for (i=1;i<row;i++)
{
if (sp<saddlepoints)
sp=saddlepoints;
}
cout<<"The saddle point of matrix is "<<sp<<endl;
getch();
}

 

[shaunak]

i still didnt understand abt "saddle point"
in the following array which would b the saddle point?
1 2 3 4
4 3 2 1

as 1 is the smallest element of row1 but of column1 4 is the largest element.
which is the saddle piont?

 

[casanova]

Dont have enough idea abt that, came to know abt saddlepoint from wikipidea and did the proggy.
For ur ques, my prog returns 1 as saddle point. But dont know what it shud return. Paschim shud hav a better idea.
As far as I know abt this type of programs, these things are only for special cases
e.g sparse matrix for more zero elements than non-zero elements

 

[Paschim]

Actually it should only work with a square matrix.However thx to casanova I hav made a few modifications and all was hunky&dory untill my teach said I had to make it class based proggy.Any help guys??

 

[casanova]

^^^
Till wat date do u have to submit the proggy. I wudnt be free till saturday.

Wat u can do is make a class saddle and a function say find_saddle() in that class and call it. Do post the updated proggy. I will try to make a class based proggy by 2morow night. Cant guarantee though.

 

[sakumar79]

Should the saddle point represent the location of the number (row, column) rather than just the number? In that case, the above program should be tweaked a bit...

Arun

 

[Paschim]

Should the saddle point represent the location of the number (row, column) rather than just the number? In that case, the above program should be tweaked a bit...

Arun

Nah... i just need it to display whether the entered matrix has a saddle point or not and if yes display that number.

And casanova....a saddle point is unique to a matrix....there can be no saddle point for every row but as a whole matrix.

 

[siriusb]

Hey paschim, most articles on saddle point on the net state that it's not just THE minimum col value and THE maximum row value but a local mimum and maximum. If that's so, then the above prog will not be correct. (link)
Sorry if I am wrong. I am just now looking through articles for saddle points after seeing this thread. I am writing a c++ saddle point finder right now.

 

[abhishekkulkarni]

How to find the Saddle Point -

Let us consider this Matrix -

1 2 3
4 5 6
7 8 9

Step 1 -

Build a Column Matrix containing the greatest values from all the Rows -

That matrix would be -

3
6
9

Step 2 -

Build a Row Matrix containing the Smallest values from all the Columns -

That matrix would be -

[ 1 2 3 ]

Step 3 -

Find the Smallest Element from the newly created Column Matrix . In our case it is 3 .

Step 4 -

Find the Largest Element from the newly created Row Matrix . In our case it is 3 .

Step 5 -

If both these elements are equal then a Saddle Point exists for the given Matrix and is defined as -
The Saddle Point for the given Matrix is 3 ( ie - the common element ) .

This element ( which is 3 in this case ) is the Saddle Point of the considered Matrix .


Here is a Code segment which finds the Saddle Point according to the above mentioned algorithm -

saddlepointa(int a1[10][10],int rowa,int cola)
{
int big[10],small[10],i,j,max,min;
clrscr();
big[0]=a1[0][0];
for(i=0;i<rowa;i++)
{
for(j=0;j<cola;j++)
{
if(a1[j] > big)
{
big = a1[j];
}
}
}
for(j=0;j<cola;j++)
{
small[j]=a1[0][j];
for(i=0;i<rowa;i++)
{
if(a1[j] < small[j])
{
small[j]=a1[j];
}
}
}
min=big[0];
for(i=0;i<rowa;i++)
{
if(big < min)
{
min = big;
}
}
max=small[0];
for(j=0;j<cola;j++)
{
if(small[j] > max)
{
max = small[j];
}
}
if(max==min)
{
printf("\n\n\n\t\t\tTHE SADDLE POINT IS --> %d ",min);
}
else
{
printf("\n\n\n\nNO SADDLE POINT");
}
getch();
return 0;

}

 

[siriusb]

My saddle.cpp

I see two different definitions for saddle points in a matrix. One is the above one and the other is like this. Both produce different results with the same matrix! Obviously, one of them must not apply and I am just confusing everyone here. Maybe the OP can help.

Anyways, here's the class based implementation I am working on. I want to clean up the code and make it template based later. The definition is the one from wikipedia.

#include <iostream.h>
#include <alloc.h>
#include <stdlib.h>
#include <limits.h>


class SaddlePoint
{
private:
struct spstruct
{
	int value;
	int idx;
};

/*int *imatrix;*/

spstruct *mincol;  //LUT of max of each cols.
spstruct *maxrow;  //LUT of max of each rows.
int  rccount; //Number of rows or cols in the LUTs.
char isLoaded;//Flag to check if the LUTs have been initialized.
int  spcount; //Saddle point count.


public:
SaddlePoint()
{
	isLoaded = 0;
	spcount  = -1;
}

~SaddlePoint ()
{
	delete[] mincol;
	delete[] maxrow;
}

char LoadMatrix (int *thematrix, int rows, int cols)
{
	/*Do some preliminary checks*/
	//Is it a valid row and col value?
	if (rows > 0 && cols > 0)
	{
		//Is it a square matrix?
		if (rows == cols)
		{
			//if (sizeof (thematrix) == rows * cols * sizeof(int))
			//{
				rccount = cols;
			//}
			//else
			//{
			//	cout<< "Matrix size does not match size params!";
			//	return (-1);
			//}
		}
		else
		{
			cout<<"Only square matrices (for now)";
			return (-1);
		}
	}

	isLoaded = 0;
	maxrow = new spstruct[rccount];
	mincol = new spstruct[rccount];
	for (int i = 0; i < rccount; i++)
	{
		maxrow[i].value = INT_MIN;
		mincol[i].value = INT_MAX;
	}

	/*TODO::Allocate space for a local copy of the input matrix
	imatrix = (int *)malloc (rccount * 2 * sizeof (int));
	int i = 0;
	for i = 0 to
	*/

	/*Find the max from column and min from row
	and fill teh LUT*/
	int irow, icol;

	for (irow = 0; irow < rccount; irow++)
	{
		for (icol = 0; icol < rccount; icol++)
		{
			if (thematrix[icol + (irow * rccount)] > maxrow[irow].value)
			{
				//Record the value and the col index of the value.
				maxrow[irow].value = thematrix[(irow * rccount) + icol];
				maxrow[irow].idx   = icol;
			}

			if (thematrix[irow + (icol * rccount)] < mincol[irow].value)
			{
				//Record the value and record the row index of the value.
				mincol[irow].value = thematrix[irow + (icol * rccount)];
				mincol[irow].idx   = irow;
			}

		}
	}



	/*//Print the LUT for debugging.
	cout<< endl<< "This is the matrix and the LUTs:"<< endl;

	for (irow = 0; irow < rccount; irow++)
	{
		cout<< "|";
		for (icol = 0; icol < rccount; icol++)
		{
			cout<< thematrix [icol + (irow * (rccount))];
			if (icol < rccount-1)
				cout<< "\t";
		}
		cout<< "| |"<< maxrow[irow].value<< "|"<< endl;
	}

	cout<< endl<< "|";

	for (icol = 0; icol < rccount; icol++)
	{
		cout<< mincol[icol].value;
		if (icol < rccount-1)
			cout<< "\t";
	}

	cout<< "|"<< endl;*/


	isLoaded = 1;
	return (1);
}


int SaddlePointPresent ()
{
	if (isLoaded != 1)
	{
		/*Load a matrix first using the LoadMatrix() function.*/
		spcount = -1;
		return  (-1);
	}

	/*See if there's a saddle point at all
	and return the number of saddle points.*/
	spcount = 0;

	for (int i = 0; i < rccount; i++)
	{
		if (mincol[i].value == maxrow[i].value)
		{
			spcount++;
		}
	}


	return (spcount);

}

int PrintSaddlePoints ()
{
	if (SaddlePointPresent () == -1)
	{
		return (-1);
	}

	cout<< endl<< "Found "<< spcount<< " saddle points."<< endl;

	if (spcount < 1)
	{
		return (0);
	}
	/*Now to extract them saddles*/
	//int **spoints;
	//spoints = malloc(spcount * sizeof (int) * 2);
	for (int i = 0; i < rccount; i++)
	{
		if (mincol[i].value == maxrow[i].value)
		{
			cout<< mincol[i].value<< " at ("<< maxrow[i].idx<< ", "<<mincol [i].idx<< ")"<< endl;
		}
	}

	return (spcount);
}

};//End of class

void main()
{
	int *imatrix;
	int rows = 0, cols = 0;
	int irow, icol;

	cout<< "\nHow many rows?->";
	cin>> rows;
	cout<< "How many cols?->";
	cin>> cols;

	imatrix = new int[rows * cols];
	//if ( (imatrix = (int *)malloc (rows * cols * sizeof(int))) == NULL)
	if (imatrix == NULL)
	{
		cout<< "Not enough memory to allocate buffer\n";
		exit (1);  /* terminate program if out of memory */
	}

	cout<< "\n:Now enter the elements of the matrix:"<< endl;

	for (irow = 0; irow < rows; irow++)
	{
		for (icol = 0; icol < cols; icol++)
		{
			cout<< "("<< irow<< ", "<< icol<< ")-->";
			cin>> imatrix [icol + (irow * (cols))];
		}
	}

	cout<< endl<< "This is the matrix:"<< endl;

	for (irow = 0; irow < rows; irow++)
	{
		cout<< "|";
		for (icol = 0; icol < cols; icol++)
		{
			cout<< imatrix [icol + (irow * (cols))];
			if (icol < cols-1)
				cout<<"\t";
		}
		cout<< "|"<< endl;
	}


	SaddlePoint sp;
	if (sp.LoadMatrix (imatrix, rows, cols) == -1)
	{
		cout<< "Unable to load the matrix.";
		exit (1);
	}
	sp.PrintSaddlePoints();


	delete[] imatrix;
	system ("PAUSE");
}

Unfortunately, my code has one logical error which only becomes evident with some multiple saddle point matrices. I'll try to correct it.