最小覆盖(外接)圆算法,java版

最近在学习算法和数据结构,刚好公司有了一个需要算法应用的场景。
需求时一个最小覆盖圆问题。 在LBS相关的应用中,可能存在这样的场景, 给定n个点的经纬度,求一个最小的,覆盖所有这n个点的圆的圆心。 地球时球形,经纬度不同于二维平面上的xy坐标。但是当几个点的距离不那么遥远的时候,二者近似。

这个算法并不简单。借助于google,找到了2篇参考文章。下面是参考地址:
http://wenku.baidu.com/view/47c0c1758e9951e79b8927b3.html
http://web.nmsu.edu/~xiumin/project/smallest_enclosing_circle/

下面是实现代码:

继续阅读“最小覆盖(外接)圆算法,java版”

最大子数组问题,非递归实现,c语言实现。

这篇博客中,描述了“最大子数组”问题,和一个递归,分治思路的实现。这里给出一个非递归的实现。 由于子数组必须是连续的,因此问题可以从头到尾扫描数组一次,找出最终解。

思路是,始终保留6个变量,分别是 result_start, result_end, result_sum, curr_start, curr_end, curr_sum. 游标从数组的第0号元素开始,每经过一个元素,就把它的值加到curr_sum中。 每当发现curr_sum的值大于result_sum时,就把curr的3个变量的值赋值到result的3个变量中。 但是其中有一点要注意的是,任何时候,只要curr_sum的值小于0,就要把curr_start游标跳转到下一个元素,并把curr_sum清零,重新开始计。 因为curr_sum为0时,就代表之前的所有元素加和小于0.那么后续任何元素与这个小于0的数相加,肯定都不是最大子数组,应该把边和小于0的元素去掉。

实现代码如下:

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

#define LENGTH(s) (sizeof(s) / sizeof(int))

int main(void) {

	int array[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
	//int array[] = {-1, -2, -3};

	int result_start = 0, result_end = 0, result_sum = 0;
	int curr_start = 0;
	int curr_end = 0;
	int curr_sum = 0;

	int length = LENGTH(array);

	int i;
	for (i = 0; i < length; i++) {
		curr_end = i;
		curr_sum = curr_sum + array[i];

		if (curr_sum < 0) {
			curr_start = i + 1;
			curr_sum = 0;
			continue;
		}

		if (curr_sum > result_sum) {
			result_sum = curr_sum;
			result_start = curr_start;
			result_end = curr_end;
		}
	}

	printf("max subarry : %d - %d, sum : %d n", result_start, result_end, result_sum);

	return EXIT_SUCCESS;
}

(全文完)

最大子数组问题,分治递归实现,c语言实现

最大字数组问题的简单描述:给定一个输入的数组,求解此数组的子数组(元素必须是连续的)中所有元素和最大的那个子数组。 这个算法最简单也最容易理解的应该是非递归的方式。 这里看到《算法导论》第3版讲到“分治”这一章给出的案例,用c语言实现一下,以加深印象。

这个算法的分治思路是:给定的输入数组,取中间元素将数组分为左右连个子数组,那么这个输入数组的最大子数组可能有3种情况。 分别是,a)完全位于左子数组中,b)完全位于右子数组中,和c)跨越中点。 那么问题就成了,求解这3种情况下的最大子数组。而a和b情况,刚好与求解最初输入数组类似,形成递归。 c情况则是一个简单问题。由一个单独的函数实现。代码如下:

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

#define LENGTH(s) (sizeof(s) / sizeof(int))

struct subarray{
	int start;
	int end;
	int sum;
};

void find_max_cross(int* array, int start, int mid, int end, struct subarray *p) {
	int left_sum = 0;
	int left = 0;
	int right_sum = 0;
	int right = 0;

	int tmp_sum = 0;

	int i = 0;
	for (i = mid; i >= start; i--) {
		tmp_sum = tmp_sum + array[i];
		if (tmp_sum > left_sum) {
			left_sum = tmp_sum;
			left = i;
		}
	}

	tmp_sum = 0;
	for (i = mid + 1; i<= end; i++) {
		tmp_sum = tmp_sum + array[i];
		if (tmp_sum > right_sum) {
			right_sum = tmp_sum;
			right = i;
		}
	}

	p->start = left;
	p->end = right;
	p->sum = left_sum + right_sum;
}

void find_max_subarray(int* array, int start, int end, struct subarray *p) {
	struct subarray sa_left;
	struct subarray sa_right;
	struct subarray sa_cross;

	if (start == end) {
		p->start = start;
		p->end = start;
		p->sum = array[start];
		return;
	}

	int mid = (start + end) / 2;

	find_max_subarray(array, start, mid, &sa_left);
	find_max_subarray(array, mid + 1, end, &sa_right);
	find_max_cross(array, start, mid, end, &sa_cross);

	if (sa_left.sum > sa_right.sum && sa_left.sum > sa_cross.sum) {
		p->start = sa_left.start;
		p->end = sa_left.end;
		p->sum = sa_left.sum;
	} else if (sa_right.sum > sa_left.sum && sa_right.sum > sa_cross.sum) {
		p->start = sa_right.start;
		p->end = sa_right.end;
		p->sum = sa_right.sum;
	} else {
		p->start = sa_cross.start;
		p->end = sa_cross.end;
		p->sum = sa_cross.sum;
	}
}

int main(void) {

	int array[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};

	struct subarray sa;

	find_max_subarray(array, 0, LENGTH(array) - 1, &sa);

	printf("max subarray : %d - %d, sum : %d", sa.start, sa.end, sa.sum);
	return EXIT_SUCCESS;
}

(全文完)