finding second maximumin array

hey! i have to find the second maximum in an array by a recursive

Page 1 of 1

13 Replies - 1928 Views - Last Post: 16 January 2009 - 11:13 AM Rate Topic: -----

#1 drordh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 15-January 09

finding second maximumin array

Post icon  Posted 15 January 2009 - 03:45 AM

//A recursive program to find the second maximal element in an array.
#include <iostream.h>

#define SIZE 10
int static max1=0;
int static max2=0;



int max (int arr[SIZE],int s)//recursive function to find the second maximal
{
	if(s>=0)//recursive condition
	{
		if (max1<arr[s])//put the value in max1?
		{
			if (max1>max2)
				max2=max1;
			max1=arr[s];
		}
		else//no, put it in max2
			if (max2<arr[s])
			{
				if (max2>max1)
					max1=max2;
				max2=arr[s];
			}
			max(arr,s-1);//recursive calling
	}
	else
		if(max1>max2)
			return max2;
		else
			return max1;
}

void main() 
{
	int s=0;
	int arr[SIZE]={14,98,50,2,24,61,88,13,55,7};
	
	s=SIZE;
	cout <<"The second maximum is:"<<max(arr,s-1)<<"\n";
}



** Edit ** :code:

Is This A Good Question/Topic? 0
  • +

Replies To: finding second maximumin array

#2 stefan.jacobs  Icon User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 6
  • Joined: 09-December 08

Re: finding second maximumin array

Posted 15 January 2009 - 03:59 AM

What seems to be the problem ?
Was This Post Helpful? 0
  • +
  • -

#3 no2pencil  Icon User is offline

  • Admiral Fancy Pants
  • member icon

Reputation: 5411
  • View blog
  • Posts: 27,424
  • Joined: 10-May 07

Re: finding second maximumin array

Posted 15 January 2009 - 04:14 AM

Please post your question in the message body & not in the subject.
Was This Post Helpful? 0
  • +
  • -

#4 drordh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 15-January 09

Re: finding second maximumin array

Posted 15 January 2009 - 04:14 AM

View Poststefan.jacobs, on 15 Jan, 2009 - 02:59 AM, said:

What seems to be the problem ?


my programme finding the second maximum, but the way is not good.
i had to do that in recursive way and not with recursia that very similar to for loop...
i should over the array just once, so i cant find the maximum and then drop it and find the new maximum...
Was This Post Helpful? 0
  • +
  • -

#5 Linkowiezi  Icon User is offline

  • D.I.C Regular

Reputation: 58
  • View blog
  • Posts: 316
  • Joined: 07-October 08

Re: finding second maximumin array

Posted 15 January 2009 - 06:08 AM

You seem to have pretty much more than needed in your function.
To make it work properly you just need this part:
int max( int arr[], int s ){
  if( s >= 0 ){
    if( max1 < arr[s] ){
      if( max1 > max2 )
        max2 = max1;
      max1 = arr[s];
    }
    max( arr, s-1 );
  }
  return max2;
}

And ofc you need to make you main() function an int, and put in a return 0; at the end of it.
And this is because main should always be declared an int.
It may be that some compilers allow otherwise and might even change it to an int with a return statement at the end without you ever having to worry about it.
But you should always make your main like this:
int main(){
  return 0;
}
//  This is also an approach if you want it to be able to take runtime arguments
int main( int argc, char *argv[] ){
  return 0;
}


EDIT: You should also change <iostream.h> to just <iostream> and also toss in a 'using namespace std' on the next line under it.
And it is also good to try to avoid using global variables.

This post has been edited by Linkowiezi: 15 January 2009 - 06:10 AM

Was This Post Helpful? 0
  • +
  • -

#6 drordh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 15-January 09

Re: finding second maximumin array

Posted 15 January 2009 - 07:34 AM

View PostLinkowiezi, on 15 Jan, 2009 - 05:08 AM, said:

You seem to have pretty much more than needed in your function.
To make it work properly you just need this part:
int max( int arr[], int s ){
  if( s >= 0 ){
    if( max1 < arr[s] ){
      if( max1 > max2 )
        max2 = max1;
      max1 = arr[s];
    }
    max( arr, s-1 );
  }
  return max2;
}

And ofc you need to make you main() function an int, and put in a return 0; at the end of it.
And this is because main should always be declared an int.
It may be that some compilers allow otherwise and might even change it to an int with a return statement at the end without you ever having to worry about it.
But you should always make your main like this:
int main(){
  return 0;
}
//  This is also an approach if you want it to be able to take runtime arguments
int main( int argc, char *argv[] ){
  return 0;
}


EDIT: You should also change <iostream.h> to just <iostream> and also toss in a 'using namespace std' on the next line under it.
And it is also good to try to avoid using global variables.




its not good.
because i can loss solution.
for exemple if max2>max1
but anyway its not good.
i have to do it in recursive way..
and not with tail recursive...
tail recursive means that it very similar to for loop.
Was This Post Helpful? 0
  • +
  • -

#7 Linkowiezi  Icon User is offline

  • D.I.C Regular

Reputation: 58
  • View blog
  • Posts: 316
  • Joined: 07-October 08

Re: finding second maximumin array

Posted 15 January 2009 - 07:54 AM

That is similar to a for loop.
And it doesn't skip any slutions.

Your's on the other hand could skip solutions but the one I posted don't.

It will continue to call itself until s reaches 0 just like this for loop:
for( int i = 10; i >= 0; i-- ){ /* Do Stuff */ }


Btw, I didn't say that the recursive functin I posted was good, I just simply removed a coupple of lines from your code to make it 'work'.
Was This Post Helpful? 0
  • +
  • -

#8 drordh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 15-January 09

Re: finding second maximumin array

Posted 15 January 2009 - 08:03 AM

View PostLinkowiezi, on 15 Jan, 2009 - 06:54 AM, said:

That is similar to a for loop.
And it doesn't skip any slutions.

Your's on the other hand could skip solutions but the one I posted don't.

It will continue to call itself until s reaches 0 just like this for loop:
for( int i = 10; i >= 0; i-- ){ /* Do Stuff */ }


Btw, I didn't say that the recursive functin I posted was good, I just simply removed a coupple of lines from your code to make it 'work'.


thanks anyway..
if you have a smart recursive way it will be helpfull! :)
Was This Post Helpful? 0
  • +
  • -

#9 AmitTheInfinity  Icon User is offline

  • C Surfing ∞
  • member icon

Reputation: 119
  • View blog
  • Posts: 1,565
  • Joined: 25-January 07

Re: finding second maximumin array

Posted 15 January 2009 - 08:07 AM

This can be another approach [I don't claim it to be the optimal solution. :)]

#include<stdio.h>

float second_max(float* , int, float, float);


int main()
{

float arr[] = {85,782,45,358,74};
float max=arr[0];
float max2=arr[0];
printf("%f", second_max(arr,5,max,max2));

getch();
return 0;
}

float second_max(float* arr, int size, float max, float max2)
{
	  if(size==0)	
		 return max2; // return final max2 value
	  if(max < *arr) 
	  {
			 if(size == 1) // just trying to take care that I should not increment array beyond limits, so if size reaches to it's end, i send same value instead of next array element [arr+1].  As in next recursive call size will be size-1 anyways and we return max2 from there without looking at array.
					 return second_max( arr, (size-1), *arr, max); // current value is max till now .
			 return second_max( (arr+1), (size-1), *arr, max);
			 
	  }
	  else if (max > *arr && max2 < *arr) 
	  {
		   if(size == 1)
					 return second_max( arr, (size-1), max, *arr); // current value is max2 till now.
		   return second_max( (arr+1), (size-1), max, *arr);
	  }
	  else 
	  {
		   if(size == 1)
					 return second_max( arr, (size-1), max, max2); // current value is not one of the 2 maximums.
		   return second_max( (arr+1), (size-1), max, max2);
	  }
}




I hope this will help you. :)
Was This Post Helpful? 0
  • +
  • -

#10 drordh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 15-January 09

Re: finding second maximumin array

Posted 15 January 2009 - 09:44 AM

View PostAmitTheInfinity, on 15 Jan, 2009 - 07:07 AM, said:

This can be another approach [I don't claim it to be the optimal solution. :)]

#include<stdio.h>

float second_max(float* , int, float, float);


int main()
{

float arr[] = {85,782,45,358,74};
float max=arr[0];
float max2=arr[0];
printf("%f", second_max(arr,5,max,max2));

getch();
return 0;
}

float second_max(float* arr, int size, float max, float max2)
{
	  if(size==0)	
		 return max2; // return final max2 value
	  if(max < *arr) 
	  {
			 if(size == 1) // just trying to take care that I should not increment array beyond limits, so if size reaches to it's end, i send same value instead of next array element [arr+1].  As in next recursive call size will be size-1 anyways and we return max2 from there without looking at array.
					 return second_max( arr, (size-1), *arr, max); // current value is max till now .
			 return second_max( (arr+1), (size-1), *arr, max);
			 
	  }
	  else if (max > *arr && max2 < *arr) 
	  {
		   if(size == 1)
					 return second_max( arr, (size-1), max, *arr); // current value is max2 till now.
		   return second_max( (arr+1), (size-1), max, *arr);
	  }
	  else 
	  {
		   if(size == 1)
					 return second_max( arr, (size-1), max, max2); // current value is not one of the 2 maximums.
		   return second_max( (arr+1), (size-1), max, max2);
	  }
}




I hope this will help you. :)


can you explain me what are the lines means?
because i work with c++ and i dont know...

printf("%f", second_max(arr,5,max,max2));
getch();
Was This Post Helpful? 0
  • +
  • -

#11 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Re: finding second maximumin array

Posted 15 January 2009 - 11:30 AM

Quote

...can you explain me what are the lines means? because i work with c++ and i dont know...


// cout <<  second_max(arr,5,max,max2);
printf("%f", second_max(arr,5,max,max2));

// cin.sync(); // flush cin stream
// cin.get(); // wait for the 'Enter' key to be pressed
getch(); // wait for ANY key to be pressed <Note: not part of standard C>



But you might also like to look at this below, that seems? to work but may need more testing ...

Shalom,
David
http://developers-he...index.php/topic,46.0.html
http://developers-he.../index.p...opic,106.0.html

// Using recursion to find ...
// the 'top 2' element's in an array.
// Note! Array must have at least two elements.

#include <iostream>
using namespace std;

struct Top2
{
    int one;
    int two;
};

void getTop2( int arr[], int s, Top2 &p )
{
    if( s >= 0 )
    {
        if( arr[s] > p.one )
        {
            p.two = p.one;
            p.one = arr[s];
        }
        else if( arr[s] > p.two )
            p.two = arr[s];
            
        getTop2( arr, s-1, p );
    }
}


int main() 
{
    int arr[]={14,99,-100, 50,2,24,61,88,13,55,7,100};
    int s= sizeof arr / sizeof arr[0];
    Top2 p2;
    p2.one = arr[s-1]; // initialize with values at top index
    p2.two = arr[s-2];
    
    if(p2.two > p2.one) // swap
    {
        int tmp = p2.two;
        p2.two = p2.one;
        p2.one = tmp;
    }
        
    getTop2(arr, s-3, p2); 
    cout <<"The top 2 are " << p2.one << ", " << p2.two
         <<"\nPress 'Enter' to continue ..." << flush;
    cin.get();
}

This post has been edited by David W: 15 January 2009 - 12:52 PM

Was This Post Helpful? 0
  • +
  • -

#12 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Re: finding second maximumin array

Posted 15 January 2009 - 12:58 PM

Or this Top 3 version ... which seems to confirm this approach ...

Shalom,
David
http://developers-he...index.php/topic,46.0.html
http://developers-he.../index.p...opic,106.0.html


// Using recursion to find ...
// the 'top 3' element's in an array.
// Note! Array must have at least three elements.

#include <iostream>
using namespace std;

class Top3
{
public:
    int one;
    int two;
    int three;
};

void getTop3( int arr[], int s, Top3 &t )
{
    if( s >= 0 )
    {
        if( arr[s] > t.one )
        {
            t.three = t.two;
            t.two = t.one;
            t.one = arr[s];
        }
        else if( arr[s] > t.two )
        {
            t.three = t.two;
            t.two = arr[s];
        }
        else if( arr[s] > t.three )
            t.three = arr[s];
            
        getTop3( arr, s-1, t );
    }

}

void order( int &a, int &b )
{
    if( a > b ) // swap
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
}
    

int main() 
{
    int arr[]={14,99,-100,98,50,2,24,61,88,13,55,7,100};
    int s= sizeof arr / sizeof arr[0];
    Top3 t3;
    t3.one = arr[s-1]; // initialize with values at top index
    t3.two = arr[s-2];
    t3.three = arr[s-3];
    
    // bubble sort these 3 ...
    order( t3.three, t3.two );  // biggest in two
    order( t3.two, t3.one );    // biggest in one
    order( t3.three, t3.two );  // biggest in two
        
    getTop3(arr, s-4, t3); 
    cout <<"The top 3 are " << t3.one << ", " << t3.two << " and " << t3.three
         <<"\nPress 'Enter' to continue ..." << flush;
    cin.get();
}

Was This Post Helpful? 0
  • +
  • -

#13 drordh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 15-January 09

Re: finding second maximumin array

Posted 16 January 2009 - 06:25 AM

View PostDavid W, on 15 Jan, 2009 - 11:58 AM, said:

Or this Top 3 version ... which seems to confirm this approach ...

Shalom,
David
http://developers-he...index.php/topic,46.0.html
http://developers-he.../index.p...opic,106.0.html


// Using recursion to find ...
// the 'top 3' element's in an array.
// Note! Array must have at least three elements.

#include <iostream>
using namespace std;

class Top3
{
public:
    int one;
    int two;
    int three;
};

void getTop3( int arr[], int s, Top3 &t )
{
    if( s >= 0 )
    {
        if( arr[s] > t.one )
        {
            t.three = t.two;
            t.two = t.one;
            t.one = arr[s];
        }
        else if( arr[s] > t.two )
        {
            t.three = t.two;
            t.two = arr[s];
        }
        else if( arr[s] > t.three )
            t.three = arr[s];
            
        getTop3( arr, s-1, t );
    }

}

void order( int &a, int &b )
{
    if( a > b ) // swap
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
}
    

int main() 
{
    int arr[]={14,99,-100,98,50,2,24,61,88,13,55,7,100};
    int s= sizeof arr / sizeof arr[0];
    Top3 t3;
    t3.one = arr[s-1]; // initialize with values at top index
    t3.two = arr[s-2];
    t3.three = arr[s-3];
    
    // bubble sort these 3 ...
    order( t3.three, t3.two );  // biggest in two
    order( t3.two, t3.one );    // biggest in one
    order( t3.three, t3.two );  // biggest in two
        
    getTop3(arr, s-4, t3); 
    cout <<"The top 3 are " << t3.one << ", " << t3.two << " and " << t3.three
         <<"\nPress 'Enter' to continue ..." << flush;
    cin.get();
}


thank you very much david!!!!
it was very helpfull....
i over just on the first code and it was good!
have a good weekend!!! :)
Was This Post Helpful? 0
  • +
  • -

#14 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Re: finding second maximumin array

Posted 16 January 2009 - 11:13 AM

Quote

...thank you very much david!!!! it was very helpfull....have a good weekend!!! :)


You are very welcome. Thank you for your reply ... and you too have a wonderfully blessed week ... and end.

Shalom,
David
http://developers-he...index.php/topic,46.0.html
http://developers-he.../index.p...opic,106.0.html
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1