Jump to content

  • Log In with Google      Sign In   
  • Create Account


Find Min with Recursion


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
33 replies to this topic

#1 shadowstep00   Members   -  Reputation: 474

Like
0Likes
Like

Posted 30 January 2014 - 09:41 AM

So I am trying to create an algorithm in C that finds the Min number of an array A[n] using recursion.
 
What the algorithm does is split the array to  2 equal subsections until the subsections become with only one position left. Until n = 1 so min = A[0]. Then it goes back and the subsectopms start comparing each other.
 

 
This is where I have gotten so far.
 

#include <stdio.h>
#define N 10

int min_num(double T[],int n);

int main()
{
	double T[]={4,5,10,5,7,3,6,2,8,9};
	double min;
	min = min_num(T,N);

	printf("min = %g\n",min);
	return 0;
}

int min_num(double T[],int n)
{

	double min; // the min number
	if (n == 1)
		min = T[0];

	else
	{
		int k;
		k = n/2;
		double SubsectionA_T[k];
		double SubsectionB_T[n-k];

		int i;
		double x,y;
		for (i=0;i<k;i++)
			SubsectionA_T[i] = T[i];
		for (i=k; i<N; i++)
			SubsectionB_T[i] = T[i];

		x = min_num(SubsectionA_T, k);
		y = min_num(SubsectionB_T, n-k);
		min = x;
		if (x > y)
			min = y;
	}
	return min;
}


Edited by shadowstep00, 30 January 2014 - 12:01 PM.

Failure is not an option...


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 12362

Like
6Likes
Like

Posted 30 January 2014 - 10:06 AM

Oh, geez! Don't make copies of the data! All you need to do is pass pointers into the original data in the recursive call.

 

Why are you passing k+1 to the recursive call for the second half?

 

[EDIT: Also, you are happily writing to SubsectionB_T outside the bounds of the array...]


Edited by Álvaro, 30 January 2014 - 10:12 AM.


#3 shadowstep00   Members   -  Reputation: 474

Like
0Likes
Like

Posted 30 January 2014 - 10:25 AM

Yeah true... Too many unnecessary mistakes... I will take a look at the code again. tongue.png


Edited by shadowstep00, 30 January 2014 - 10:26 AM.

Failure is not an option...


#4 shadowstep00   Members   -  Reputation: 474

Like
0Likes
Like

Posted 30 January 2014 - 11:37 AM

So I repost the code

#include <stdio.h>
#define N 10

int min_num(double T[],int n);
void subsections(double T[], int n, int k, double SubsectionA_T[], double SubsectionB_T[]);

int main()
{
	double T[]={4,5,10,5,7,3,6,2,8,9};
	double min;
	min = min_num(T,N);

	printf("min = %g\n",min);
	return 0;
}

int min_num(double T[],int n)
{

	double min;
	if (n == 1)
		min = T[0];

	else
	{
		int k;
		k = n/2;


		double SubsectionA_T[k];
		double SubsectionB_T[n-k];

		double x,y;

		subsections( T, n, k,SubsectionA_T, SubsectionB_T);

		x = min_num(SubsectionA_T, k);
		y = min_num(SubsectionB_T, k-n);
		min = x;
		if (x > y)
			min = y;
	}
	return min;
}

void subsections(double T[], int n, int k, double SubsectionA_T[], double SubsectionB_T[])
{
	int i;
	int j = 0;
	for (i=0;i<k;i++)
		SubsectionA_T[i] = T[i];
	for (i=k; i<n; i++)
	{
		SubsectionB_T[j] = T[i];
		j++;
	}
}

The void function has problems with the array index again...(I think)


Edited by shadowstep00, 30 January 2014 - 11:47 AM.

Failure is not an option...


#5 Álvaro   Crossbones+   -  Reputation: 12362

Like
0Likes
Like

Posted 30 January 2014 - 12:01 PM

You are making it way too complicated. You don't need SubsectionA_T or SubsectionB_T at all. Just call min_num with a pointer into the same array that was passed to the function. Do you know how pointer arithmetic works?



#6 shadowstep00   Members   -  Reputation: 474

Like
0Likes
Like

Posted 30 January 2014 - 12:08 PM

Well I think I know. For example if: int *p points to 1004 place in memory. 

The *(p+1) will point on 1008. This is what you mean?


Edited by shadowstep00, 30 January 2014 - 12:12 PM.

Failure is not an option...


#7 Álvaro   Crossbones+   -  Reputation: 12362

Like
0Likes
Like

Posted 30 January 2014 - 12:12 PM

Sure, that's enough. You should be able to solve the problem without copying the data to other buffers.



#8 Ryan_001   Prime Members   -  Reputation: 1279

Like
0Likes
Like

Posted 30 January 2014 - 12:17 PM

*edit: see below

Edited by Ryan_001, 30 January 2014 - 12:26 PM.


#9 Álvaro   Crossbones+   -  Reputation: 12362

Like
0Likes
Like

Posted 30 January 2014 - 12:20 PM

He wasn't asking for a solution.

 

But here's mine: ;)

#include <stdio.h>

double min(double a, double b) {
  return a < b ? a : b;
}

double recursive_min(double *data, unsigned n) {
  return n==1 ? data[0] : min(recursive_min(data, n/2), recursive_min(data + n/2, n - n/2));
}

int main() {
  double a[13] = {31.0, 26.0, 23.0, 15.0, 42.0, 23.0, 53.0, 28.0, 12.0, 40.0, 45.0, 20.0, 39.0};
 
  printf("%lf\n", recursive_min(a, 13));
}


#10 Ryan_001   Prime Members   -  Reputation: 1279

Like
0Likes
Like

Posted 30 January 2014 - 12:26 PM

 

He wasn't asking for a solution.

 

But here's mine: ;)

#include <stdio.h>

double min(double a, double b) {
  return a < b ? a : b;
}

double recursive_min(double *data, unsigned n) {
  return n==1 ? data[0] : min(recursive_min(data, n/2), recursive_min(data + n/2, n - n/2));
}

int main() {
  double a[13] = {31.0, 26.0, 23.0, 15.0, 42.0, 23.0, 53.0, 28.0, 12.0, 40.0, 45.0, 20.0, 39.0};
 
  printf("%lf\n", recursive_min(a, 13));
}

 

But that would go into a infinite recursion on a zero sized array ;)  I was trying to keep mine a bit more readable.  I didn't notice he didn't want a solution, my apologizes, I will erase my post.



#11 Álvaro   Crossbones+   -  Reputation: 12362

Like
0Likes
Like

Posted 30 January 2014 - 12:35 PM


But that would go into a infinite recursion on a zero sized array ;)

 

True! There should probably be a comment indicating that n should be at least 1, and perhaps an assert.

 

But what is the minimum of zero things? It should probably be +Infinity, I guess...

 

 

 

I was trying to keep mine a bit more readable.

 

I find mine readable, actually. It's only hard to read if you are not used to seeing ?:.

 

Is this better?

double recursive_min(double *data, unsigned n) {
  if (n==1)
    return data[0];
  return min(recursive_min(data, n/2),
             recursive_min(data + n/2, n - n/2));
}


#12 Strewya   Members   -  Reputation: 1324

Like
0Likes
Like

Posted 30 January 2014 - 12:48 PM

 


But that would go into a infinite recursion on a zero sized array ;)

 

True! There should probably be a comment indicating that n should be at least 1, and perhaps an assert.

 

But what is the minimum of zero things? It should probably be +Infinity, I guess...

Or you could check if n == 0, and return 0 if so?


devstropo.blogspot.com - Random stuff about my gamedev hobby


#13 Álvaro   Crossbones+   -  Reputation: 12362

Like
0Likes
Like

Posted 30 January 2014 - 12:54 PM


Or you could check if n == 0, and return 0 if so?

 

No! Defining the minimum of zero things to be zero is a very bad idea. It violates basic features that people expect, like the minimum of the union of two sets being the minimum of the minima of the sets (the property my code uses in the recursion, precisely).



#14 Ryan_001   Prime Members   -  Reputation: 1279

Like
0Likes
Like

Posted 30 January 2014 - 01:07 PM

 


But that would go into a infinite recursion on a zero sized array ;)

 

True! There should probably be a comment indicating that n should be at least 1, and perhaps an assert.

 

But what is the minimum of zero things? It should probably be +Infinity, I guess...

 

 

 

I was trying to keep mine a bit more readable.

 

I find mine readable, actually. It's only hard to read if you are not used to seeing ?:.

 

Is this better?

double recursive_min(double *data, unsigned n) {
  if (n==1)
    return data[0];
  return min(recursive_min(data, n/2),
             recursive_min(data + n/2, n - n/2));
}

 

Sorry, I should've been more clear.  It was a joke.  Perhaps I should've written it in italics or comic san serif?

 

When I was in school we'd be given silly assignments like the OP posted.  I'd give an answer like you presented (ie. the proper solution) and inevitably get a mark deducted because the prof would say something like 'it doesn't handle zero sized arrays'.  Which is true, except that you can't define a zero sized array.  Course that would lead into a long discussion about use cases, with arguments like 'well perhaps a nullptr was passed' and I'd point out that the 'true' answer (that which the prof posted) didn't bother to check for that either.  It always ended up being a whole lotta nonsense the irony being that searching an array in C (or C++) by using a subdivide algorithm is one of the worst ways to do so.

 

And so ya, it was a smart-ass comment meant as a joke.



#15 Álvaro   Crossbones+   -  Reputation: 12362

Like
0Likes
Like

Posted 30 January 2014 - 01:15 PM

Here's a tricky question:

 

When you compute the minimum of N things, whether you use the recursive version or the iterative version, you'll end up performing about N comparisons. How many comparisons are needed to compute both the minimum and the maximum?



#16 frob   Moderators   -  Reputation: 19624

Like
1Likes
Like

Posted 30 January 2014 - 02:02 PM

Here's a tricky question:

 

When you compute the minimum of N things, whether you use the recursive version or the iterative version, you'll end up performing about N comparisons. How many comparisons are needed to compute both the minimum and the maximum?

 

If you were the original poster I would suspect homework, but since you're not...

 

 

 

How many are needed depends on what you already know.

 

 

 

If you know the collection is already sorted you can use the endpoints. No comparisons are needed.

 

If the collection is unsorted and you already know the value but are searching for them in a collection, the average number of comparisons is 1/2 of the collection size and the worst case of comparisons is the full container size. Since you must do this for both minimum and maximum, will be N on average and 2N worst case.

 

If the collection is unsorted and the maximum and minimum are unknown then it requires a comparison against every element. The number of comparisons is equal to the number of elements in the collection minus one (the first element starts as the initial best value).  Since the problem's definition requires a test against every element, N-1 is the lowest bound on the number of comparisons for a single pass.

 

If you want both the minimum and maximum value it depends on if you are performing two operations or one. You will need two comparisons for each, one against the best known minimum and another against the best known maximum. A few microprocessors provide CPU instruction that performs both tests, and I'm not sure if you would count that as one comparison or two. Either way, for the situations game developers usually care about doing this on a single core and a flat array will be most efficient to simply walk the list; cache effects will come into play and a simple linear traversal will result in both the minimum number of comparisons and good clock time.

 

 

 

 

The minimum number of comparisons does not always equate to most efficient for a situation.

 

Most of us have multiple processors available. Large data sets that span multiple devices offer non-uniform memory speeds and parallel space options. You can exchange linear time and linear space for parallel time or parallel space for a small cost.

 

If multiple processors are available you can partition the work among the processors you might run a pass on each partition in parallel, gather the work together, and run a second pass against the results of each partition. Similarly there are SIMD instructions you could perform on a single processor. When access time is not constant, such as having terabytes of data spread across data tapes rather than disk drives, a similar partition may make sense. There are several algorithms such as QuickSelect that may make sense in those situations as you can exchange time and space in data processing. 

 

You will perform more comparisons in these cases but likely complete the search in less clock time. 


Edited by frob, 30 January 2014 - 02:10 PM.
Realized I needed a bit of clarification.

Check out my personal indie blog at bryanwagstaff.com.

#17 shadowstep00   Members   -  Reputation: 474

Like
0Likes
Like

Posted 30 January 2014 - 03:45 PM

I looked through your solutions which were far better than my code. (translated Alvaro's code to be able to read it) :P

 

The funny thing is that the last code which I posted only had one careless little mistake which it didin't make it work.

That was on line:  y = min_num(SubsectionB_T, k-n); where instead of n-k I had written k-n.

After I saw your code I took a look at my code to find out what did I do wrong. And after 1 min I found that little mistake.

I laughed so hard. :P

 

Anyways guys thanks for taking the time helping me out.

Now I will try to modify the code in order for the function to return where the min is located.


Failure is not an option...


#18 Álvaro   Crossbones+   -  Reputation: 12362

Like
0Likes
Like

Posted 30 January 2014 - 04:06 PM

The funny thing is that the last code which I posted only had one careless little mistake which it didin't make it work.


No, the last code you posted contained this piece:
 
void subsections(double T[], int n, int k, double SubsectionA_T[], double SubsectionB_T[])
{
	int i;
	int j = 0;
	for (i=0;i<k;i++)
		SubsectionA_T[i] = T[i];
	for (i=k; i<n; i++)
	{
		SubsectionB_T[j] = T[i];
		j++;
	}
}
Imagine n is 10, so k is 5 and SubsectionA_T and SubsectionB_T are arrays of length 5. When you write into SubsectionB_T, you do it with indices 5, 6, ...

I pointed this problem out in the edit of my first post.

[EDIT: Ahhh, no! You did use a different variable j, so the code is more or less correct. You are still making copies of the data, though. Anyway, sorry about that.]

Edited by Álvaro, 30 January 2014 - 04:17 PM.


#19 Álvaro   Crossbones+   -  Reputation: 12362

Like
0Likes
Like

Posted 30 January 2014 - 04:08 PM

I frob missed the trick:

You can process the elements two at a time, compare them and then only use the smaller of the two to try to update the minimum and only use the larger of the two to try to update the maximum. This requires about N*3/2 comparisons.

I am not making any claims about practical usability of this trick: It's just a neat little puzzle.

#20 shadowstep00   Members   -  Reputation: 474

Like
0Likes
Like

Posted 30 January 2014 - 05:03 PM

So guys any ideas on how to make the code return except for the value also the position of min? 


Failure is not an option...





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS