Jump to content
Site Stability Read more... ×
  • Advertisement
Sign in to follow this  
shadowstep00

Find Min with Recursion

This topic is 2089 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement

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

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?

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

Share this post


Link to post
Share on other sites

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

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

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!