• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
shadowstep00

Find Min with Recursion

33 posts in this topic

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
0

Share this post


Link to post
Share on other sites

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

Edited by shadowstep00
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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?

0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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));
}
0

Share this post


Link to post
Share on other sites

 

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.

0

Share this post


Link to post
Share on other sites

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));
}
0

Share this post


Link to post
Share on other sites

 


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?

0

Share this post


Link to post
Share on other sites


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).

0

Share this post


Link to post
Share on other sites

 


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.

0

Share this post


Link to post
Share on other sites

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?

0

Share this post


Link to post
Share on other sites

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
Realized I needed a bit of clarification.
1

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites

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.

 

Meh, it is a micro-optimization in the part that doesn't dominate. My hunch is that the added branch would slow things down if you were worried about performance.

 

As mentioned, there are solutions that require zero comparisons. Keep the collection sorted in the first place and don't worry about it.

0

Share this post


Link to post
Share on other sites
No, it's not a micro-optimization: It's the solution to a brain teaser. I think I posed the question correctly. If you don't enjoy that kind of thing, that's OK. But trying to argue about the real-life complexities of the situation is missing the interesting mathematical curiosity that I was pointing at.
0

Share this post


Link to post
Share on other sites

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


What part are you having a hard time with?
0

Share this post


Link to post
Share on other sites

The problem is that the index keeps changing during the recursions.

And I dont want to make a classical search in order to find where the min is located inside the A[10]. 

I wanna know if there is a solution on how to return the index without searching.

 

6z1w5u.png

Edited by shadowstep00
0

Share this post


Link to post
Share on other sites

The easy way is with just searching. Is there another more clever way?

#include <stdio.h>

double recursive_min(double T[], int n,int *index);

int main(){
	double T[10] = {4,50,-10,-6,7,-11.6,7,-1,8,-9};
	double min;
	int index;
	min = recursive_min(T,11,&index);
  
    printf("min = %g\n", min);
    printf("Index = %d\n",index);
	
}

double recursive_min(double T[], int n,int *index){
	int i;
	if (n == 1)	
		return T[0];
	else{
		double x = recursive_min(T,n/2,index);
		double y = recursive_min(T + n/2, n - n/2,index);
		if (x < y)
		{
			for (i = 0; i<=n/2; i++){
				if (T[i] == x) 
					*index = i;
		}
			return x;
		}
		else 
		{
			for (i =n/2 ; i<=n; i++){
				if (T[i] == y) 
					*index = i;
				}
			return y;
		}
	}
}
Edited by shadowstep00
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0