mid.cpp

来自「在一维空间上」· C++ 代码 · 共 104 行

#include <stdio.h>
#include <stdlib.h>

int x[] = {1, 3, 8, 22,97, 99, 100, 153, 180, 182, 185, 201, 213};
struct pair
{
	int x1;
	int x2;
};
typedef struct pair pair_t;
void get_min (int x[], int n, pair_t *res);
int comp (pair_t *res1, pair_t *res2, pair_t *res3, pair_t *res);

int main (void)
{
	int i;
	printf ("x[%d] = ", sizeof (x)/sizeof (int));
	for (i = 0; i < sizeof (x)/sizeof (int); i++)
	{
		if (i == 6)
			printf ("\n");
		printf (" %d ", x[i]);
	}
	printf ("\n");

	pair_t res;
	get_min (x, sizeof (x)/sizeof (int), &res);


	return 0;
}
void show_x (int x[], int n)
{
	int i;
	printf ("x[] = ");
	for (i = 0; i < n; i++)
	{
		printf ("%d ", x[i]);

	}
	printf ("\n");
}
void show_pair (pair_t *res)
{
	printf ("pair = ( %d, %d)\n", res->x1, res->x2);
}
void get_min (int x[], int n, pair_t *res)
{
	if (n <= 1)
	{
		printf ("error\n");
		
		return;
	}
	if (n == 2)
	{
		res->x1 = x[0];
		res->x2 = x[1];

		return;
	}
	if (n == 3)
	{
		if ((x[1] - x[0]) < (x[2] - x[1]))
		{
			res->x1 = x[0];
			res->x2 = x[1];
		}
		else
		{
			res->x1 = x[1];
			res->x2 = x[2];
		}

		return;
	}
	pair_t res1, res2, res3;
	int d = n/2 -1;
	res3.x1 = x[d];
	res3.x2 = x[d + 1];
	get_min (&x[0], n/2, &res1);
	get_min (&x[d + 1], n - n/2, &res2);
	
	printf ("n = %d\n", n);
	show_pair (&res1);
	show_pair (&res2);
	show_pair (&res3);
	comp (&res1, &res2, &res3, res);
	//show_pair (res);
}
int comp (pair_t *res1, pair_t *res2, pair_t *res3, pair_t *res)
{
	pair_t *temp \
		= (res1->x2 - res1->x1) <= (res2->x2 - res2->x1) ? res1 : res2;
	temp \
		= (temp->x2 - res->x1) <= (res3->x2 - res3->x1) ? temp : res3;
	printf ("x1 = %d, x2 = %d\n", temp->x1, temp->x2);

	res->x1 = temp->x1;
	res->x2 = temp->x2;

	return 0;
}